YLCHUP头像

【思维&图论建模】题解:债权(debt)_图论_建模_思路转化_思维题目_C++算法竞赛

A. 债权(debt)
文件IO:debt 1000ms 256MiB

文章目录

题目描述

天色已晚,小 Y 决定在一处村庄过夜。这座村庄中有 n n n 个人,他们之间存在 m m m 个欠债关系。例如 A A A 欠 B B B 五元钱,而每还款 1 1 1 元钱就会给村子带来 0.1 0.1 0.1 元的成本。村长很苦恼如何能够通过债权转让的方式让成本最小化,于是求助于小 Y。现在小 Y 已经帮助村长完成了债权的转让,只需要你计算出最小化后的成本即可。

债权转让:若 A A A 欠 B B B 五元钱, B B B 欠 C C C 五元钱,可以通过债权转让变为 A A A 欠 C C C 五元钱。

输入格式

输入文件的第一行包含两个正整数 n , m n,m n,m,以空格隔开,表示一共有 n n n 个人和 m m m 个欠债关系。

接下来的 m m m 行每行包含三个正整数 x , y , z x,y,z x,y,z,以空格隔开,表示 x x x 欠 y y y 的钱数为 z z z。

输出格式

输出一个保留一位的小数,表示最小化后的成本。

样例 1

样例输入 1

5 3
1 2 5
2 3 3
4 5 4

样例输出 1

0.9

样例说明 1

1 1 1 欠 2 2 2 五元钱、 2 2 2 欠 3 3 3 三元钱可以转变为 1 1 1 欠 2 2 2 两元钱、 1 1 1 欠 3 3 3 三元钱,然后可以得到一共需要还款 9 9 9 元钱,成本为 0.9 0.9 0.9 元钱。

样例 2

样例输入 2

2 2 
1 2 5
2 1 5

样例输出 2

0.0

样例说明 2

1 1 1 和 2 2 2 债务相抵后互不相欠,成本为 0.0 0.0 0.0 元。

数据范围

  • 子任务 1 1 1( 30 30 30 分): n ≤ 10 n\le 10 n≤10, m ≤ 20 m\le 20 m≤20。
  • 子任务 2 2 2( 30 30 30 分): n ≤ 100 n\le 100 n≤100, m ≤ 10000 m\le 10000 m≤10000。
  • 子任务 3 3 3( 40 40 40 分):无特殊限制。

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 100000 1\le n\le 100000 1≤n≤100000, 1 ≤ m ≤ 200000 1\le m\le 200000 1≤m≤200000, 1 ≤ x , y ≤ n 1\le x,y\le n 1≤x,y≤n, 1 ≤ z ≤ 10 9 1\le z\le 10^9 1≤z≤109。

题解

考虑图论建模,对于A欠B x元钱,构建一条(A,B,x)的边

题目允许的“债权转让”操作,可以理解为对于A->B->C “抄近路”变成A->C

考虑边权的变化,设t=min(g[a][b],g[b][c]),则有g[a][b]-=t,g[b][c]-=t,g[a][c]+=t(前提a!=c)

有一个关键观察:不管如何转移,每个点的“净欠款”是不变的!!!(例如点A:A->B减少t,A->C增加t,所以不变)

d[i]=out[i]-in[i],若d[i]>0说明它净欠别人d[i]元,若d[i]<0说明别人欠它(它净被欠)d[i]元
因为有人欠钱,就一定有相应的人被欠钱,所以 ∑ d [ i ] = 0 \sum{d[i]}=0 ∑d[i]=0

可以理解为村里有一个“银行”,欠钱的人交d[i]元给银行,被欠钱的人从银行得到d[i]元

银行只是中转,最后的总还款额就是所有净欠钱人的欠款总和: ∑ d [ i ] > 0 d [ i ] \sum_{d[i]>0}d[i] ∑d[i]>0​d[i]

又因为正负净额相等,所以 ∑ d [ i ] > 0 d [ i ] = 1 / 2 ∗ ∑ ∣ d [ i ] ∣ \sum_{d[i]>0}d[i] = 1/2 * \sum{|d[i]|} ∑d[i]>0​d[i]=1/2∗∑∣d[i]∣(因为每个欠钱会被算2次,它的起点、终点各算一次)

这就是最小还款总额

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;

int n,m; 
ll in[N],out[N];

void solve()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z; cin>>x>>y>>z;
		in[y]+=z,out[x]+=z;
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans+=llabs(out[i]-in[i]);
	}
	ans/=2;
	cout<<ans/10<<'.'<<ans%10;
}

signed main()
{
	freopen("debt.in","r",stdin);
	freopen("debt.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/YLCHUP/article/details/170743400

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--