[問題] 關於acm302(已解決)

看板C_and_CPP作者 (我不是阿見)時間15年前 (2010/04/24 18:44), 編輯推噓4(4推 0噓 14→)
留言18則, 4人參與, 最新討論串1/1
遇到的問題： (題意請描述清楚) 問題302是這樣的 V個點 E條edge(無方向) 輸出完成尤拉迴圈的edge編號順序(越前頭的編號越小越好) 無法成為尤拉迴圈的話就輸出Round trip does not exist. 感謝各位大大的幫忙，終於知道原來是我題意搞錯了 只是改正後上傳變成TE了Orz 我改成使用陣列，之前的問題也考慮進去了，結果卻WA... 我果然沒有寫程式的天分嗎(龜牆角... (0<V<=44 0<E<=1995) 希望得到的正確結果： AC 程式跑出來的錯誤結果： WA 開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux) dev C++4.9.9.2 有問題的code： (請善用置底文標色功能) http://codepad.org/RyBdpRtZ 補充說明： 修改後，code精簡一半...但作法一樣 依開始先判斷是否所有node的degree皆為偶數，是才繼續計算 在跑尤拉迴圈時先選擇編號小的路徑，並移除該路徑 變數說明: top=stack目前使用 check=每個node的degree M[a][b]: a表示node的編號 b表示路徑編號 若M[A][3]=1 則路徑3其中一端點為A 若M[B][5]=2 則路徑5為B自身的迴圈 感謝各位大大的閱讀!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.42.194
→
04/24 19:20, , 1F
現在UVa網站維修中，等會看有沒機會修好
04/24 19:20, 1F
→
04/24 19:31, , 2F
對了，想請教這是求尤拉路徑嗎？如果是的話，
04/24 19:31, 2F
→
04/24 19:32, , 3F
1.全為偶連通 2.剛好兩個奇連通，其他是偶連通
04/24 19:32, 3F
→
04/24 19:32, , 4F
都會有解。系統修好了我try try看。
04/24 19:32, 4F
→
04/24 19:37, , 5F
是迴圈 起點要跟終點相同
04/24 19:37, 5F
→
04/24 19:39, , 6F
嗯嗯，好的，那應該方向是對的。
04/24 19:39, 6F
→
04/24 19:41, , 7F
先感謝b大熱情幫忙
04/24 19:41, 7F
推
04/24 22:39, , 8F
判斷完degree後, 有再判斷圖是否為connected嗎 ?
04/24 22:39, 8F
推
04/24 23:20, , 9F
圖一定要是connected 才下去找尤拉迴圈
04/24 23:20, 9F
→
04/24 23:20, , 10F
試考慮一個圖有兩個components, 各有一個尤拉迴圈
04/24 23:20, 10F
→
04/24 23:20, , 11F
只判斷degree就錯了
04/24 23:20, 11F
→
04/25 00:18, , 12F
阿...真所謂一與點醒夢中人..感謝w大 我試試
04/25 00:18, 12F
→
04/25 00:36, , 13F
測資似乎一定是connected 因為我用uvatoolkit測試的結果
04/25 00:36, 13F
→
04/25 00:37, , 14F
他似乎只要以1為起點把與一相連的點能跑出尤拉迴圈即可
04/25 00:37, 14F
推
04/25 02:17, , 15F
這題英文很機車XD 起點是第一行input中較小的那個數字
04/25 02:17, 15F
→
04/25 02:17, , 16F
不一定是1
04/25 02:17, 16F
推
04/25 02:34, , 17F
同樓上
04/25 02:34, 17F
→
04/25 03:01, , 18F
我剛剛也發我錯在起點都設為1 結果改正後變成TE= =
04/25 03:01, 18F
※ 編輯: ccs5271 來自: 123.204.42.194 (04/25 03:13)
‣ 更多 ccs5271 的文章
文章代碼(AID): #1BqikN3K (C_and_CPP)