hihoCoder#1121
剛開始學習C語言，準備在做hiho的題目的過程中來學習，在此進行記錄，如果代碼中有錯誤或者不當的地方還請指正。
描述
大家好，我是小Hi和小Ho的小伙伴Nettle，從這個星期開始由我來完成我們的Weekly。
新年回家，又到了一年一度大齡剩男剩女的相親時間。Nettle去姑姑家玩的時候看到了一張姑姑寫的相親情況表，上面都是姑姑介紹相親的剩男剩女們。每行有2個名字，表示這兩個人有一場相親。由于姑姑年齡比較大了記性不是太好，加上相親的人很多，所以姑姑一時也想不起來其中有些人的性別。因此她拜托我檢查一下相親表里面有沒有錯誤的記錄，即是否把兩個同性安排了相親。
OK，讓我們愉快的暴力搜索吧！
才怪咧。
對于拿到的相親情況表，我們不妨將其轉化成一個圖。將每一個人作為一個點(編號1..N)，若兩個人之間有一場相親，則在對應的點之間連接一條無向邊。(如下圖)
因為相親總是在男女之間進行的，所以每一條邊的兩邊對應的人總是不同性別。假設表示男性的節點染成白色，女性的節點染色黑色。對于得到的無向圖來說，即每一條邊的兩端一定是一白一黑。如果存在一條邊兩端同為白色或者黑色，則表示這一條邊所表示的記錄有誤。
由于我們并不知道每個人的性別，我們的問題就轉化為判定是否存在一個合理的染色方案，使得我們所建立的無向圖滿足每一條邊兩端的頂點顏色都不相同。
那么，我們不妨將所有的點初始為未染色的狀態。隨機選擇一個點，將其染成白色。再以它為起點，將所有相鄰的點染成黑色。再以這些黑色的點為起點，將所有與其相鄰未染色的點染成白色。不斷重復直到整個圖都染色完成。(如下圖)
在染色的過程中，我們應該怎樣發現錯誤的記錄呢？相信你一定發現了吧。對于一個已經染色的點，如果存在一個與它相鄰的已染色點和它的顏色相同，那么就一定存在一條錯誤的記錄。(如上圖的4，5節點)
到此我們就得到了整個圖的算法：
- 選取一個未染色的點u進行染色
- 遍歷u的相鄰節點v：若v未染色，則染色成與u不同的顏色，并對v重復第2步；若v已經染色，如果 u和v顏色相同，判定不可行退出遍歷。
- 若所有節點均已染色，則判定可行。
接下來就動手寫寫吧！
輸入
第1行：1個正整數T(1≤T≤10)
接下來T組數據，每組數據按照以下格式給出：
第1行：2個正整數N,M(1≤N≤10,000，1≤M≤40,000)
第2..M+1行：每行兩個整數u,v表示u和v之間有一條邊
輸出
第1..T行：第i行表示第i組數據是否有誤。如果是正確的數據輸出”Correct”，否則輸出”Wrong”
- 樣例輸入
-
2 5 5 1 2 1 3 3 4 5 2 1 5 5 5 1 2 1 3 3 4 5 2 3 5
樣例輸出
Wrong Correct
解決思路
使用一個結構體記錄一個人的所有信息{性別，約會數量，約會對象}，其中約會對象通過指向指針數組的指針來實現。
這樣的結構體可以在讀取數據的過程中把所有的信息全部存儲下來。
在進行性別判斷時有一種情況需要考慮，可能存在幾個人是單獨成一組的，就是說這幾個是獨立于其他人的他們只在
他們自己內部之間有約會，而不與其他人有約會。這時如果你一開始選取的點的邏輯中不包含他們，那么按照題目提示的
方法是無法考慮到他們的。我采用的方法是，在第一個循環中為每個沒有性別的人都賦予性別，但是賦予性別后用遞推把
所有與他存在邏輯關系的人的性別全部確定。這樣做的結果是如果他們所有人都互相之間存在邏輯關聯的話，當我給第一
個人一個性別并遞推他的關系時就給所有人都賦予了性別，當存在前面所說的特殊情況時，我們的第一層循環也會找到這
些邏輯上獨立的人，將他們的關系遞推出來。
但是現在在我編出的程序中存在問題，我的運行結果是RE，我暫時還沒有找到錯誤的地方，希望看到的人給以幫助。
#include<stdio.h> #define OPPSEX(sex) sex==1?2:1 typedef struct PEOPLE { int Sex; //sex 無性別0，男性1，女性2； int PDateNum; //約會數量 struct PEOPLE **DataToOther; //指向約會對象的數組的指針 }people; //正確返回0，錯誤返回1 int JudgeDateROW(people *Group,int PeoNum,int DateNum) { int i; for(i=0;i<PeoNum;i++) { if(Group[i+1].Sex==0) { Group[i+1].Sex=1; if(derive_others(&Group[i+1])==1) return 1; } } return 0; } //正確返回0，錯誤返回1 int derive_others(people *Person) { int i; for(i=0;i<Person->PDateNum;i++) { if(Person->DataToOther[i]->Sex==0) Person->DataToOther[i]->Sex=OPPSEX(Person->Sex); else { if(Person->DataToOther[i]->Sex==Person->Sex) return 1; else return 0; } if(derive_others(Person->DataToOther[i])==1) return 1; } return 0; } int main(void) { int PeoNum,DateNum,GroupNum; int i,j,k; char *Answer[2]={"Correct","Wrong"}; //獲得數據量 scanf("%d",&GroupNum); int AnswerNum[GroupNum]; //獲取每組的數據，并得到分析結果 for(i=0;i<GroupNum;i++) { int person1,person2; //獲取人數和約會數 scanf("%d %d",&PeoNum,&DateNum); people *Group; //為這組人分配人數加一個人的內存，第零個忽略掉 Group=calloc(sizeof(people),PeoNum+1); size_t PDateSize=sizeof(people*)*5; //先為每個人分配5個約會的指針內存 for(j=1;j<=PeoNum;j++) Group[j].DataToOther=(people**)calloc(sizeof(people*),5); //讀取每組數據，并生成二分圖 for(j=0;j<DateNum;j++) { scanf("%d %d",&person1,&person2); //判斷是否需要分配更多的內存給約會指針 if((Group[person1].PDateNum+1)%5==0) Group[person1].DataToOther=(people**)realloc(Group[person1].DataToOther,\ sizeof(people*)*(Group[person1].PDateNum+6)); if((Group[person2].PDateNum+1)%5==0) Group[person2].DataToOther=(people**)realloc(Group[person2].DataToOther,\ sizeof(people*)*(Group[person2].PDateNum+6)); //記錄互相的約會，并將約會數量加一 *(Group[person1].DataToOther+Group[person1].PDateNum)=&Group[person2]; Group[person2].DataToOther[Group[person2].PDateNum]=&Group[person1]; Group[person1].PDateNum++; Group[person2].PDateNum++; } //判斷分組是否正確 AnswerNum[i]=JudgeDateROW(Group,PeoNum,DateNum); //釋放本組分配的內存 for(j=1;j<=PeoNum;j++) free(*Group[j].DataToOther); free(Group); } //輸出分析結果 for(i=0;i<GroupNum;i++) printf("%s\n",Answer[AnswerNum[i]]); return 0; }
浙公網安備 33010602011771號