473 字
2 分钟
Evensgn 的债务
2017-08-08

题目描述#

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)
}
Evensgn 的债务
https://www.nekomio.com/posts/76/
作者
NekoMio
发布于
2017-08-08
许可协议
CC BY-NC-SA 4.0