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)
}