526互联

CF1850H The Third Letter

发布时间 2023-08-15 19:10:42作者: -白简-

题目大意

\(n\) 个士兵站队，给出 \(m\) 个限制，要求士兵 \(b\) 站在士兵 \(a\) 前面距离为 \(d\) 的位置，可以有多个士兵站在同一个位置。询问给定限制下是否存在合法的列队方案。

思路

我们考虑把互相有直接或间接限制的点看作一棵树，加入到树中的结点是受到限制的。

最开始的状况没有限制，我们考虑逐个加入限制。最开始是一片森林，每棵树中只有一个结点，感觉很像并查集。

对于每个结点，我们维护它与自己祖先之间的相对距离，记录一个 pos。并查集合并时，我们只需要更改它祖先的 pos。

关于判无解，只需要考虑两个结点是否在同一个集合中以及距离是否与集合中的限制相等。

其他的就是普通的带权并查集操作。

记得开 long long。

Code

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int N = 200500;
 
int n,m;
 
struct Limits{
    int a,b;
    long long d;
}t[N];
 
long long pos[N];
int fa[N],size[N];
 
class DSU{
public:
    int Find(int x) {
        if(fa[x] == x)
            return x;
        int tmp = Find(fa[x]);
        pos[x] += pos[fa[x]];
        fa[x] = tmp;
        return Find(fa[x]);
    }
 
    void Union(int x,int y,long long dis) {
        int fx = Find(x);
        int fy = Find(y);
 
        if(fx == fy)
            return ;
        
        fa[fy] = fx;
 
        pos[fy] = pos[x] - dis - pos[y];
    }
 
    bool Check(int x,int y,long long dis) {
        if(Find(x) == Find(y)) 
            return pos[x] - pos[y] != dis;
        
        return 0;
    }
}dsu;
 
signed main() {
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i = 1;i <= n; i++)
            fa[i] = i;
 
        for(int i = 1,u,v,w;i <= m; i++) {
            cin >> u >> v >> w;
 
            t[i].a = u;
            t[i].b = v;
            t[i].d = w;
        }
 
        bool flag = 0;
        for(int i = 1;i <= m; i++) {
            if(dsu.Check(t[i].a,t[i].b,t[i].d)) {
                cout << "NO\n";
                flag = 1;
                break;
            }
 
            dsu.Union(t[i].a,t[i].b,t[i].d);
        }
        if(!flag)
            cout << "YES\n";
        for(int i = 1;i <= n; i++)
            pos[i] = 0;
    }
    return 0;
}