自动搬运

查看原文

来自洛谷，原作者为

	YellowBean_Elsa You find me waiting in the wings......

搬运于2025-08-24 21:53:37，当前版本为作者最后更新于2020-04-10 15:44:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

	S 向正权点建边，容量为点权；负权点向 T 建边，容量为点权绝对值，

	x->y 的限制就直接建 x->y。最后拿正权和-最小割就是答案。

这是神仙出题人的方法，我来给一个完整的正确性证明。

证明

若一个限制条件连的 x, y 点权不同号，在取了其中正的那个后，要么放弃正的，要么取了负的，要么减少 dXY，与连边方式的最小割相同。

如果同号会怎样呢？

我们任意选两个同号点1, 2，连边2->1，选1的任意一条到T的路径1->3->T。（如果没有这条路径那么1，2常规都选（负点权则不选）答案不受影响）

边a, x, y中至少有一条删掉。

1. 删x或y：

1，2仍然都选，且不用割去其它边，答案不受影响。

2. 删a：

1不选了，这时要么不选2（割b）要么损失d12（割c）。

如果割x或y了咋办？

怎么可能，那样转化为上一种情况，a就不用割了，不是最小割。

那这样答案也不受影响了。

综上

同号的限制条件也解决了。

证毕

最后还是贴一下代码吧。

//coder: Feliks*GM-YB
#include<bits/stdc++.h>
#define fu(i,a,b) for(register int i = a, I = (b) + 1; i < I; ++i)
#define fd(i,a,b) for(register int i = a, I = (b) - 1; i > I; --i)
typedef long long ll;
using namespace std;
template <class T> inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(!isdigit(ch))f=ch=='-'?-1:1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    x*=f;
}int n,m;
#define go(x) for(int i=first[x],y=v[i];i;i=nex[i],y=v[i])
const int N=1e3+5;
const int M=1e5+5;
int v[M],nex[M],w[M],first[N],tot=1;
inline void add(int x,int y,int z){
    v[++tot]=y;w[tot]=z;
    nex[tot]=first[x];
    first[x]=tot;
}namespace Dinic{
    const int s=0;
    const int t=N-4;
    const int inf=1e9+7;
    int d[N],flow,ans;
	queue<int> q;
    inline bool bfs(){
        while(!q.empty())q.pop();
        memset(d,0,sizeof(d));
        q.push(s);d[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            go(x){
                if(!w[i] || d[y])continue;
                q.push(y);
                d[y]=d[x]+1;
                if(y==t)return 1;
            }
        }return 0;
    }int dinic(int x,int f){
        if(x==t)return f;
        int res=f,k;
        for(int i=first[x],y=v[i];i && res;i=nex[i],y=v[i]){
            if(!w[i] || d[y]!=d[x]+1)continue;
            k=dinic(y,min(res,w[i]));
            if(!k)d[y]=0;
            w[i]-=k;w[i^1]+=k;
            res-=k;
        }return f-res;
    }inline void solve(int c){
    	while(bfs()){
			while(flow=dinic(s,inf))ans+=c*flow;
		}
	}
}using namespace Dinic;
int a[N],df;
int main(){
	read(n),read(m);
	fu(i,1,n){
		read(a[i]);
		if(a[i]>=0)add(s,i,a[i]),add(i,s,0),ans+=a[i];
		else add(i,t,-a[i]),add(t,i,0);
	}fu(i,1,m){
		int x,y;
		read(x),read(y);
		read(df);
		add(x,y,df),add(y,x,0);
	}solve(-1);
	printf("%d\n",ans);
    return 0;
}