「欸，我錢包忘在樓上，可以幫我墊一下嗎？」
「拜託借我50塊，明天還你。」
「快點繳班費！！！！」
學生時期常常會有大家把錢借來借去的問題，可想而知，如果欠錢的人一直還沒還錢，卻一直有新的借據出現的話，整個借錢的關係只會越來越複雜。
金錢的流動越多，就越容易發生爭執和意外，為了減緩這件事情，你決定把大家的「還款圖」記錄下來，並試圖減少金錢的流量總量。
用明確一點的方式說明，現在有$\color{black}{\space N\space}$個人，並且有$\color{black}{\space M\space}$條還款關係，每條還款關係將會有$\color{black}{\space a,b,w\space}$三個正整數，代表編號$\color{black}{\space a\space}$的人還需要還編號$\color{black}{\space b\space}$的人$\color{black}{\space w\space}$塊錢。
你希望能構造出一個新的「還款圖」，使得每個人都沒有任何損失，而且金錢總流動量(也就是所有還款關係的還錢量總和)最少。
輸入首行有一個正整數$\color{black}{\space T(T\leq 20)\space}$，代表測資筆數。
每筆測資首行有兩個正整數$\color{black}{\space N,M(N,M\leq 10^5)\space}$如題目所述。
接下來$\color{black}{\space M\space}$行，每行三個整數$\color{black}{\space a,b,w(1\leq a,b\leq N,a\neq b,1\leq w\leq 10^4)\space}$，代表編號$\color{black}{\space a\space}$的人還需要還編號$\color{black}{\space b\space}$的人$\color{black}{\space w\space}$塊錢。
對於每筆測資，首行輸出一個$\color{black}{\space k\space}$，代表你重新構造完的圖有$\color{black}{\space k\space}$條邊，接下來$\color{black}{\space k\space}$行，每行三個正整數$\color{black}{\space a,b,w\space}$，你構造出來的圖中，編號$\color{black}{\space a\space}$的人還需要還編號$\color{black}{\space b\space}$的人$\color{black}{\space w\space}$塊錢。
你的輸出需要滿足對於每筆測資，有$\color{black}{\space k\leq max(M,N)\space}$且任意一條還款關係都有$\color{black}{\space 1\leq a,b\leq N,a\neq b,1\leq w\leq 10^9\space}$，當有任一項不符合，你將會獲得一個WA；否則對於任何一個還錢量總和是最佳解(最小值)的關係圖，你都能獲得AC。
2 4 3 1 2 1 2 3 3 3 4 1 2 2 1 2 2 2 1 3
3 1 3 1 2 3 1 2 4 1 1 2 1 1
第一筆範例測資中， 我們可以讓$\color{black}{\space 2\space}$號幫$\color{black}{\space 3\space}$號還$\color{black}{\space 1\space}$塊給$\color{black}{\space 4\space}$號，並讓$\color{black}{\space 1\space}$號再幫$\color{black}{\space 2\space}$號還$\color{black}{\space 1\space}$塊給$\color{black}{\space 3\space}$號，這樣最後$\color{black}{\space 2\space}$號只要再還$\color{black}{\space 1\space}$塊給$\color{black}{\space 3\space}$號便能使所有人沒有損失，並使總流動量從原本的$\color{black}{\space 1+3+1=5\space}$降為$\color{black}{\space 1+1+1=3\space}$。
第二筆範例測資中， $\color{black}{\space 1\space}$號和$\color{black}{\space 2\space}$號互相欠了錢，抵銷之後易知$\color{black}{\space 2\space}$號只需要還$\color{black}{\space 1\space}$號$\color{black}{\space 1\space}$塊便能完成還款，總流動量從原本的$\color{black}{\space 2+3=5\space}$降為$\color{black}{\space 1\space}$。
本題共有三組測試題組，條件限制如下所示。每一組可對應到一或多筆測試資料。
測資點$\color{black}{\space 0(8\%)\space}$：$\color{black}{\space N=2\space}$。
測資點$\color{black}{\space 1(28\%)\space}$：$\color{black}{\space N\leq 100,M\leq 500\space}$。
測資點$\color{black}{\space 2(64\%)\space}$：無特別限制。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||