首页 > 代码库 > 【BZOJ-4690】Never Wait For Weights 带权并查集
【BZOJ-4690】Never Wait For Weights 带权并查集
4690: Never Wait for Weights
Time Limit: 15 Sec Memory Limit: 256 MBSubmit: 88 Solved: 41
[Submit][Status][Discuss]
Description
在实验室中,Nathan Wada作为助手的职责是测定两个样品的重量差异。当样品的差异很小时,使用天平能比使用弹簧秤得到更精确的结果,所以他只使用天平来测得一些样品的重量差。他偶尔会被询问一些样品的重量差,而他能否回答这些问题取决于在回答相应问题时他已经得到的测量结果。由于他所在处理的测量数据是巨大的,所以他希望你能写个程序帮他处理数据和回答问题。
Input
输入包含多组测试数据。每组数据第一行包含两个整数 N 和 M ,其中 N 表示样品的数量,样品从 1 到 N 标号,满足 2≤N≤100000 。
接下来 M 行,每行包括一个测量结果或者询问,按时间顺序给出,满足 1≤M≤100000 。
一个测量结果被格式化为 ! a b w ,表示第 a 个样品比第 b 个样品轻 w 个单位重量满足 a≠b,0≤w≤1000000 ,且任意的测试结果互不矛盾。
一个询问被格式化为 ? a b ,表示询问第 a 个样品比第 b 个样品轻多少个单位重量,满足 a≠b 。
输入以两个零作为结束。
Output
对于每个询问输出一行,如果能回答问题,则输出问题的答案,你可以认为答案的绝对值不超过 1000000
否则输出 UNKNOWN ,表示不能回答问题。
Sample Input
2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0
Sample Output
1
-1
UNKNOWN
100
200
-50
-1
UNKNOWN
100
200
-50
HINT
Source
鸣谢Tangjz提供试题
Solution
典型的思博题了啊
随便写个带权并查集,delta[i]记录到集合的代表元素的差值,然后就可以了
Code
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}#define MAXN 100010int N,M;int fa[MAXN],delta[MAXN];inline void Init() {for (int i=1; i<=N; i++) fa[i]=i,delta[i]=0;}inline int F(int x) {if (x==fa[x]) return x; int Fa=F(fa[x]); delta[x]+=delta[fa[x]]; return fa[x]=Fa;}inline void Merge(int x,int y,int d){ int Fx=F(x),Fy=F(y); if (Fx==Fy) return; int Fa=fa[x]; fa[Fa]=fa[y]; delta[Fa]=delta[y]+d-delta[x];}int main(){ while (scanf("%d%d",&N,&M)) { if (!N && !M) break; Init(); while (M--) { char opt[5]; scanf("%s",opt); int u=read(),v=read(),d; if (opt[0]==‘!‘) d=read(),Merge(u,v,d); if (opt[0]==‘?‘) if (F(u)!=F(v)) puts("UNKNOWN"); else printf("%d\n",delta[u]-delta[v]); } } return 0;}
这思博题我还能WA?
然而因为打的太快了...手误了一个地方....然后真的WA了....
暗言术:WA!
【BZOJ-4690】Never Wait For Weights 带权并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。