11分wa求助
查看原帖
11分wa求助
1122530
elpsconr楼主2024/9/3 21:06

不知道为啥wa了,感觉写的没问题

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define tul tuple<int,int,int>
#define all(x) x.begin(),x.end()
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define lc rt<<1
#define rc rt<<1|1
const int N=3e5+6,yyx=998244353;
int n,m,a[N],b[N],d[N];
struct DSU{
    vector<int> fa,sz,d;
    DSU(int n){
      fa.resize(n+1);
      sz.resize(n+1,1);
      d.resize(n+1,0);
      iota(fa.begin(),fa.end(),0);
    }
    int find(int x){
      if(x==fa[x]) return x;
      int px=find(fa[x]);
      d[x]+=d[fa[x]];
      fa[x]=px;
      return fa[x];
    }
    bool same(int x,int y){
      int px=find(x),py=find(y);
      return px==py;
    }
    bool same(int x,int y,int k){
      return d[x]-d[y]==k;
    }
    void merge(int x,int y,int k){
        int px=find(x),py=find(y);
        if(px!=py){
          fa[px]=py;
          sz[py]+=sz[px];
          d[px]=k+d[y]-d[x];
        }
    }
    void merge(int x,int y){
        int px=find(x),py=find(y);
        if(px!=py){
          fa[px]=py;
          sz[py]+=sz[px];
        }
    }
    int size(int x){
      return sz[find(x)];
    }
};
inline void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;++i){
    cin>>a[i]>>b[i]>>d[i];
  }
  DSU dsu(n+1);
  int ok=1;
  for(int i=1;i<=m;++i){
    if(!ok) continue;
    if(!dsu.same(a[i],b[i])){
        dsu.merge(a[i],b[i],d[i]);
    }
    else{
        if(!dsu.same(a[i],b[i],d[i])){
          ok=0;
          break;
        }
    }
  }
  if(ok) cout<<"false"<<endl;
  else cout<<"true"<<endl;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  //freopen("D://321//in.txt","r",stdin);
  //freopen("D://321//out.txt","w",stdout);
  int _=1;
  cin>>_;
  while(_--)
  solve();
  return 0;
}
2024/9/3 21:06
加载中...