# hdu 3061 Battle 题解【网络流】【最小割】【最大权闭合子图】

## Sample Input

5 5
8
-8
-10
12
-10
1 2
2 5
1 4
3 4
4 5


## Sample Output

2


## Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{
return x<y?x:y;
}
struct edge
{
int n,nxt,v;
edge(int n,int nxt,int v)
{
this->n=n;
this->nxt=nxt;
this->v=v;
}
edge(){}
}e[300000];
{
}
int d[505],q[505];
bool bfs()
{
int l=0,r=0;
memset(d,0,sizeof(d));
q[++r]=501;
d[501]=1;
while(l<r)
{
int x=q[++l];
if(e[i^1].v&&!d[e[i].n])
{
d[e[i].n]=d[x]+1;
q[++r]=e[i].n;
}
}
return d[0]>0;
}
int dinic(int x,int in)
{
if(x==501)
return in;
int flow=in;
if(e[i].v&&d[e[i].n]==d[x]-1)
{
int tmp=dinic(e[i].n,Min(e[i].v,flow));
if(!tmp)
d[e[i].n]=0;
e[i].v-=tmp;
e[i^1].v+=tmp;
flow-=tmp;
}
return in-flow;
}
int a[505],ans=0;
bool used[505];
int main()
{
int n,m,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(used,0,sizeof(used));
ecnt=-1,ans=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
if(a[i]<0)
else
{
ans+=a[i];
}
}
for(int i=1;i<=m;++i)
{
scanf("%d%d",&u,&v);
}
while(bfs())
{
int tmp;
do
{
tmp=dinic(0,0x3fffffff);
ans-=tmp;
}while(tmp);
}
printf("%d\n",ans);
}
return 0;
}


Subscribe

/* */