名校联赛第三天A层 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 元”。

输出文件共一行，输出最小的总债务规模。

数据范围

对于 30% 的数据，1 ≤ n ≤ 10，1 ≤ m ≤ 10。

对于 60% 的数据，1 ≤ n ≤ 100, 1 ≤ m ≤ 104。

对于 80% 的数据，1 ≤ n ≤ 104，1 ≤ m ≤ 104。

对于 100% 的数据，1 ≤ n ≤ 106，1 ≤ m ≤ 106。

对于所有的数据，保证 1 ≤ ai; bi ≤ n; 0 < ci ≤ 100。

 　　这道题太坑爹了，当时一看就以为是图论题，一股脑就扎进去了，然后一脸颓废的杠了一个半小时，发现挂了，导致此次考试全线崩溃，我对不起老师，对不起组织，对不起HZOI。

　　这道题当时确实想歪了，这道题和图论八竿子打不到一块。所以让我们从根本上来分析这道问题，首先，债务规模就是所有人欠的债的总和，债务得以转移的前提就是有人在欠钱的同时又被欠钱了，因此既然欠债可以转移，转移给谁不是转移呢，因此我们只要计算出一个人的净欠款，再把所有结算完之后还在欠账的人的欠款总额加在一起，就可以了。

　崩爹呢！

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<map>
 7 #include<queue>
 8 #include<string>
 9 #include<cmath>
10 using namespace std;
11 int n,m,sum[1000005];
12 int main(){
13     scanf("%d%d",&n,&m);
14     for(int i=1;i<=m;i++)
15     {
16         int x,y,z;
17         scanf("%d%d%d",&x,&y,&z);
18         sum[x]-=z;
19         sum[y]+=z;
20     }
21     int ans=0;
22     for(int i=1;i<=n;i++)
23     {
24         if(sum[i]<0)
25             ans-=sum[i];
26     }
27     printf("%d\n",ans);
28     //while(1);
29     return 0;
30 }

View Code