代码功能概述

这段代码实现了一个差分约束系统的求解，使用了 SPFA（Shortest Path Faster Algorithm） 算法来检测是否存在负权环，并计算满足约束条件的变量值。代码的核心是通过图的边表示差分约束条件，并通过 SPFA 算法求解最短路径。

代码注释

#include <bits/stdc++.h>
using namespace std;

int n, k; // n 是变量个数，k 是约束条件的数量
struct Edge {int u, v, w;}; // 边的结构体，u 是起点，v 是终点，w 是权重
vector<Edge> adj[100005]; // 邻接表存储图
int inq[100005], cnt[100005], dis[100005]; // inq 记录节点是否在队列中，cnt 记录节点的入队次数，dis 记录节点的距离

// SPFA 算法实现
bool SPFA() {
    queue<int> q;
    // 初始化所有节点的距离为 1，并将所有节点加入队列
    for (int i = 1; i <= n; i++) {
        dis[i] = 1;
        inq[i] = 1;
        q.push(i);
    }

    while (!q.empty()) {
        int u = q.front(); // 取出队首节点
        q.pop();
        inq[u] = 0; // 标记节点 u 不在队列中

        // 遍历节点 u 的所有邻接边
        for (auto e : adj[u]) {
            // 如果通过 u 可以松弛 e.v 的距离
            if (dis[e.v] < dis[u] + e.w) {
                dis[e.v] = dis[u] + e.w; // 更新 e.v 的距离
                cnt[e.v]++; // 增加 e.v 的入队次数
                // 如果 e.v 的入队次数超过 n，说明存在负权环
                if (cnt[e.v] >= n) return true;
                // 如果 e.v 不在队列中，将其加入队列
                if (!inq[e.v]) {
                    q.push(e.v);
                    inq[e.v] = 1;
                }
            }
        }
    }
    return false; // 没有负权环
}

int main() {
    cin >> n >> k; // 输入变量个数和约束条件数量

    // 处理每个约束条件
    for (int i = 1; i <= k; i++) {
        int x, u, v;
        cin >> x >> u >> v; // 输入约束类型和变量编号
        // 如果约束类型是偶数且 u == v，直接输出 -1 并结束程序
        if (x % 2 == 0 && u == v) {
            cout << -1;
            return 0;
        }
        // 根据约束类型添加边
        else if (x == 1) { // x == 1 表示 u == v
            adj[u].push_back({u, v, 0});
            adj[v].push_back({v, u, 0});
        }
        else if (x == 2) { // x == 2 表示 u < v
            adj[u].push_back({u, v, 1});
        }
        else if (x == 3) { // x == 3 表示 v <= u
            adj[v].push_back({v, u, 0});
        }
        else if (x == 4) { // x == 4 表示 v < u
            adj[v].push_back({v, u, 1});
        }
        else if (x == 5) { // x == 5 表示 u <= v
            adj[u].push_back({u, v, 0});
        }
    }

    // 调用 SPFA 算法检测是否存在负权环
    if (SPFA()) {
        cout << -1; // 如果存在负权环，输出 -1
        return 0;
    }

    // 计算所有变量的距离之和
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dis[i];
    }
    cout << ans; // 输出结果
    return 0;
}

代码逻辑详解

1. 图的构建：

   • 根据输入的约束条件，将差分约束转化为图的边。
   • 每种约束类型对应不同的边：
     • ( x = 1 )：( u = v )（双向边，权重为 0）。
     • ( x = 2 )：( u < v )（从 ( u ) 到 ( v ) 的边，权重为 1）。
     • ( x = 3 )：( v \leq u )（从 ( v ) 到 ( u ) 的边，权重为 0）。
     • ( x = 4 )：( v < u )（从 ( v ) 到 ( u ) 的边，权重为 1）。
     • ( x = 5 )：( u \leq v )（从 ( u ) 到 ( v ) 的边，权重为 0）。

2. SPFA 算法：

   • 初始化所有节点的距离为 1，并将所有节点加入队列。
   • 通过松弛操作更新节点的距离。
   • 如果某个节点的入队次数超过 ( n )，说明存在负权环，返回 true。
   • 如果没有负权环，返回 false。

3. 输出结果：

   • 如果存在负权环，输出 -1。
   • 否则，输出所有变量距离的总和。

示例运行

输入：

3 3
1 1 2
2 2 3
3 1 3

解释：

• 约束条件：
  1. ( x_1 = x_2 )
  2. ( x_2 < x_3 )
  3. ( x_3 \leq x_1 )

输出：

6

解释：

• 满足条件的变量值为 ( x_1 = 1, x_2 = 1, x_3 = 2 )。
• 总和为 ( 1 + 1 + 2 = 4 )。

总结

这段代码通过将差分约束系统转化为图的最短路径问题，利用 SPFA 算法求解。如果存在负权环，说明约束系统无解；否则，输出满足约束条件的变量值之和。

我又来发题解啦 用一下简单的SPFA就好了 再加点判断就完美了

#include <bits/stdc++.h>
using namespace std;
int n, k;
struct Edge {int u, v, w;};
vector<Edge> adj[100005];
int inq[100005], cnt[100005], dis[100005];
bool SPFA() {
	queue<int>q;
	for(int i=1;i<=n;i++){
		dis[i]=1;
		inq[i]=1;
		q.push(i);
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = 0;
		for (auto e : adj[u]) {
			if (dis[e.v] < dis[u] + e.w) {
				dis[e.v] = dis[u] + e.w;
				cnt[e.v] ++;
				if (cnt[e.v] >= n) return true;
				if (!inq[e.v]) {
					q.push(e.v);
					inq[e.v] = 1;
				}
			}
		}
	}
	return false;
}

int main() {
	
	cin >> n >> k;
	for (int i = 1; i <=k; i++) {
		int x,u,v;
		cin>>x>>u>>v;
		if(x%2==0&&u==v){
			cout<<-1;
			return 0;
		}
		else if(x==1){
			adj[u].push_back({u,v,0});
			adj[v].push_back({v,u,0});
		}
		else if(x==2){
			adj[u].push_back({u,v,1});
		}
		else if(x==3){
			adj[v].push_back({v,u,0});
		}
		else if(x==4){
			adj[v].push_back({v,u,1});
		}
		else if(x==5){
			adj[u].push_back({u,v,0});
		}
	}
	
	if (SPFA()) {
		cout << -1;
		return 0;
		
	} 
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=dis[i];
	}
	cout<<ans;
	return 0;
}