題目描述：
有三個物種 A，B，C，其中A可以吃B，B可以吃C，C可以吃A。 給出N(N<50000)個生物，給出X(X<100000)個定論，請問X個定論中有多少是謊話？
吐槽：
剛做完GCJ想到"今天"還沒有寫題解，于是就堅持捉完了這個水題。可惜還是過了0點.... 殘念啊
算法分析：
除了正常的并查集需要記錄每個節點的父親以外，我們還要維護該點與父親的關系(吃? 被吃? 等價？)
判斷的時候，如果i和j屬于同一集合，這就不用說了....
如果parent[i]!=parent[j]，那么就將i和j所在集合合并，我的做法是將i的代表的父親直接變為j。
維護i與新的父親j的關系只需要改變一下parent[i]與j的關系值就好了(i本身的關系值不必改變，因為i和parent[i]的關系在那里)。
至于parent[i]和j的關系如何通過i和j的關系來確定.... 額 自己在紙上畫一畫就有了...
路徑壓縮也要維護的(很重要)... 應該很簡單吧.....
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define re1(i,n) for(int i=1;i<=n;i++)
5 int P[50001][2];
6 int find(
int x){
7 int u = P[x][0];
8 if(u==x)
return x;
9 P[x][0]=find(u);
10 P[x][1]=(P[u][1] + P[x][1])%3;
11 return P[x][0];
12 }
13 int main(){
14 int n,k;
15 scanf("%d%d",&n,&k);
16 int c,a,b,ans=0;
17 re1(i,n) P[i][0] = i, P[i][1] = 0;
18 re1(i,k){
19 scanf("%d%d%d",&c,&a,&b);
20 if(a > n || b>n) { ans ++;
continue;}
21 if(c == 1) {
22 if(find(a)!=find(b)){
23 int u = P[a][0];
24 P[u][0] = b;
25 P[u][1] = (3-P[a][1])%3;
26 }
27 else if(P[a][1]!=P[b][1]){
28 ans ++;
29 }
30 }
31 else {
32 if(a == b) ans ++;
33 else if(find(a)!=find(b)){
34 int u = P[a][0];
35 P[u][0] = b;
36 P[u][1] = P[a][1]==2?2:P[a][1]^1;
37 }
38 else if((P[a][1]-P[b][1]+3) % 3 != 1) ans++;
39 }
40 // re1(i,n) cout<<P[i][0]<<" "<<P[i][1]<<" ";cout<<endl;
41 }
42 cout<<ans<<endl;
43 44 }
45 posted on 2012-05-06 02:28
西月弦 閱讀(391)
評論(7) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目