還記得海鞘嗎?對,就是上次那隻視財如命的烏龜。
海鞘的藏寶窟群越蓋越大,到最後已經由原本的樹狀變成複雜的網狀結構。
他的藏寶窟群由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);
表示已經輸出所有路徑,並會幫你結束程式。
==============================
本題無須輸入,請依序使用Init()、GetVE()、E次Get()來讀取藏寶窟的資訊。
保證V ≤ 1,000,E ≤ 50,000
本題無須輸出,請依照上述方法連續輸出所有人的巡邏路徑。
你可以在這裡載到一個測試用的.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
原TIOJ1692 / ABCLS Contest, Problem B
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 16 |
2 | 1 | 16 |
3 | 2 | 16 |
4 | 3 | 16 |
5 | 4 | 16 |
6 | 5 | 20 |