回分類題庫
d177: 2010 程式達人 H - 找出守密人問題
出處:

Difficulity : N/A
Accepted : 6 Times | Submit :71 Times | Clicks : 1384
Accepted : 3 Users | Submit : 5 Users | Accepted rate : 60%
Time Limit :20000 ms | Memory Limit : 99999 KBytes
題目加入時間 : 2010-05-16 19:46

Content :

猛哥是個業餘駭客,為了成為pro級的駭客,他必須侵入數個政府機關的Server,以證明他具備職業級的能力。就在今天,被指定要入侵的名單已經發布了,我們的任務就是得到這份名單進行保衛戰。

麻煩來了,猛哥是個極為嚴謹的人,為了不讓正義的一方知道他要入侵的Server地點,他將這份名單的每個Server都交給兩位他信任的守密人來保護,而這些守密人就形成了一個守密網路。

幸運的是,我們已經成功取得所有守密人的姓名。在時間有限的情況下,我們必須盡快找出一些守密人來得到Server的地點,並詢問出另一位守密人。我們採取的策略是先分析這個網路中這些守密人被任意兩個守密人之間的最短路徑經過的次數(Betweenness Centrality,以下簡稱BC),找出BC值前三名,並以其為出發點來進行破解。
BC的公式如下:

σxy代表從x點到y點的最短路徑數目。σxy (v)代表x到y的最短路徑中有經過v的次數。以下圖為例,黑色的點被任意兩點之間最短路徑經過的次數為9次,所以其BC值為9。

Input :

輸入會有多組資料,每組資料包含兩個部份:
1.    每組的第一行是一個正整數N ( N >= 3),代表這個守密網路總共有多少人。
2.    接下來M行每行各有兩個正整數p, q,數字間以一空白字元隔開。數字p, q代表守密人的編號(p != q; 0 <= p, q <= N-1),而此行代表兩人之間有守密關係(順序先後不代表方向性),並且同一段關係不會重複出現。每組資料最後一行為-1 -1代表此組資料結束。

例如:0 1,代表0號與1號守密人之間有互相守密關係,之後不會再出現0 1或1 0這筆資料。

範例輸入的兩筆資料請參考下圖:

Output :

對每組資料請輸出三行,依BC值大小排序,如果BC值相同則根據編號由小到大排。每行包含兩個數字a和b,以空白隔開。a代表守密人編號,b代表BC值(四捨五入到小數第一位)。

Sample Input :

4
2 0
2 3
0 3
1 3
-1 -1
5
1 0
4 1
4 3
2 4
0 4
0 3
1 2
-1 -1

Sample Output :

3 2.0
0 0.0
1 0.0
4 2.0
0 0.5
1 0.5

Hint :

送出數: 0  出題者小愛說很簡單

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
27833. henryokc (60 ms , 520KB)
39659. cp100701020 (76 ms , 518KB)
55896. ag100 (60 ms , 500KB)
55895. ag100 (60 ms , 500KB)
55898. ag100 (112 ms , 502KB)
56133. ag100 (136 ms , 61536KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡