473 字
2 分钟
Evensgn 的债务
题目描述
Evensgn 有一群好朋友,他们经常互相借钱。假如说有三个好朋友 A,B,C。
A 欠 B 20 元,B 欠 C 20 元,总债务规模为 20+20=40 元。Evensgn 是个追求简约
的人,他觉得这样的债务太繁杂了。他认为,上面的债务可以完全等价为 A 欠 C
20 元,B 既不欠别人,别人也不欠他。这样总债务规模就压缩到了 20 元。
现在给定 n 个人和 m 条债务关系。Evensgn 想找到一种新的债务方案,使得
每个人欠钱的总数不变,或被欠钱的总数不变(但是对象可以发生变化),并且使
得总债务规模最小。
输入
输入文件第一行两个数字 n; m,含义如题目所述。
接下来 m 行,每行三个数字 ai; bi; ci,表示 ai 欠 bi 的钱数为 ci。
注意,数据中关于某两个人 A 和 B 的债务信息可能出现多次,将其累加即可。
如”A 欠 B 20 元”、”A 欠 B 30 元”、”B 欠 A 10 元”,其等价为”A 欠 B 40 元”。
输出
输出文件共一行,输出最小的总债务规模。
样例输入
样例输入 1
5 3
1 2 10
2 3 1
2 4 1
样例输入 2
4 3
1 2 1
2 3 1
3 1 1
样例输出
样例输出 1
10
样例输出 2
0
题解
考试的时候想了想
发现可以理解为
每一个人将他的真正的需要交出的钱一起交出
然后就需要拿钱的人去拿
统计一下就可以了
#include <cstdio>
#include <algorithm>
using namespace std;
int in[1000005], out[1000005];
long long Sum = 0;
int main()
{
int n, m, a, b, c;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
out[a] += c;
in[b] += c;
Sum += c;
}
for (int i = 1; i <= n; i++)
{
Sum -= min(out[i], in[i]);
}
printf("%lld\n", Sum);
//while (1)
}