1719 測資加強 已 rejudge
1779 . 房屋裁員(HOU13)
TopCoder
Tags
Description
過了幾年，因為你太過寵愛大鈞了，所以你的公司快被吃垮了。
為了讓公司繼續營業，身為董事長的你必頇做出對策。
雖然說把大鈞從窗外丟下去就沒事了，但你回想起之前跟他冒險的種種經歷，而不忍心下手。
於是，你就找了別人來動手。
於是，你決定對公司的員工進行裁員。
當然，裁員當然要根據每個員工對公司的貢獻來決定該解決掉誰，你要做的就是留下一些員工讓公司的總效益越大。
可是，人是有朋友的，有些人會因為朋友離開公司而辭職，這也必頇列入你的考量之中。
現在，給你每個員工留下的利益和每個員工間的關係，請求出你炒了一些員工之後，所留下最大的總利益。
Input Format
第一行有兩個數字 n 和 m，代表你公司有 n 個員工(編號為 1~n)，員工之間有 m 條關係。
n≤8000, m≤50000, -100000≤ci≤100000
接下來有 n 行，每行一個數字 ci 代表編號為 i 的人留在公司會造成多少收益；
再下來有 m 行，每行兩個數字 ai,bi 代表 ai 離開公司的話 bi 也會跟著離開公司。
Output Format
請輸出經過裁員後，公司剩下員工收益的最大總和。
Sample Input 1
4 3
-1
-3
5
2
1 2
1 3
2 4
-1
-3
5
2
1 2
1 3
2 4
Sample Output 1
4
Sample Input 2
4 4
-1
-3
5
2
1 2
1 3
2 4
2 3
-1
-3
5
2
1 2
1 3
2 4
2 3
Sample Output 2
3
Hints
第一筆範例說明： 留下 1、3。
第二筆範例說明： 全留。
後記
經過適當裁員之後,公司只剩下了你和大鈞,然而,這並不是結束,只是一 個開始。
(你為了裁員所請來的專家們)
Problem Source
原TIOJ1779 / 99建中校內資訊能力競賽(prob4)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |