2198 . 軍隊改（Army）
TopCoder
Tags
Description
糟了！國家有危機了！
今天軍營偵測到了敵人的來襲，在戰場的分佈圖恰好是由 $N$ 個島嶼（編號 $1\sim N$）和 $M$ 條雙向橋樑所連接的情況下，我國已經派出了 $A$ 團軍隊在各地待命，其中第 $i$ 團軍隊位於編號第 $x_i$ 的島嶼、兵力為 $c_i$ 人；而敵國則是派出了 $B$ 團軍隊在各地待命，其中第 $i$ 團軍隊位於編號第 $y_i$ 的島嶼、兵力為 $d_i$ 人。
對於這場戰爭，我國在兵力上有著十足的把握，絕對不會比對方少。但由於事出突然，軍營在攻打策略上有些混亂還無法好好整理出來，於是他們找上了身為資訊兵的你，希望你給出一套攻打敵國的策略來幫助國家取得勝利。
為了使得軍隊的移動流程更加清晰，他們希望你給出的策略是這樣的：你必須依序輸出若干組移動順序 $u_i,v_i,p_i$，代表你要讓我國在島嶼 $u_i$ 的軍隊分流 $p_i$ 的兵力出來移動到島嶼 $v_i$，該島嶼的軍隊在接受到事件後，便會開始進行移動。每次移動之後，島嶼 $u_i$ 的我國軍隊人數會減少 $p_i$ 人，且接下來可能會有三種事件發生：
- 島嶼 $v_i$ 上沒有任何軍隊：並不會有特殊的事情發生。
- 島嶼 $v_i$ 上有我國的軍隊 $q_i$ 人：該島嶼的我國軍隊人數增加至 $p_i+q_i$ 人。
- 島嶼 $v_i$ 上有敵國的軍隊 $q_i$ 人：若 $q_i>p_i$，則該島嶼的敵國軍隊人數減少至 $q_i-p_i$ 人；若 $q_i < p_i$，則該島嶼的敵國軍隊將會消失，並留下 $p_i-q_i$ 人的我國軍隊在該島嶼上；若 $q_i=p_i$，則該島嶼上將不會剩下任何一人。
軍營希望敵國的所有軍隊都被消滅得一乾二淨，並限制你至多只能執行 $Q_{upper}$ 次移動，你可以幫助軍營設計策略嗎？
Input Format
首行輸入五個整數 $N,M,A,B,Q_{upper}$，代表島嶼數量、橋樑數量、我國的軍隊團數、敵國的軍隊團數以及你最多可以執行的移動次數。
接下來 $M$ 行，每行兩個正整數 $u_i,v_i$，代表第 $i$ 條橋樑連接著編號 $u_i$ 和 $v_i$ 的兩座島嶼。
再接下來 $A$ 行，每行兩個正整數 $x_i,c_i$，代表我國第 $i$ 團軍隊位於編號 $x_i$ 的島嶼，兵力為 $c_i$。
最後接著 $B$ 行，每行兩個正整數 $y_i,d_i$，代表敵國第 $i$ 團軍隊位於編號 $y_i$ 的島嶼，兵力為 $d_i$。
所有同一行的數字將以單一空格隔開。
Output Format
首行輸出一個整數 $Q$，代表你決定的攻打事件數量。
接下來 $Q$ 行，每行三個整數 $u_i,v_i,p_i$，代表你要讓我國在島嶼 $u_i$ 的軍隊分流 $p_i$ 的兵力出來移動到島嶼 $v_i$。
請注意，若你輸出的 $Q$ 不是介於 $[0,Q_{upper}]$ 之間的整數、$u_i$ 和 $v_i$ 不是介於 $[1,N]$ 之間的整數 、$p_i$ 不是正整數、島嶼 $u_i$ 上的我國軍隊人數小於 $p_i$、$u_i$ 和 $v_i$ 之間沒有橋樑、$u_i$ 和 $v_i$ 相同或所有的攻打事件結束後敵國軍隊並沒有完全被消滅，都將被視為不合法的操作，會獲得 0分。否則即使我國軍隊被完全消滅，也會獲得 。
所有同一行的數字須以單一空格隔開。
Sample Input 1
1 2
2 3
1 2
3 1
Sample Output 1
1 2 2
2 3 2
Sample Input 2
1 2
2 3
2 4
3 4
3 5
1 8
2 3
4 2
3 4
5 9
Sample Output 2
2 3 3
4 3 2
3 5 1
1 2 8
2 3 8
3 5 8
Sample Input 3
1 2
1 3
1 4
1 100
2 8
3 7
4 6
Sample Output 3
1 2 8
1 3 7
1 4 6
Hints
測資限制：
- $2\le N\le 3\times 10^ 5$。
- $N-1\le M\le \min(\frac{N(N-1)}{2},5\times 10^ 5)$。
- $1\le A,B\le N$。
- $2\le A+B\le N$。
- $N-1\le Q_{upper}\le 3\times 10^ 5$。
- $1\le u_i,v_i,x_i,y_i \le N$。
- $u_i\ne v_i$。
- 沒有連接同樣兩座島嶼的兩座橋樑。
- $1\le c_i,d_i\le 10^ 9$。
- $\sum_{i=1}^ A c_i\ge \sum_{i=1}^ B d_i$。
- 不會有兩團軍隊同時在同一座島嶼。
- 保證任兩座島嶼都可以經由若干座橋樑互相來往。
本題共有 $5$ 組測試題組，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。
- ($21\%$) $M=N-1$，$u_i=i$，$v_i=i+1$。
- ($18\%$) $N\le 500$，$Q_{upper}=3\times 10^ 5$。
- ($14\%$) $N\le 500$。
- ($23\%$) $A=1$。
- ($24\%$) 無額外限制。
Problem Source
2021 板中TOI模考模擬賽
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 3~10 | $M=N-1$，$u_i=i$，$v_i=i+1$。 | 21 |
| 2 | 11~25 | $N\le 500$，$Q_{upper}=3\times 10^ 5$。 | 18 |
| 3 | 11~43 | $N\le 500$。 | 14 |
| 4 | 44~59 | $A=1$。 | 23 |
| 5 | 0~77 | 無額外限制。 | 24 |