c426: pE 網路測試的難題
標籤 :
通過比率 : 75% (9 人 / 12 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-12-12 12:55

內容

骨幹網路是網際網路中重要的基礎設施。骨幹網路由多台伺服器組成,彼此間以高速網路連結;

其他電腦與裝置,則透過骨幹網路連線到網際網路上。

機關、學校、公司與資料中心也經常透過建置自己的骨幹網路, 來提供內部與外部的網路服務。
骨幹網路中的伺服器通常透過不只一條的實體連線相互連結,提供妥善的分流與備援。

確保每條連線的品質,就是確保骨幹網路穩定的基本方法,

然而有效率的測試所有連線可能是相當艱鉅的任務。

假設每條直接連線都是雙向的,考慮以下的簡單方法:
「每台伺服器都有自己的唯一 ID 識別碼。每台伺服器查看所有與自己直接連線的伺
服器 ID,如對方的 ID 比自己的 ID 大,則 ID 較小的伺服器負責對此連線進行測試。」

如此一來,每條直接連線都會被測試恰好一次。然而 ID 較小又擁有較多直接連線
的伺服器可能得負擔較多的測試, 會導致測試工作的分配並不是很平均。

我們能靠重新分配伺服器的 ID,以減少(最小化)伺服器最大的負擔。

例如以下這張網路:

 1

需要的測試如下:
伺服器 0 → {1, 4, 5}
伺服器 1 → {2, 5}
伺服器 2 → {3, 5}
伺服器 3 → {4}
伺服器 4 → {5,6}
伺服器 5 → {}
伺服器 6 → {}
伺服器 0 最多需要 3 次測試。

 

若 ID 經過適當地重新分配後:

 2

需要的測試如下:
伺服器 0 → {4}
伺服器 1 → {2, 4}
伺服器 2 → {3, 5}
伺服器 3 → {5, 6}
伺服器 4 → {5,6}
伺服器 5 → {6}
伺服器 6 → {}
伺服器 1,2,3,4 最多只需要 2 次測試。

 

可見適當的重新分配 ID,可以使最多的連線測試次數減少。對於給定的網路關係
圖,請問重新分配 ID 後,每台伺服器最多連線測試次數可以減至多少?

輸入說明

輸入第一行為一個整數 T (T <= 10),以下包含 T 組測資。

每組測資的第一行有以空白分隔的兩個整數 N 與 E;

N 是伺服器的數量,E 表示直接連線的數量。往後有 E 行。

每行包含以空白分隔的兩個整數 u 與 v (0 <= u,v < N),表示伺服器 u與 v 之間有直接連線。

任一伺服器不會直接連線到自己,任兩伺服器間不會出現重複
的連線,但不保證任兩伺服器之間有連通。

輸出說明

每筆測資有一行輸出,輸出為空白分隔的兩個整數,分別代表重分配 ID 之前與
之後的最大的連線測試數量。

範例輸入
1
7 10
4 6
4 0
4 5
4 3
5 0
5 1
5 2
3 2
1 0
1 2
範例輸出
3 2
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (15%): 8.0s , <1M
不公開 測資點#1 (18%): 8.0s , <10M
不公開 測資點#2 (20%): 8.0s , <10M
不公開 測資點#3 (22%): 8.0s , <50M
不公開 測資點#4 (25%): 8.0s , <50M
提示 :

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組 15 分,N <= 100、E <= 500。
第二組 18 分,N <= 5,000、E <= 80,000。
第三組 20 分,N <= 50,000、E <= 200,000。
第四組 22 分,N <= 200,000、E <= 400,000。
第五組 25 分,N <= 500,000、E <= 800,000。

標籤:
出處:
104學年度全國資訊學科能力競賽 [編輯:
andy89923 (CTFang)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」