引言

在信息竞赛中会有这样一类问题，其最终的目标是维护一些变量之间的关系（比如说相等与不等，变量之间的差），对于这类问题的不同变种，我们有不同的方法进行解决。
阅读本文前，我们假设读者已经掌握了如下内容：并查集模板、深度优先搜索、负环判定方法。

维护相等与不相等关系

变量取值任意

模板

给定 nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n，mm 组关系。每组关系形如 xi=xjx_i=x_j 或 xi≠xjx_i\ne x_j。请求出是否存在一组合法解。

解法

对于这个问题，一般解法是利用并查集：我们进行离线处理，先将所有形如 xi=xjx_i=x_j 的关系的 (i,j)(i,j) 合并到一个集合中，然后再对于所有 xi≠xjx_i\ne x_j 的进行检查，如果对应的 (i,j)(i,j) 已经被划分到了一个集合中，说明不存在合法解，否则就存在合法解。

时间复杂度 O(n+m)O(n+m)。

习题

[NOI2015] 程序自动分析
同模板，注意先离散化一次。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+5;

// 标准并查集操作
int fa[N];
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i, int j) {
    int fi=find(i), fj=find(j);
    fa[fi]=fj;
}

int main() {
    int T;scanf("%d",&T);

    while (T--) {
        int n;scanf("%d",&n);
        vector<pair<int, int>> eq, neq;
        vector<int> m; // 离散化

        for (int i=0;i<n;i++) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if (c==1)eq.push_back(make_pair(a, b)); // 相等
            else neq.push_back(make_pair(a, b));// 不等
            
            m.push_back(a);m.push_back(b); // 离散化
        }

        
        sort(m.begin(), m.end()); // 排序
        m.erase(unique(m.begin(), m.end()), m.end()); // 去重
        int len = m.size();
        map<int,int> mp; // 储存离散化对应值
        for (int i=0;i<len;i++) {
            mp[m[i]]=i;
        }

        //并查集初始化
        for (int i=0;i<len;i++) {
            fa[i]=i;
        }
        //合并所有等于的
        for (auto [a,b]:eq) {
            merge(mp[a],mp[b]);
        }
        // 然后逐个判断不等于的
        bool flag = 1;
        for (auto [a,b]:neq) {
            if (find(mp[a])==find(mp[b])) {
                flag = 0;
                break;
            }
        }
        if(flag)puts("YES");
        else puts("NO");
    }
    return 0;
}

变量取值为 {0,1}

模板

给定 nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n，每个变量取值为 {0,1}\textbf{\{0,1\}}。mm 组关系。每组关系形如 xi=xjx_i=x_j 或 xi≠xjx_i\ne x_j。请求出是否存在一组合法解。

（等价变形）有 nn 个人，mm 组关系，每组关系为两人是朋友或是敌人。朋友的朋友是朋友，朋友的敌人是敌人，敌人的敌人是朋友，敌人的朋友是朋友。请确定这些关系是否矛盾。

为什么等价？
存在这个等价变形，关键在于这里的等式具有一些特殊的性质。
普通等式的都有的性质：

  • 若 a=b,b=ca=b,b=c，则 a=ca=c；
  • 若 a=b,b≠ca=b,b\ne c，则 a≠ca\ne c；
  • 若 a≠b,b=ca\ne b,b=c，则 a≠ca\ne c；

{0,1}\{0,1\} 下特殊性质：

  • 若 a≠b,b≠ca\ne b,b\ne c，则 a=ca=c。（普通等式没有！）

因此就与上面的朋友和敌人关系等价。

解法①——深度优先搜索法

对每个节点开始进行深度优先搜索，并同时维护每个节点的取值。如果从这个节点开始访问到了一个没有确定值的节点，那么就用关系确定出其取值。如果遇到了一个已经确定了值的节点，那么就用关系判定是否矛盾，矛盾就直接返回。

解法②——拓展并查集法

总所周知，正常的并查集只能维护是否在同一集合中，无法维护这样的关系。但是，通过一种叫做拓展并查集的技巧，我们就可以维护这种敌人和朋友关系。

具体来说，将每个变量 uu 拓展为两个节点 u,u′u,u'（称为原点和拓展点）。我们定义所有只要与节点 uu 连通的原点是 uu 的朋友，所有只要与节点 uu 联通的原点是 u′u' 的敌人。注意：这是我们人为定义出来的关系，后面可以看到，这样定义恰好能解决这个问题。
对于朋友关系 (u,v)(u,v)，我们需要将 (u,v)(u,v) 和 (u′,v′)(u',v') 合并（代表我的朋友是你的朋友，我的敌人是你的敌人），对于敌人关系 (u,v)(u,v)，我们只需要将 (u,v′)(u,v') 和 (u′,v)(u',v) 合并即可（代表我的敌人是你的朋友，你的朋友是我的敌人）。

举个例子，假设有三个节点，则初始并查集如下图左。
我们假设现在 (1,2)(1,2) 是敌人，那么之后的并查集如下图中。此时我们可以看到，拓展点 1′1' 和原点 22 连通，根据定义，我们知道了 22 是 11 的敌人。同理我们得知 11 是 22 的敌人。
我们再假设现在 (1,3)(1,3) 是朋友，那么我们将 (1,3),(1′,3′)(1,3),(1',3') 连接，如下图右。此时我们发现，拓展点 2′2' 和原点 1,31,3 连通，因此 22 是 1,31,3 的敌人。

拓展并查集示例

不难发现，这样的定义是完备的，因此可以完美解决这个问题。
这样定义后，就可以判断新加入的一组关系是否和前面的关系有矛盾：

  1. 新加入朋友关系 (u,v)(u,v) 是否有矛盾?
    若此时 u′u' 和 vv 在同一个集合中，那么就有矛盾（并且此时 uu 和 v′v' 也一定在一个集合中）；
  2. 新加入敌人关系 (u,v)(u,v) 是否有矛盾?
    若此时 uu 和 vv 在同一个集合中，那么就有矛盾（并且此时 u′u' 和 v′v' 也一定在一个集合中）。

在实践中，我们将所有拓展点 uu 的编号记为 u+nu+n。

解法③——带权并查集法

上面一个方法可能有一点难以理解，实践中还有一种更好用的方法来改进并查集，称作带权并查集。

在带权并查集中，我们对每一个节点额外维护一个权值 hh，作为和它的祖先的关系。
在这个情况下，我们将和祖先相同的节点权值置为 00，和祖先不同的节点权值置为 11。这个权值是动态维护的，它随着祖先的改变而改变。

因此，我们在路径压缩和合并集合时需要对这个权值进行修改。这就是带权并查集全部题目的核心。

  1. 路径压缩

    画图进行分析，我们知道了新的 h[u]h[u] 为 h[fa[u]]⊕h[u]h[fa[u]] \oplus h[u]。

    路径压缩示意图

  2. 合并集合

    同样画图进行分析。我们假设 uu 作为最后合并集合的根，然后画图可以推导出新的 hh。

    路径压缩示意图

那么，如何判定新加入关系是否矛盾呢？

假设现在的关系是 (u,v)(u,v) 之间的关系。

  • 若目前 (u,v)(u,v) 不在同一个集合当中，那么这个关系一定不矛盾，直接合并集合即可。
  • 若目前 (u,v)(u,v) 在同一集合当中，那么这个关系就可以根据 u,vu,v 与它们共同的根的关系 h[u]h[u] 和 h[v]h[v] 进行判断是否矛盾。

总结

这三种方法中，第一种深度优先搜索必须全部读入关系后离线处理，后面两种方法都可以进行在线处理。平常更推荐采用带权并查集，理解更简单，并可以维护更多信息。

习题

[NOIP2010 提高组] 关押罪犯

考虑如何求出这个影响力。根据贪心，我们应该先优先满足影响力大的罪犯，直到出现了矛盾，然后矛盾的这组关系的影响力就是最小的影响力。

参考代码（深度优先搜索）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;

const int N = 2e4+5;
const int M = 1e5+5;

int n,m;

struct Node{
    int u,v,w;
    bool operator>(const Node& o)const{
        return w>o.w;
    }
};

Node a[M];

vector<int> G[N];

int color[N];
bool dfs(int u){
    for(int v:G[u]){
        if(color[v]==-1){
            color[v]=color[u]^1; // 新节点还没有确定
            if(!dfs(v))return 0;
        }
        else if(color[v]!=(color[u]^1)){ // 已经确定了，检查是否满足条件
            return 0;
        }
    }
    return 1;
}

// 0~cnt 的关系都满足可以吗？
bool check(int cnt){
    for(int i=1;i<=n;i++)G[i].clear();

    // 0~cnt 的条件建图
    for(int i=0;i<cnt;i++){
        G[a[i].u].push_back(a[i].v);
        G[a[i].v].push_back(a[i].u);
    }

    memset(color,-1,sizeof(color));
    for(int i=1;i<=n;i++){
        if(color[i]==-1){
            color[i]=0; // 还没染色，赋初值，然后dfs
            if(!dfs(i))return 0; 
        }
    }
    return 1;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    sort(a,a+m,greater<Node>());

    int l = 0, r= m; // 二分答案，找出到底可以几个
    while(l<r){
        int mid = (l+r+1)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    printf("%d\n",a[l].w);
}

参考代码（拓展并查集）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

const int N = 2e4+5;
const int M = 1e5+5;

int n,m;

struct Node{
    int u,v,w;
    bool operator>(const Node& o)const{
        return w>o.w;
    }
};

Node a[M];

// 标准并查集，但是空间开两倍
int fa[N*2];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void unite(int u,int v){
    fa[find(u)]=find(v);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    sort(a,a+m,greater<Node>());

    for(int i=1;i<=2*n;i++){ // 初始化并查集
        fa[i]=i;
    }
    for(int i=0;i<m;i++){
        if(find(a[i].u)==find(a[i].v)){ // 矛盾了，直接输出这个影响力
            printf("%d\n",a[i].w);
            return 0;
        }
        // 拓展并查集的操作
        unite(a[i].u+n,a[i].v);
        unite(a[i].v+n,a[i].u);
    }
    // 所有都能满足，那么就是0
    puts("0");
    return 0;
}

参考代码（带权并查集）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

const int N = 2e4+5;
const int M = 1e5+5;

int n,m;

struct Node{
    int u,v,w;
    bool operator>(const Node& o)const{
        return w>o.w;
    }
};

Node a[M];

// 带权并查集
int fa[N];
int h[N];
int find(int x){
    if(fa[x]==x)return x; // 到根节点了
    int p = find(fa[x]); // 新的祖先
    h[x] = h[x]^h[fa[x]]; // 新的权值
    return fa[x]=p; // 路径压缩
}
void unite(int u,int v){
    int fu=find(u),fv=find(v);
    fa[fv]=fu;
    h[fv]=h[u]^h[v]^1;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    sort(a,a+m,greater<Node>());

    for(int i=1;i<=n;i++){ // 初始化并查集
        fa[i]=i;
        h[i]=0;
    }
    for(int i=0;i<m;i++){
        // 带权并查集判断矛盾分两步
        // 1. 是在一个集合当中
        // 2. 判断它们的权值是否满足当前的条件
        if(find(a[i].u)==find(a[i].v) && // 在一个集合当中
           h[a[i].u]==h[a[i].v]){  // 相等，不满足！
            printf("%d\n",a[i].w);
            return 0;
        }
        // 还不在一个集合里，维护它们的关系
        else{
            unite(a[i].u,a[i].v);
        }
    }

    puts("0");
    return 0;
}

维护变量的差

正常意义下差

模板

给定 nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n，mm 组关系。每组关系形如 xi−xj=dx_i-x_j=d 。请求出是否存在一组合法解。

解法

这个问题也有两个方法，一种类似于上面的深度优先搜索法，只需要将维护关系时的异或运算改为加法即可。
另一种改编自上面的带权并查集，只需要重新推出路径压缩和合并的式子即可。按照上文画图分析，很容易可以推出，在此略去（详见代码）。
在这个问题上，两种方法仍然和上面说的一样，深度优先搜索只能离线处理，带权并查集可以在线处理。

习题

[CF1850H] The Third Letter

参考代码（深度优先搜索）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N=2e5+5;
ll pos[N];
struct Edge{
    int v,w;
};
vector<Edge> G[N];

bool ok;
void dfs(int u){
    if(pos[u]==(ll)1e18){ // 1e18 代表还未访问
        pos[u]=0; // 未访问直接置为0
    }
    for(auto [v,w]:G[u]){
        if(pos[v]!=(ll)1e18){ // 已经确定权值了
            if(pos[v]!=pos[u]+w)ok=0; // 如果矛盾
        }
        else{
            pos[v]=pos[u]+w; // 不然就人工赋权值
            dfs(v);
        }
    }
}

void solve(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        G[i].clear();
    }

    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w); // 用关系建图
        G[u].push_back({v,w});
        G[v].push_back({u,-w});
    }

    for(int i=1;i<=n;i++){
        pos[i]=(ll)1e18; // 初始化所有的pos
    }

    ok=1;
    for(int i=1;i<=n;i++){
        dfs(i); // dfs
    }
    if(ok)puts("YES");
    else puts("NO");
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

参考代码（带权并查集）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N=2e5+5;

int fa[N];
ll h[N];
int find(int x){
    if(fa[x]==x)return x;
    int p=find(fa[x]);
    h[x]=h[x]+h[fa[x]]; // 路径压缩维护h
    return fa[x]=p;
}
void unite(int u,int v,ll dis){
    int fu=find(u),fv=find(v);
    fa[fv]=fu;
    h[fv]=h[u]-h[v]-dis; // 新的h[fv]（画图推导）
}

void solve(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        h[i]=0;
    }

    bool ok=1;
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        if(find(u)==find(v)){
            if(h[u]-h[v]!=w){
                ok=0;
            }
        }
        else{
            unite(u,v,w);
        }
    }

    if(ok)puts("YES");
    else puts("NO");
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

模意义下差

模板

给定模数 MM，nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n，变量取值为 {0,1,…,M−1}\{0,1,\ldots,M-1\}。给出 mm 组关系。每组关系形如 xi−xj≡d(modM)x_i-x_j\equiv d \pmod M。请求出是否存在一组合法解。

解法

事实上，这个问题是我们在 2.2 中讨论问题的强化版。2.2 中问题可看作是 M=2M=2 时的一个特例。

因此，三个方法仍然都可以采用。
深度优先搜索和带权并查集都和 2.2 中内容相同，只需修改对权值的维护操作即可，可自行推导（详见代码）。

拓展并查集此时要将每个节点拆分成 MM 个（如图），对于关系 xA−xB≡d(modM)x_A-x_B\equiv d\pmod M，我们需要将 i=0,1,…,M−1,(Ai,B(i+d mod M))i=0,1,\ldots,M-1, (A_i,B_{(i+d\bmod M)}) 这样 MM 对点合并到同一个集合中。

对于判断条件是否与前面的冲突，我们需要找出是否存在 (Ai,Bj)(A_i,B_j) 在同一个集合中，并且 i−j≢d(modM)i-j\not\equiv d\pmod M，直接枚举所有 M−1M-1 对其他的点对即可。

习题

[NOI2001] 食物链

考虑三种类型 A,B,CA,B,C 分别用 0,1,20,1,2 表示。此时，若 uu 被 vv 吃，那么两个动物类型在模意义下的差为 22 ；若 uu 吃 vv，那么两个动物类型在模意义下的差为 11；若 uu 和 vv 是同类，那么两个动物类型在模意义下的差为 00。因此我们就成功将这个问题转化为了上面的模板。由于本题不适合离线，故不给出使用深度优先搜索的示例代码。

参考代码（拓展并查集）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5;

int fa[N*3]; // 三倍空间的拓展并查集
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int u,int v){
    fa[find(u)]=find(v);
}

int main(){
    int n,k;scanf("%d%d",&n,&k);

    for(int i=1;i<=3*n;i++)fa[i]=i;

    int cnt = 0;
    for(int i=0;i<k;i++){
        int a,u,v;
        scanf("%d%d%d",&a,&u,&v);
        if(u>n || v>n){// 编号不对，是假话
            cnt++;
            continue;
        }
        if(a==2 && u==v){
            cnt++; // 我吃我自己 是假话
            continue;
        }

        // 然后判断剩下的
        if(a==1){ // 是同类，那么检查0->1 和 0->2
            if(find(u+n)==find(v)||find(u+n+n)==find(v)){
                cnt++; // 不合法
            }
            else{ // 合法，合并三组差0的点
                unite(u,v);// 0->0
                unite(u+n,v+n); //1->1
                unite(u+n+n,v+n+n); //2->2
            }   
        }
        else{ // 是x吃y的关系，检查 0->0 和 0->1
            if(find(u)==find(v) || find(u)==find(v+n)){
                cnt++; // 不合法
            }
            else{ // 合法，合并三组差2的点
                unite(u,v+n+n);// 0->2
                unite(u+n,v);// 1->0
                unite(u+n+n,v+n);// 2->1
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

参考代码（带权并查集）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5;

int fa[N]; // 一倍空间的带权并查集
int h[N]; // 权值
int find(int x){
    if(fa[x]==x)return x;
    int p=find(fa[x]);
    h[x]=(h[x]+h[fa[x]])%3;
    return fa[x]=p;
}
void unite(int u,int v,int val){
    // u->v = val
    int fu=find(u),fv=find(v);
    fa[fv]=fu;
    h[fv]=(-h[v]-val+h[u]+42)%3; // 加到正数再对3取模！
}

int main(){
    int n,k;scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)fa[i]=i;

    int cnt = 0;
    for(int i=0;i<k;i++){
        int a,u,v;
        scanf("%d%d%d",&a,&u,&v);
        if(u>n || v>n){// 编号不对，是假话
            cnt++;
            continue;
        }
        if(a==2 && u==v){
            cnt++; // 我吃我自己 是假话
            continue;
        }

        // 然后判断剩下的
        if(a==1){ 
            if(find(u)==find(v)){
                if(h[u]!=h[v])cnt++;
            }
            else unite(u,v,0); // 模的差值为 0
        }
        else{ 
            if(find(u)==find(v)){
                if((h[u]-h[v]+42)%3!=2)cnt++;
            }
            else unite(u,v,2); // 模的差值为 2
        }
    }
    printf("%d\n",cnt);
    return 0;
}

维护不等式关系

模板

（差分约束）给定 nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n，mm 组关系。每组关系形如 xi−xj≤dx_i-x_j\le d。请求出是否存在一组合法解。

解法

我们可以把每个变量 xix_i 看做图中的一个结点，对于每个约束条件 xi−xj≤ckx_i-x_j\le c_k ，从结点 jj 向结点 ii 连一条长度为 ckc_k 的有向边。

设 dist0=0dist_0=0 并向每一个点连一条权重为 00 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，xi=distix_i=dist_i 为该差分约束系统的一组解（证明略）。其余解都是该组解加上一个常数。[1]

习题

[洛谷P1993] 小K的农场

对于 xa−xb≥cx_a-x_b\ge c，转化为 xb−xa≤−cx_b-x_a\le -c；对于 xa−xb≤cx_a-x_b\le c，无需转化；对于 xa=xbx_a=x_b，转化为 xa−xb≤0x_a-x_b\le 0 且 xb−xa≤0x_b-x_a\le 0。这样转化显然与原命题等价，因此我们就转化为了模板问题。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

const int N = 5e3+5;

vector<pair<int,int>> G[N];
int d[N]; // 最短路距离
int cnt[N]; // 被松弛了几次？
bool inqueue[N];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x;scanf("%d",&x);

        // 转化为差分约束
        if(x==1){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            G[a].push_back({b,-c});
        }
        else if(x==2){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            G[b].push_back({a,c});
        }
        else{
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back({b,0});
            G[b].push_back({a,0});
        }
    }

    for(int i=1;i<=n;i++){
        G[0].push_back({i,0}); // 从超级源点0往每个节点连一条权值为0的边
    }

    // 用SPFA求是否存在负环
    memset(d,0x3f,sizeof(d));
    d[0]=0;
    queue<int> q;
    q.push(0);inqueue[0]=1;

    while(q.size()){
        int u=q.front();q.pop();inqueue[u]=0;
        for(auto [v,w]:G[u]){
            if(d[v]>d[u]+w){ // 可以松弛
                d[v]=d[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n+1){ // 有负环！
                    puts("No");
                    return 0;
                }
                if(!inqueue[v]){
                    inqueue[v]=1;
                    q.push(v);
                }
            }
        }
    }
    puts("Yes");
    return 0;
}

[1]. OI Wiki - 差分约束