【题目分析】
最大权闭合子图。
S到集合1容量为获利的大小,集合2到T为所需要付出的相反数。
然后求出最大流,然后用总的获利相减即可。
【代码】
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> //#include <map> #include <set> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define maxn 50005 #define ll long long #define me 200005 #define inf 0x3f3f3f3f #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) void Finout() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif } int Getint() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } int h[me<<1],to[me<<1],ne[me<<1],fl[me<<1],en=0,S=0,T=me-1; void add(int a,int b,int c) { // cout<<"add "<<a<<" "<<b<<" "<<c<<endl; to[en]=b; ne[en]=h[a]; fl[en]=c; h[a]=en++; to[en]=a; ne[en]=h[b]; fl[en]=0; h[b]=en++; } int map[me]; bool tell() { queue <int> q; memset(map,-1,sizeof map); map[S]=0; while (!q.empty()) q.pop(); q.push(S); while (!q.empty()) { int x=q.front(); q.pop(); // cout<<"bfs"<<x<<endl; for (int i=h[x];i>=0;i=ne[i]) { // cout<<"to "<<to[i]<<endl; if (map[to[i]]==-1&&fl[i]>0) { map[to[i]]=map[x]+1; q.push(to[i]); } } } // cout<<"over"<<endl; if (map[T]!=-1) return true; return false; } int zeng(int k,int r) { if (k==T) return r; int ret=0; for (int i=h[k];i>=0&&ret<r;i=ne[i]) if (map[to[i]]==map[k]+1&&fl[i]>0) { int tmp=zeng(to[i],min(fl[i],r-ret)); ret+=tmp; fl[i]-=tmp; fl[i^1]+=tmp; } if (!ret) map[k]=-1; return ret; } int n,m,x,a,b,c; ll ans=0; int main() { memset(h,-1,sizeof h); Finout(); n=Getint(); m=Getint(); F(i,1,n) { x=Getint(); add(i+m,T,x); } F(i,1,m) { a=Getint(); b=Getint(); c=Getint(); add(S,i,c); add(i,m+a,inf); add(i,m+b,inf); ans+=c; } // cout<<"add over"<<endl; ll tmp=0,now=0; while (tell()) while (tmp=zeng(S,inf)) now+=tmp; // cout<<now<<endl; cout<<ans-now<<endl; }