CF1266D Decreasing Debts

巧妙的思维题

题解：

为了方便表述，我设$in(x)$表示点$x$的入边的权值和，$out(x)$表示点$x$的出边的权值和

在此题中，我们需要发现如果一条出边$$满足$in(u)=0$，$out(v)=0$，且起点$u$固定，那么只要终点$v$合法就可以随意连（这里的“合法”指的是这条边的权值小于$in(v)$），入边同理。

为什么呢？因为如果满足上述条件，那么此时能与边$$发生关系的边$$一定是与它无公共端点的，此时会变成$$和$$，也就是上文所说的“随便连”

为了让图中只存在这样的边，我们需要消去形如$u->v->w$的边

具体地，消去的方法就是让$in(v)$和$out(v)$同时减去$\min(in(v),out(v))$

这样，点$v$就会偏向$u$或$w$，甚至直接消失

现在，图上就只剩下两种点了，我们把它划分成两个点集：

只有出边的点集A

只有入边的点集B

只要双指针跑一遍（两个点集分别一个），将它们随意配对，用点集B的$in()$去抵消点集A的$out()$只需满足最后所有的$in()$和$out()$都等于0就好了，而每进行一次抵消，就是连一次边，消一个（或两个）点

为什么一定有方案存在，使得A和B可以同时消完呢？因为$\sum\limits_{u\in A} out(u)=\sum\limits_{u\in B} in(u)$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=1e5+5;
int n,m,in[N],out[N];
vector<int> a,b;

struct edge{
    int x,y,z;
};
vector<edge> ans;

signed main(){
    read(n);read(m);
    for(int i=1,x,y,z;i<=m;i++){
        read(x);read(y);read(z);
        out[x]+=z;
        in[y]+=z;
    }
    for(int i=1;i<=n;i++){
        int tp=min(in[i],out[i]);
        in[i]-=tp;
        out[i]-=tp;
        if(in[i]) b.push_back(i);
        if(out[i]) a.push_back(i);
    }
    for(int i=0,j=0;i<a.size()&&j<b.size();){
        int tp=min(out[a[i]],in[b[j]]);
        out[a[i]]-=tp;
        in[b[j]]-=tp;
        ans.push_back((edge){a[i],b[j],tp});
        if(out[a[i]]==0) i++;
        if(in[b[j]]==0) j++;
    }
    write(ans.size());puts("");
    for(int i=0;i<ans.size();i++){
        write(ans[i].x);putchar(' ');
        write(ans[i].y);putchar(' ');
        write(ans[i].z);puts("");
    }
}