# 洛谷 P2774 方格取数问题 题解【网络流】【最小点权覆盖集】

## 输入输出样例

3 3
1 2 3
3 2 3
2 3 1


11


m,n<=100

## 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[50000];
{
}
int d[10500],q[10500];
//源点0，汇点10001
bool bfs()
{
int l=0,r=0;
memset(d,0,sizeof(d));
d[10001]=1;
q[++r]=10001;
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==10001)
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 main()
{
int n,m,u,ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%d",&u);
ans+=u;
if((i+j)&1)
{
if(i<n)
if(j<m)
}
else
{
if(i<n)
if(j<m)
}
}
while(bfs())
{
int tmp;
do
{
tmp=dinic(0,0x3fffffff);
ans-=tmp;
}while(tmp);
}
printf("%d\n",ans);
return 0;
}


### 4 说点什么

0 Followers

Most reacted comment
0 Comment authors
Recent comment authors
Subscribe

[…] Information on that Topic: wjyyy.top/3106.html […]