首页 > 代码库 > 数石子RQNOJ 并查集
数石子RQNOJ 并查集
巧妙的并查集。对于 i,j,k 可以表示 d[j] - d[i-1]= k;若i,j有公共祖先 则可以求出 分别到 祖先的距离,差值就是答案。
#include<stdio.h>#include<iostream>#include<string.h>#include<queue>#include<stack>#include<list>#include<stdlib.h>#include<algorithm>#include<vector>#include<map>#include<set>#include <fstream>using namespace std;const int Maxn=5555;int father[Maxn];int dist[Maxn];int getfather(int x){ //cout<<x<<endl;system("pause"); if(x==father[x]) return x; int t=getfather(father[x]); dist[x]+=dist[father[x]]; return father[x]=t;}int main(){ int n,m,k; int a,b,c; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++) father[i]=i; memset(dist,0,sizeof(dist)); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); int fa=getfather(a-1);int fb=getfather(b); if(fa==fb) continue; father[fa]=fb; dist[fa]=c+dist[b]-dist[a-1]; } for(int i=0;i<k;i++){ scanf("%d%d",&a,&b); int fa=getfather(a-1);int fb=getfather(b); if(fa!=fb) { printf("UNKNOWN\n"); } else{ printf("%d\n",dist[a-1]-dist[b]); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。