e200: 金錢危機
Tags :
Accepted rate : 6人/8人 ( 75% ) [非即時]
評分方式:
Special

最近更新 : 2019-05-27 10:37

Content

  「欸,我錢包忘在樓上,可以幫我墊一下嗎?」

  「拜託借我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}$塊錢。

  你希望能構造出一個新的「還款圖」,使得每個人都沒有任何損失,而且金錢總流動量(也就是所有還款關係的還錢量總和)最少。

Input

輸入首行有一個正整數$\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}$塊錢。

Output

對於每筆測資,首行輸出一個$\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。

Sample Input
2
4 3
1 2 1
2 3 3
3 4 1
2 2
1 2 2
2 1 3
Sample Output
3
1 3 1
2 3 1
2 4 1
1
2 1 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (8%): 2.0s , <10M
公開 測資點#1 (28%): 2.0s , <1M
公開 測資點#2 (64%): 2.0s , <50M
Hint :

  第一筆範例測資中, 我們可以讓$\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}$:無特別限制。

Tags:
出處:
板橋高中校友盃 [管理者:
baluteshih (波路特石)
]


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