最大权闭合子图...详细证明见胡伯涛论文
s向正权点连边容量为收益 负权点向T连边容量为花费
然后对于每一条依赖关系 两个点向依赖的点连边容量为正无穷
最后答案即为总收益减最大流
1 #include<bits/stdc++.h> 2 #define inf 2147483647 3 #define N 60000 4 #define rep(i,l,r) for(int i=l;i<=r;i++) 5 using namespace std; 6 int n,m,ans,tot=1,head[N],dis[N],a,b,c,T; 7 struct Edge{ 8 int to,next,w; 9 }e[350000]; 10 inline int read() { 11 int x=0,ch=getchar(); 12 while(ch<'0'||ch>'9') ch=getchar(); 13 while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); 14 return x; 15 } 16 inline void ins(int u,int v,int w) { 17 e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; 18 } 19 inline void insert(int u,int v,int w) { 20 ins(u,v,w); ins(v,u,0); 21 } 22 inline bool bfs(){ 23 for(int i=0;i<=T;i++) dis[i]=-1; queue<int>q; q.push(0); dis[0]=0; 24 while(!q.empty()) { 25 int x=q.front(); q.pop(); 26 for(int k=head[x];k;k=e[k].next) 27 if(dis[e[k].to]<0 && e[k].w>0) { 28 dis[e[k].to]=dis[x]+1; q.push(e[k].to); 29 } 30 } 31 if(dis[T]>0) return 1;else return 0; 32 } 33 int find(int x,int low){ 34 if(x==T) return low; 35 int delta=low,now; 36 for(int k=head[x];k;k=e[k].next) 37 if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 38 now=find(e[k].to,min(e[k].w,delta)); 39 e[k].w-=now; e[k^1].w+=now; delta-=now; 40 if(!delta) return low; 41 } 42 dis[x]=-1; 43 return low-delta; 44 } 45 int main () { 46 n=read(); m=read(); T=1+n+m; 47 rep(i,1,n) a=read(),insert(i,T,a); 48 rep(i,1,m) a=read(),b=read(),c=read(),insert(n+i,a,inf),insert(n+i,b,inf),insert(0,n+i,c),ans+=c; 49 while(bfs()) ans-=find(0,inf); 50 printf("%d",ans); 51 }