st_nec's Blog

最近我得把网络流这一块搞一搞。

最大权闭合子图问题，胡乱搞搞就行了。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
using namespace std;

struct edge{
	int to,next,v;
}e[500000];

int h[500000],q[500000],head[500000],ans=0,sum=0,n,m,S,T,ne=1;

inline void insert(int u,int v,int x){
	ne++;
	e[ne].to=v;
	e[ne].v=x;
	e[ne].next=head[u];
	head[u]=ne;
	ne++;
	e[ne].to=u;
	e[ne].v=0;
	e[ne].next=head[v];
	head[v]=ne;
}

inline bool bfs(){
	int t=0,w=1;
	memset(h,-1,sizeof(h));
	q[0]=h[S]=0;
	while(t<w){
		int now=q[t++];
		for(int i=head[now];i;i=e[i].next){
			if(e[i].v&&h[e[i].to]==-1){
				h[e[i].to]=h[now]+1;
				q[w++]=e[i].to;
			}
		}
	}
	if(h[T]==-1)	return 0;
	else	return 1;
}

int dfs(int x,int f){
	if(x==T)	return f;
	int w,used=0;
	for(int i=head[x];i;i=e[i].next){
		if(e[i].v&&h[e[i].to]-h[x]==1){
			w=f-used;
			w=dfs(e[i].to,min(w,e[i].v));
			e[i].v-=w;
			e[i^1].v+=w;
			used+=w;
			if(used==f)	return f;
		}
	}
	if(!used)	h[x]=-1;
	return used;
}

void dinic(){
	while(bfs())	ans+=dfs(S,inf);
}

int main(){
	scanf("%d%d",&n,&m);
	S=0;T=n+m+1;
	for(int i=1;i<=n;i++){
		int p;
		scanf("%d",&p);
		insert(i,T,p);
	}
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		insert(S,n+i,c);
		insert(n+i,a,inf);
		insert(n+i,b,inf);
		sum+=c;
	}
	dinic();
	printf("%d",sum-ans);
	return 0;
}