# hdu 3657 Game 题解【网络流】【最小点权覆盖集】

## 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[30000];
{
}
int d[2505],q[2505];
bool bfs()
{
int l=0,r=0;
memset(d,0,sizeof(d));
d[2501]=1;
q[++r]=2501;
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==2501)
return in;
int flow=in;
if(e[i].v&&d[e[i].n]==d[x]-1)
{
int tmp=dinic(e[i].n,Min(flow,e[i].v));
if(!tmp)
d[e[i].n]=0;
e[i].v-=tmp;
e[i^1].v+=tmp;
flow-=tmp;
}
return in-flow;
}
int a[55][55];
bool lkd[55][55];
int main()
{
int n,m,k,u,v;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
memset(lkd,0,sizeof(lkd));
ecnt=-1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
for(int i=1;i<=k;++i)
{
scanf("%d%d",&u,&v);
lkd[u][v]=1;
}
int sum=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
sum+=a[i][j];
if((i+j)&1)//注意区分连边，并只连一个方向
{
if(i<n)
if(j<m)
}
else
{
if(i<n)
if(j<m)
}
}
int ans=0;
while(bfs())
{
int tmp;
do
{
tmp=dinic(0,0x3fffffff);
ans+=tmp;
}while(tmp);
}
printf("%d\n",sum-ans);
}
return 0;

}


### 2 说点什么

0 Followers

Most reacted comment
0 Comment authors
Recent comment authors
Subscribe