Noi2001食物鏈-并查集 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 #include<cmath> 8 #include<vector> 9 #include<queue> 10 #include<set> 11 using namespace std; 12 int par[50001],dis[50001]; 13 void get_par(int v){ 14 if(par[v]!=v){ 15 get_par(par[v]); 16 dis[v]=(dis[par[v]]+dis[v])%3; 17 par[v]=par[par[v]]; 18 } 19 } 20 int get_kind(int x,int y){ 21 get_par(x); 22 get_par(y); 23 if(par[x]!=par[y]) return -1; 24 int a=(dis[y]-dis[x])%3; 25 if(a<0) a+=3; 26 return a; 27 } 28 void add_relation(int x,int y,int d){ 29 get_par(x); 30 int a=(-d+1-dis[x])%3; 31 if(a<0) a+=3; 32 dis[par[x]]=a; 33 par[par[x]]=y; 34 35 } 36 int main(){ 37 int n,k,ans=0; 38 scanf("%d%d",&n,&k); 39 for(int i=1;i<=n;i++) par[i]=i; 40 for(int i=0;i<k;i++){ 41 int d,x,y; 42 scanf("%d%d%d",&d,&x,&y); 43 if(x>n||y>n){ 44 ans++; 45 continue; 46 } 47 int a=get_kind(x,y); 48 if(a==-1) add_relation(x,y,d); 49 else if(a!=(d-1)) ans++; 50 } 51 printf("%d\n",ans); 52 return 0; 53 }

代碼第32、33行的順序一定不能反！要注意。

posted on 2017-03-06 19:26 學無止境-1980 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/rdzrdz-acm/p/6511508.html

總結

以上是生活随笔為你收集整理的Noi2001食物链-并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。