申請SAE

如果您發現本博客的外觀很難看,那是因為部分外觀文件被中國.國家.防火.牆屏.蔽所致!
請翻~牆!

我的Wordpress博客的地址: http://zhuyf.tk/
顯示具有 連通分量 標籤的文章。 顯示所有文章
顯示具有 連通分量 標籤的文章。 顯示所有文章

2012年2月27日 星期一

圖論練習題 摔跤 rassle 題解

【問題描述】
有兩種類型的職業摔跤手:一種是“好選手”,另一種是“差選手”。對於任何一對職業摔跤手來說,他們中可能有、也可能沒有比賽。假定有 n 位職業摔跤手,並且有一份清單,上面列出了 r 對參加比賽的摔跤手。寫一個程序,它能夠確定是否可能指定某些摔跤手為好選手,而將餘下的摔跤手指定為壞選手,從而使得每一場比賽都是在一個好選手與一個差選手之間進行。如果有可能做出這樣的指定,你的程序就應該將它產生出來,否則輸出無解“No”。
【輸入格式】
第1行有三個整數n,r。n是職業摔跤手的數量,r是比賽場數,它們之間用一個空格隔開。
接下來的r行,每行用兩個數V1,V2表示V1號摔跤手與V2號摔跤手比賽,選手從1開始編號。
【輸出格式】
輸出有兩行,第一行“好選手”的編號,第二行為“差選手”的編號,編號之間用一個空格隔開。
注意:為了鼓勵選手,使輸出答案唯一,請儘量多的將選手設為“好選手”,並且在可行條件下選擇編號小的選手為“好選手”。
如果無解,則輸出一行“No”。