方格取数(2) |
| Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 68 Accepted Submission(s): 33 |
| Problem Description给你一个m*n的格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。 |
| Input包括多个测试实例，每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50) |
| Output 对于每个测试实例，输出可能取得的最大的和 |
Sample Input
3 3
|
Sample Output
188
|
| Authorailyanlu |
| SourceHappy 2007 |
代码：
//类似于二分图中求最大独立集，但这里带权值。看成二分图，把点数换成奇偶数，(x+y为奇/偶)，
//因为奇数和偶数相邻不能同时取，我们把相互冲突的做边(权值为无穷大)，左边加一个源点
//连接所有奇数，右边加一个汇点连接所有偶数(权值为点权值,建边时边的方向要一致)，就有了
//最大流模型，最大流求出来的就是最小点权覆盖。二分图中 最大独立集=总点数-最小点覆盖(最
//大匹配)；类似 最大点权独立集=总点权值-最小点权覆盖
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=,inf=0x7fffffff;
struct edge{
int from,to,cap,flow;
edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct dinic{
int n,m,s,t;
vector<edge>edges;
vector<int>g[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];
void init(int n){
this->n=n;
for(int i=;i<n;i++) g[i].clear();
edges.clear();
}
void addedge(int from,int to,int cap){
edges.push_back(edge(from,to,cap,));
edges.push_back(edge(to,from,,));//反向弧
m=edges.size();
g[from].push_back(m-);
g[to].push_back(m-);
}
bool bfs(){
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);
d[s]=;
vis[s]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=;i<(int)g[x].size();i++){
edge&e=edges[g[x][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to]=;
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t||a==) return a;
int flow=,f;
for(int&i=cur[x];i<(int)g[x].size();i++){
edge&e=edges[g[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>){
e.flow+=f;
edges[g[x][i]^].flow-=f;
flow+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int maxflow(int s,int t){
this->s=s;this->t=t;
int flow=;
while(bfs()){
memset(cur,,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
}dc;
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)==){
int sum=,tmp[][];
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
scanf("%d",&tmp[i][j]);
sum+=tmp[i][j];
}
dc.init(n*m+);
int s=,t=n*m+;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
int nu=(i-)*n+j;
if((i+j)%){
dc.addedge(s,nu,tmp[i][j]);
if(i>) dc.addedge(nu,nu-n,inf);
if(i<m) dc.addedge(nu,nu+n,inf);
if(j>) dc.addedge(nu,nu-,inf);
if(j<n) dc.addedge(nu,nu+,inf);
}
else dc.addedge(nu,t,tmp[i][j]);
}
int x=dc.maxflow(s,t);
printf("%d\n",sum-x);
}
return ;
}
