目录
BZOJ1202 狡猾的商人题解ｃｏｄｅ
BZOJ1202 狡猾的商人
[题目传送门][1]
题解
刚开始看题了之后第一反应就是差分约束，后来发现自己可能已经不怎么会差分约束，就准备放弃这道题目去看题解了，但是看到题解大部分都是并查集，才发现这题可能并不用差分约束（虽然差分约束也是可以做的）。我们用带权并查集维护每一个月收入，记\(c[i]\)表示第\(i\)个月与这个联通块中根节点的收入差。然后进行\(unite\)操作的时候，如果\(unite\)的两个节点已经在同一个联通块中了，就判断这两个节点\(x\)、\(y\)的当记录的收入是否与当前给出的\(w\)相同，如果不相同，则可以判断是假的了。注意路径压缩的时候需要同时更新\(c\)数组。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=1e3+500;
int T;
int n,m;
int fa[maxn],c[maxn];
bool f=0;
/*==================Define Area================*/
void init() {
for(int i=0;i<=n;i++) {
fa[i]=i;
c[i]=0;
}
f=0;
}
int find(int x) {
if(x==fa[x]) return x;
else {
int t=find(fa[x]);
c[x]+=c[fa[x]];
fa[x]=t;
}
return fa[x];
}
void unite(int x,int y,int w) {
int fx=find(x),fy=find(y);
if(fx==fy) {
if(c[x]-c[y]!=w) f=1;
return ;
}
c[fa[y]]=c[x]-c[y]-w;
fa[fa[y]]=fa[x];
return ;
}
int main() {
read(T);
while(T--) {
read(n);read(m);
init();
for(int i=1,x,y,z;i<=m;i++) {
read(x);read(y);read(z);
x--;
unite(x,y,z);
}
if(f) puts("false");
else puts("true");
}
}
[1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1202
转载于:https://www.cnblogs.com/Apocrypha/p/9433651.html
相关资源：JAVA上百实例源码以及开源项目
