本文主要是介绍[bzoj4690][带权并查集]Never Wait for Weights,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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
Sample Output
1
-1
UNKNOWN
100
200
-50
题解
转化确实挺好想的吧,不过一开始想复杂了想直接搞就想到LCT启发式合并去了。。
直接上带权并查集
设g[i]表示i比他的连通块根轻多少,然后瞎做
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int g[110000],fa[110000];
int findfa(int x)
{if(fa[x]!=x){int k=findfa(fa[x]);g[x]+=g[fa[x]];fa[x]=k;}return fa[x];
}
int n,m;
char ch[10];
int main()
{while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)break;for(int i=1;i<=n;i++)fa[i]=i,g[i]=0;while(m--){int u,v,op;scanf("%s%d%d",ch+1,&u,&v);if(ch[1]=='?'){int p=findfa(u),q=findfa(v);if(p!=q)printf("UNKNOWN\n");else printf("%d\n",g[u]-g[v]);}else{scanf("%d",&op);int p=findfa(u),q=findfa(v);if(p!=q){fa[p]=q;g[p]=g[v]+op-g[u];}}}}return 0;
}
这篇关于[bzoj4690][带权并查集]Never Wait for Weights的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!