b233: TOI2009 第五題:謠言問題
Tags :
Accepted rate : 118人/172人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 01:16

Content
在一個小鎮中,該鎮上的居民間存在一些好友關係,這個小鎮的居民非常喜歡告訴別人他所獲得的消息,只要某人得知一個消息,他就會傳播給他所有的好友。此外,這個小鎮上有兩家超級市場:每日鮮超市及撰大前超市,兩家超市經常會爾虞我詐地相互競爭。
有一天,撰大前超市故意放出一個不利於每日鮮超市的消息給一位鎮民甲:說每日鮮超市賣的香瓜很難吃,每日鮮超市派遣在撰大前超市中的密探在第一時間得知這個消息。由於這個小鎮中的居民皆很
單純,只要聽到他的好友告訴他一個消息,他便會信以為真,並會傳播給他的好友;但是他若知道消息為誤傳,便不會再繼續傳播下去。
每日鮮超市為了使不利的消息傳播的範圍減小,在第一時間(假設甲還沒傳播消息出去)希望找到鎮民甲以外的一位鎮民乙,送他一籃香瓜,使得他就算聽到這個不利消息,也不會繼續傳播消息給他的好友。為了使這個謠言防堵的效果達到最好,必須慎選這位要贈送香瓜的鎮民乙,使得最後會獲知此不利消息的鎮民數達到最少。
舉例說明:鎮上有6個鎮民,鎮民編號從正整數1依序表示,而鎮民間的好友關係配對有(1,3), (3,4), (5,1), (2,6), (4,5), (6,3),及(5,3)。若鎮民甲為編號4的鎮民,並挑選編號6的鎮民為防堵對象,最後會獲知此不利消息的鎮民會有{1, 3, 4, 5, 6};挑選編號3的鎮民為防堵對象,最後會獲知此不利消息的鎮民只會有{1, 3, 4, 5},可達到最佳防堵效果。
現在每日鮮超市已握有鎮上的居民間存在的好友關係,給定將散播不利消息的鎮民甲,請你寫一個程式來找出要贈送香瓜的鎮民乙,以及防堵後會獲知此不利消息的鎮民數(包含鎮民甲及鎮民乙)。
Input

第一行為一正整數N (1<=N<=30000)及M (1<=M<=30000),以空白分開。其中N 表示鎮民數目,M 表示好友的鎮民配對數目。鎮民編號從正整數1 依序表示,例如有三個鎮民,則以鎮民1,鎮民2,
鎮民3來表示。
第二行起的M 行,每一行表示互為好友的鎮民配對。兩個鎮民編號間以空白分開,例如1 3 表示鎮民1和鎮民3互為好友,且出現的兩個編號間的大小順序性不一定。
第(M+2)行為一正整數K,表示鎮民甲的編號。

 

Output
請由螢幕輸出所找出鎮民乙的編號及最後會獲知此不利消息的鎮民數,兩者以空白隔開。若有多個符合條件的鎮民乙,請輸出編號最小者。
若不管有沒有選擇一個防堵消息傳播的鎮民乙,皆不會影響會獲知此不利消息的鎮民數,則只需輸出0。
Sample Input #1
6 7
1 3
3 4
5 1
2 6
4 5
6 3
5 3
4

5 4
1 2
1 3
2 3
4 5
1
Sample Output #1
3 4

0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
出處:
2009TOI研習營初選


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」