#P10888. [2015yali备战noi]debts

    ID: 10031 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200提高子集 DPlowbit路径恢复同向双指针

[2015yali备战noi]debts

题目描述

已知 NN 名公民之间的欠款关系。一个人给另一个人支付正数金额,称为一次交易。允许用等价交易清偿全部欠款。例如,若 AA 欠 BB 10 元且 BB 欠 CC 10 元,则只需 AA 给 CC 10 元。

形式化地,把初始债务看作带权有向图 G=(V,E)G=(V,E)。对每个顶点 vv 定义

$$p(v)=\sum_{(u,v)\in E}c(u,v)-\sum_{(v,u)\in E}c(v,u).$$

构造一个点集相同的带权有向图 G′G',使每个点的 p(v)p(v) 保持不变。先使 G′G' 的边数最小,在边数最小的前提下使全部边权之和最小。若仍有多个最优方案,输出任意一个。

输入格式

第一行两个整数 N,MN,M(2≤N≤202\le N\le 20,1≤M≤1001\le M\le100),表示人数和欠款关系数。公民编号为 11 至 NN。

接下来 MM 行,每行三个整数 A,B,KA,B,K(1≤A,B≤N1\le A,B\le N,A≠BA\ne B,1≤K≤1001\le K\le100),表示 AA 欠 BB 金额 KK。

输出格式

第一行两个整数 T,CT,C,分别表示最少交易次数和此前提下最小交易总金额。

接下来 TT 行,每行三个整数 A,B,KA,B,K,表示 AA 支付 BB 金额 KK。

样例

6 5
1 2 10
2 3 10
4 5 5
5 6 5
6 4 5
1 10
1 3 10

原 PDF 题面