# 洛谷 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 head[10010],ecnt=-1;
void add(int from,int to,int v)
{
e[++ecnt]=edge(to,head[from],v);
head[from]=ecnt;
e[++ecnt]=edge(from,head[to],0);
head[to]=ecnt;
}
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];
for(int i=head[x];~i;i=e[i].nxt)
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;
for(int i=head[x];flow&&~i;i=e[i].nxt)
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()
{
memset(head,-1,sizeof(head));
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)
{
add((i-1)*m+j,10001,u);
if(i<n)
add(i*m+j,(i-1)*m+j,0x3fffffff);
if(j<m)
add((i-1)*m+j+1,(i-1)*m+j,0x3fffffff);
}
else
{
add(0,(i-1)*m+j,u);
if(i<n)
add((i-1)*m+j,i*m+j,0x3fffffff);
if(j<m)
add((i-1)*m+j,(i-1)*m+j+1,0x3fffffff);
}
}
while(bfs())
{
int tmp;
do
{
tmp=dinic(0,0x3fffffff);
ans-=tmp;
}while(tmp);
}
printf("%d\n",ans);
return 0;
}


### 4 说点什么

4 Comment threads
0 Thread replies
0 Followers

Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
Subscribe

… [Trackback]

[…] Find More Info here to that Topic: wjyyy.top/3106.html […]

… [Trackback]

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

… [Trackback]

[…] There you will find 8291 additional Information on that Topic: wjyyy.top/3106.html […]

… [Trackback]

[…] Read More on to that Topic: wjyyy.top/3106.html […]

/* */