[文章目录]
Description
给你n个点，又给了m个关系，Ai，Bi，Ci。当你将Ai，Bi点都选了能得到Ci的收益，但是选第i个点时，会有一个花费Pi。问你能获得的最大收益。
N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100
网洛流。构造一个图，收益为正权点，原图点为负权点，然后，每个收益向Ai，Bi连边。然后求一下这个图的最大权闭合子图就行了。
s向所有正权点连边，边权为点的权值，负权点向汇点连边，边权为点权的绝对值，然后原图中的边保留，边权为正无穷。（别忘加反向弧，边权为0）。跑一遍最大流，再用所有正权点的点权和减去最大流就是答案了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
queue<int>q;
int n,m,ans,sum;
int dis[56000];
int head[56000],to[410000],nxt[410000],f[410000],cnt=1;
bool bfs()
{
memset(dis,-1,sizeof(dis));
while(!q.empty())q.pop();
q.push(n+m+1);dis[n+m+1]=0;
while(!q.empty())
{
int x=q.front();q.pop();
for(int y,i=head[x];i;i=nxt[i])
if(f[i]&&dis[y=to[i]]<0)
{
dis[y]=dis[x]+1;
q.push(y);
if(y==n+m+2) return true;
}
}
return false;
}
int dinic(int x,int flow)
{
int k,tmp=flow;
if(x==n+m+2) return flow;
for(int y,i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[y=to[i]]==dis[x]+1)
{
k=dinic(y,min(f[i],tmp));
if(k==0) dis[y]=-1;
tmp-=k;f[i]-=k;f[i^1]+=k;
if(tmp==0) break;
}
return flow-tmp;
}
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
f[cnt]=z;
head[x]=cnt;
to[++cnt]=x;
nxt[cnt]=head[y];
f[cnt]=0;
head[y]=cnt;
}
int main()
{
scanf("%d%d",&n,&m);
for(int x,i=1;i<=n;i++)
{
scanf("%d",&x);
add(i,n+m+2,x);
}
for(int x,y,z,i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
sum+=z;
add(n+i,x,1<<30);
add(n+i,y,1<<30);
add(n+m+1,n+i,z);
}
while(bfs()) ans+=dinic(n+m+1,1<<30);
printf("%d",sum-ans);
return 0;
}