#P10888. [2015yali备战noi]debts
[2015yali备战noi]debts
题目描述
已知 名公民之间的欠款关系。一个人给另一个人支付正数金额,称为一次交易。允许用等价交易清偿全部欠款。例如,若 欠 10 元且 欠 10 元,则只需 给 10 元。
形式化地,把初始债务看作带权有向图 。对每个顶点 定义
$$p(v)=\sum_{(u,v)\in E}c(u,v)-\sum_{(v,u)\in E}c(v,u).$$构造一个点集相同的带权有向图 ,使每个点的 保持不变。先使 的边数最小,在边数最小的前提下使全部边权之和最小。若仍有多个最优方案,输出任意一个。
输入格式
第一行两个整数 (,),表示人数和欠款关系数。公民编号为 至 。
接下来 行,每行三个整数 (,,),表示 欠 金额 。
输出格式
第一行两个整数 ,分别表示最少交易次数和此前提下最小交易总金额。
接下来 行,每行三个整数 ,表示 支付 金额 。
样例
6 5
1 2 10
2 3 10
4 5 5
5 6 5
6 4 5
1 10
1 3 10