题解：CF1266D Decreasing Debts

· · 题解

思路

一共有两个操作，最后想要使得债务总和最小。

不难发现，操作一不会让债务总和最小，操作二才会。

但是刚开始我们不存在 d(a,a) 的债务。不难发现需要用操作一来创造这样指向自身的债务。

也就要使得 c=b 或 a=d。将这两个代入操作一，可以发现两者是等价的，这里用 c=b 做一个演示。

其实 b=c 时的操作一就是这样的一个变化的过程，但是 d(b,c) 这个自环是可以用操作二删掉的。这样总债务就少了 x。

不难想到，仅考虑这三个点，x=\min\{m,n\} 时，能够删去最多的债务。

那么考虑扩展一下：

那么对于这几个点，最后可以将总和较小的那一组边全部删去。也就是说较小的那组边是无用的，只需要留下总和较大的那组边。

也就是最后只剩下欠债（记为正），或者借出（记为负）。最后还剩下的的债务价值为 \sum\limits_{i=1}^n y_i- \sum \limits_{i=1}^n x_i。

我们也不难发现，可以通过操作一进行债务转移。

具体操作是选择两个人 A,B 将他们互相还（欠）债相同的钱（但是债务价值互为相反数），这两个东西可以通过操作一将他们所欠的钱转移到正确的人的手上。

上述这个性质可以看作建了一个等价的新图，而这个建图方式只需要每个点的债务价值，建图就很方便了。只要任意选择两个点，将连边，将两点的价值加（或减）去两点价值绝对值得较小值。然后如果价值变成了 0 就选择下一个同向的加入。

代码实现

只看思路可能会有点绕。

看看代码就能明白了。

:::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5;
int n,m;
int pos[N+5],neg[N+5],pn,nn;
int debt[N+5];
struct node
{
    int u,v,w;
}ans[N+5];
int ansn;
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        debt[x]+=z; //计算点的债务价值 
        debt[y]-=z;
    }
    for(int i=1;i<=n;i++)
    {
        if(debt[i]>0) neg[++nn]=i; //判断他是正向还是负向的 
        else pos[++pn]=i;
    }
    int l=1,r=1;
    while(l<=nn)
    {
        int cost=min(debt[neg[l]],-debt[pos[r]]); //随意选择两点判断边权 
        debt[neg[l]]-=cost,debt[pos[r]]+=cost; //减去边权 
        if(cost) ans[++ansn].u=neg[l],ans[ansn].v=pos[r],ans[ansn].w=cost; //记录答案 
        if(!debt[neg[l]]) l++; //将债务价值变成0的点迭代 
        if(!debt[pos[r]]) r++;
    }
    cout<<ansn<<"\n";
    for(int i=1;i<=ansn;i++) cout<<ans[i].u<<" "<<ans[i].v<<" "<<ans[i].w<<"\n";
    return 0;
}

:::