首页 > 代码库 > [HNOI2005]狡猾的商人

[HNOI2005]狡猾的商人

2024-09-29 19:25:02   214人阅读

OJ题号：BZOJ1202、洛谷2294

思路：加权并查集。

每次将给出的区间[x-1,y]对应的v与w[y]-w[x]比较，如果与已知条件冲突则为假账单。如果条件未知加入并查集中，并维护一个类似于前缀和的东西w，对于每个联通块，w[i]表示从anc[i]到i的账目。

 1 #include<cstdio> 2 #include<cstring> 3 const int N=100; 4 class UnionFindSet { 5     private: 6         int anc[N],w[N]; 7     public: 8         void reset(const int n) { 9             memset(w,0,sizeof w);10             for(int i=0;i<=n;i++) anc[i]=i;11         }12         void Union(const int x,const int y,const int v) {13             int p=Find(x),q=Find(y);14             anc[p]=q;15             w[p]=w[y]-w[x]-v;16         }17         int Find(const int x) {18             if(x==anc[x]) return x;19             int t=Find(anc[x]);20             w[x]+=w[anc[x]];21             return anc[x]=t;22         }23         int Weight(const int y,const int x) {24             return w[y]-w[x];25         }26 };27 UnionFindSet s;28 int main() {29     int w;30     scanf("%d",&w);31     while(w--) {32         int n,m;33         scanf("%d%d",&n,&m);34         s.reset(n);35         bool isfalse=false;36         while(m--) {37             int x,y,v;38             scanf("%d%d%d",&x,&y,&v);39             if(isfalse) continue;40             if(s.Find(--x)==s.Find(y)) {41                 if(s.Weight(y,x)!=v) {42                     puts("false");43                     isfalse=true;44                 }45             }46             else {47                 s.Union(x,y,v);48             }49         }50         if(!isfalse) puts("true");51     }52     return 0;53 }

 

[HNOI2005]狡猾的商人


联系
我们