首页 > 代码库 > 【BZOJ】【1202】【HNOI2005】狡猾的商人
【BZOJ】【1202】【HNOI2005】狡猾的商人
Orz iwtwiioi http://www.cnblogs.com/iwtwiioi/p/3887617.html
View Code
并查集+前缀和
啊……这题应该是水题吧？但是我这个大沙茶居然一天都没想出来……判负环，最短路什么的都试过，都跪了……
“如果我们能够根据之前的信息推出来第r天应该比第l-1天多多少钱，再跟这次的比较一下，就知道当前这条信息是不是假的了。”蒟蒻如是想到。
上面那个查询用前缀和可以很方便的实现~但是问题是每条信息，既相当于一个update操作（对于关系未知的情况），又想当于一个query操作（对于已知的），该怎么分开呢？而且，修改之间是会有传递性的，比如一开始我们知道了[1,3]和[6,7]这几天的信息，下一次又给了一条[4,5]的信息，我们就得把前后的全部合并……
等等……？合并？并查集？
嗯对的，既不是差分约束，也不是2-SAT，就是一个并查集……
对于一个“集合”，s[i]表示从第i天到fa[i]天的金钱差（前缀和哦~）。对于每条信息，如果l和r在同一个集合里，则直接利用前缀和求差分并跟val比较就行了，如果不在同一个集合里，则合并两个集合。自己手画一下看看是个什么情况吧。
1 /************************************************************** 2 Problem: 1202 3 User: ProgrammingApe 4 Language: C++ 5 Result: Accepted 6 Time:112 ms 7 Memory:808 kb 8 ****************************************************************/ 9 10 //BZOJ 120211 #include<cstdio>12 #include<cstdlib>13 #include<cstring>14 #include<algorithm>15 #define rep(i,n) for(int i=0;i<n;++i)16 #define F(i,j,n) for(int i=j;i<=n;++i)17 #define D(i,j,n) for(int i=j;i>=n;--i)18 #define pb push_back19 using namespace std;20 const int N=110,INF=~0u>>2;21 //#define debug22 void read(int &v){23 v=0; int s=1;24 char ch=getchar();25 while(ch<‘0‘ || ch>‘9‘){ if (ch==‘-‘) s=-1; ch=getchar();}26 while(ch>=‘0‘ && ch<=‘9‘) {v=v*10+ch-‘0‘; ch=getchar();}27 v*=s;28 }//Âèµ°£¬¾ÓÈ»ÊǶÁÈë³ö´íÁË29 30 int n,m,fa[N],s[N];31 int getfather(int x){32 if (fa[x]==x) return x;33 else {34 int p=fa[x];35 fa[x]=getfather(fa[x]);//这里一定要先递归修改了父亲，再修改自己36 s[x]+=s[p];37 return fa[x];38 }39 }40 int main(){41 // freopen("input.txt","r",stdin);42 int T;43 read(T);44 while(T--){45 read(n); read(m);46 F(i,0,n) fa[i]=i,s[i]=0;47 48 bool sign=1;49 int fx,fy,x,y,z;50 F(i,1,m){51 read(x),read(y),read(z); --x;52 fx=getfather(x); fy=getfather(y);53 if (fx!=fy){54 fa[fx]=fy;55 s[fx]=s[y]-s[x]+z;//这里是重点……好好想一想56 }57 else if (s[x]-s[y]!=z) {sign=0;break;}58 }59 if (sign) printf("true\n");60 else printf("false\n");61 62 }63 return 0;64 }
【BZOJ】【1202】【HNOI2005】狡猾的商人
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。