1692 . Problem B 道路巡邏問題 [Interactive]
TopCoder
Tags
Description
還記得海鞘嗎？對，就是上次那隻視財如命的烏龜。
海鞘的藏寶窟群越蓋越大，到最後已經由原本的樹狀變成複雜的網狀結構。
他的藏寶窟群由V個藏寶窟組成、雙向連通的通道則有E條。
他希望安排一些守衛來巡邏每條道路。巡邏的龜則是這樣的：
每隻警衛會被安排一條巡邏路徑，每天早上三點會從路徑起點端巡邏到終點端、下午三點會從終點端回到起點。
海鞘希望每條通道都會恰好被巡邏到一次。
海鞘是數學一哥，他知道奇點有0個或2個時只需要一位警衛，超過2就不行了。
但是他也是節儉一哥，他希望僱用最少位警衛達成巡邏所有通道的任務。
海鞘找到了你，假設你幫他安排一組巡邏方案他就會給你109枚烏龜幣作為報酬。
==============================
本題不需進行輸入輸出，請先引入#include "lib1692.h"並使用以下函式完成任務：
＊void Init(void);
在你作任何操作前請先呼叫這個函式。
＊void GetVE(int&V, int&E);
只能呼叫一次，V表示藏寶窟的數量、E表示通道的數量。
＊void Get(int&V1, int&V2);
能呼叫E次，第i次呼叫代表通道i是連接V1和V2。
＊void ReportVst(int st);
＊void ReportVed(int ed);
＊void ReportE(int n);
用來回報一條路徑依序經過的通道編號。例如有一條1→2→4→2→5的巡邏路徑，
而通道1連接1和2、通道2連接4和2、通道3連接2和5、通道4連接2和4，
那麼你可以這樣回報：
ReportVst(1); //代表巡邏起點為房間1
ReportE(1); //代表走過通道1，走到房間2
ReportE(2); //代表走過通道2，走到房間4
ReportE(4); //代表走過通道4，走到房間2
ReportE(3); //代表走過通道3，走到房間5
ReportVed(5); //代表巡邏結束在房間5
＊void Final(void);
表示已經輸出所有路徑，並會幫你結束程式。
==============================
Input Format
本題無須輸入，請依序使用Init()、GetVE()、E次Get()來讀取藏寶窟的資訊。
保證V ≤ 1,000，E ≤ 50,000
Output Format
本題無須輸出，請依照上述方法連續輸出所有人的巡邏路徑。
Hints
你可以在這裡載到一個測試用的.h檔。
例如對於以下藏寶窟結構：
5 4 //代表V=5，E=4，以下E行為編號1~4的通道兩端房間編號。
1 2
1 2
3 5
1 4
以下會是一個能通過此筆測試的程式碼：
#include <cstdio>
#include "lib1692.h"
int edge[50010][2], V, E;
int main() {
Init();
GetVE(V, E);
for(int i=0; i<E; i++) Get(edge[i][0], edge[i][1]);
ReportVst(1);
ReportE(1);
ReportE(2);
ReportE(4);
ReportVed(4);
ReportVst(3);
ReportE(3);
ReportVed(5);
Final();
}
(*)詳情見建國中學2010年校內模擬賽Contest 4 prob 1 / Contest 7 prob 2
Problem Source
原TIOJ1692 / ABCLS Contest, Problem B
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |