网络流求最小割,另开源点汇点。
对于n个点,如果站力消耗大于0,则源点连条消耗值为权的边过去,反之这个点连条消耗值的绝对值为权的边到汇点,如果攻占b之后才可以攻占a,那么就连条a->b 权值为inf。然后结果就是所有正值之和减去最大流
#include<cstdio> #include<cstring> int n,head[600],dis[600],gap[600],s,t,m,sum,cnt; const int inf=1<<30; struct EDGE { int to,f,nxt; }edge[600000]; int min(int a,int b) { return a<b?a:b; } void init() { sum=cnt=0; memset(gap,0,sizeof(gap)); memset(head,-1,sizeof(head)); memset(dis,0,sizeof(dis)); } void add(int x,int y,int c) { edge[cnt].to=y; edge[cnt].f=c; edge[cnt].nxt=head[x]; head[x]=cnt++; edge[cnt].to=x; edge[cnt].nxt=head[y]; edge[cnt].f=0; head[y]=cnt++; } int dfs(int x,int flow) { if(x==t) return flow; int temp=flow,pos=t-1,j; for(j=head[x];j!=-1;j=edge[j].nxt) { int y=edge[j].to; int c=edge[j].f; if(c>0&&dis[x]==dis[y]+1) { int temp_flow=dfs(y,min(temp,c)); temp-=temp_flow; edge[j].f-=temp_flow; edge[j^1].f+=temp_flow; if(temp==0||dis[s]==t) return flow-temp; } if(c>0&&pos>dis[y]) pos=dis[y]; } if(temp==flow) { if(!(--gap[dis[x]])) dis[s]=t; else gap[dis[x]=pos+1]++; } return flow-temp; } int sap() { int maxflow=0; while(dis[s]<t) { maxflow+=dfs(s,inf); } return sum-maxflow; } int main() { while(2==scanf("%d%d",&n,&m)) { s=n+1,t=s+1; init(); for(int i=1;i<=n;i++) { int c; scanf("%d",&c); if(c>0) add(s,i,c),sum+=c; if(c<0) add(i,t,-c); } for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b,inf); } printf("%d\n",sap()); } return 0; };