c402. 我討厭你
標籤 : 二分圖
通過比率 : 27人/34人 ( 79% ) [非即時]
評分方式:
Strictly

最近更新 : 2017-11-25 17:29

內容

  你收到了一個幫班級分組的任務,這位委託你的老師希望你能幫他帶領的班級分成兩組好讓他進行課程,並使兩組的「實力」總和差最小化(所以老師把學生都編了號,並給了你學生號碼1~n的實力),這樣才不會導致某一組的實力遠大於另一組。

  正當你覺得這個任務如此簡單,要開始直接著手分組時,一位收到消息的班內學生突然慌張地跑來告訴你,分組並不是如你所想得那麼簡單!

  因為班上的關係不是很融洽,所以只要把互相仇視對方的同學對分在一組,他們就會打起架來,這樣的後果顯然非常的糟糕。

  想像一下,如果你讓學生打起來,學生就會吵鬧,然後就會引發附近的居民抗議,抗議不成居民就會開始遊行,遊行如果很亂就會造成政府關切,然後會有警察跑去壓制,壓制失敗就會死一堆警察,然後就會被認為是恐怖攻擊,總統發布緊急命令,政府軍武力鎮壓,全國人民不得好死!

  太恐怖了,身為一個普通的工程師竟然能造成國家滅亡,想當然你不會希望這種事情發生,所以你和這位學生聯手把班上同學相處不融洽的關係表全部列了出來,看看能不能完美地達成這個任務。

  如果不行的話,就回絕這次任務(寧可放棄錢財也不要是自己造成國家滅亡!),如果可以的話,就盡量讓兩組的「實力」總和差最小,盡可能滿足老師的要求。

  快撰寫一個程式決定吧!

輸入說明

首行輸入有兩個數字n、m, 代表班上有n位學生,且你們收集到了m組不融洽關係。

再來一行有n個數字以空格隔開,第i個數字代表編號i學生的實力。

接下來有m行,每行有兩個數字a、b,代表你不能把編號a和b的學生分在同一組(1≦a,b≦n)。

不會有a=b的關係出現。

輸出說明

若你發現不能讓所有互不融洽的同學分在不同組的話,輸出"Bye Bye Cruel World!"(不含引號)並換行。

若可以,請輸出兩個數字X、Y由小到大,代表這兩組個別的實力總和。

範例輸入 #1
8 12
1 1 1 1 1 1 1 1
1 2
5 4
3 2
8 7
6 5
6 1
8 3
3 4
2 5
7 6
4 7
1 8
範例輸出 #1
4 4
測資資訊:
記憶體限制: 512 MB
提示 :

30%的測資,任意的兩個人,都能把不融洽的關係當成橋梁互相連通。

60%的測資,絕對有辦法把這些學生分成不超過22組,讓每組內任意的兩個人,都能把不融洽的關係當成橋梁互相連通。

80%的測資,每個人的實力≦30

100%的測資,n≦3000,m≦1000000,每個人的實力≦2000,絕對有辦法把這些學生分成不超過100組,讓每組內任意的兩個人,都能把不融洽的關係當成橋梁互相連通。

 

測資好難生...QQ

標籤:
二分圖
出處:
[管理者: baluteshih (波路特石) ]

本題狀況 本題討論 排行

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