题目描述
在一个有 m*n 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。
输入格式:
第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。
输出格式:
程序运行结束时,将取数的最大总和输出
输入输出样例
输入样例 #1:
- 3 3
- 1 2 3
- 3 2 3
- 2 3 1
输出样例 #1:
- 11
说明
m,n<=100
最大独立集 =\(\sum\) 点权 - 最小顶点覆盖
观察图可知这是一个二分图(按横纵坐标之和的奇偶分成两边)
所以二分图的最小顶点覆盖就是最小割
(可以理解为,每一条边设为 \(inf\),那么边两端的点就至少有一个要被割掉,满足最小顶点覆盖的定义)
最小割 = 最大流
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- using namespace std;
- #define inf 1000000000
- const int _ = 100005;
- struct edge{int to,next,w;}a[_<<1];
- int n,m,s,t,head[_],cnt=1,dep[_],cur[_],sum,ans;
- queue<int>Q;
- void link(int u,int v,int w)
- {
- a[++cnt]=(edge){v,head[u],w};
- head[u]=cnt;
- a[++cnt]=(edge){u,head[v],0};
- head[v]=cnt;
- }
- bool bfs()
- {
- memset(dep,0,sizeof(dep));
- dep[s]=1;Q.push(s);
- while (!Q.empty())
- {
- int u=Q.front();Q.pop();
- for (int e=head[u];e;e=a[e].next)
- if (a[e].w&&!dep[a[e].to])
- dep[a[e].to]=dep[u]+1,Q.push(a[e].to);
- }
- return dep[t];
- }
- int dfs(int u,int flow)
- {
- if (u==t)
- return flow;
- for (int &e=cur[u];e;e=a[e].next)
- if (a[e].w&&dep[a[e].to]==dep[u]+1)
- {
- int temp=dfs(a[e].to,min(flow,a[e].w));
- if (temp) {a[e].w-=temp;a[e^1].w+=temp;return temp;}
- }
- return 0;
- }
- int main()
- {
- scanf("%d%d",&n,&m);s=n*m+1;t=s+1;
- for (int i=1;i<=n;i++)
- for (int j=1;j<=m;j++)
- {
- int val;scanf("%d",&val);
- if ((i+j)&1)
- {
- link(s,i*m-m+j,val);
- if (i>1) link(i*m-m+j,i*m-2*m+j,inf);
- if (i<n) link(i*m-m+j,i*m+j,inf);
- if (j>1) link(i*m-m+j,i*m-m+j-1,inf);
- if (j<m) link(i*m-m+j,i*m-m+j+1,inf);
- }
- else link(i*m-m+j,t,val);
- sum+=val;
- }
- while (bfs())
- {
- for (int i=t;i;i--) cur[i]=head[i];
- while (int temp=dfs(s,inf)) ans+=temp;
- }
- printf("%d\n",sum-ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2449524.html