首页 > 代码库 > 数石子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;}