方格取数问题
题目描述
有一个 \(m\) 行 \(n\) 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。
输入格式
第一行是两个用空格隔开的整数，分别代表方格图的行数 \(m\) 和列数 \(n\)。
第 \(2\) 到第 \((m + 1)\) 行，每行 \(n\) 个整数，第 \((i + 1)\) 行的第 \(j\) 个整数代表方格图第 \(i\) 行第 \(j\) 列的的方格中的数字 \(a_{i, j}\)。
输出格式
输出一行一个整数，代表和最大是多少。
样例 #1
样例输入 #1
3 3
1 2 3
3 2 3
2 3 1
样例输出 #1
11
提示
数据规模与约定
对于 \(100\%\) 的数据，保证 \(1 \leq n, m \leq 100\)，\(1 \leq a_{i, j} \leq 10^5\)。
提示
请注意输入的第一行先读入 \(m\) 再读入 \(n\)。
题解
话说其实转化一下题目，就变成“横行和纵行编号的和为奇数的和相邻的偶数的冲突”，考虑这种冲突问题，求和最大即求割最小，于是我们可以把所有点按上述奇偶分成两边，分别朝\(s\)和\(t\)连边（流量为权值），相邻的点连边，直接跑网络流最小割。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(w>'9'||w<'0'){
if(w=='-')f=-1;
w=getchar();
}
while(w>='0'&&w<='9'){
j=(j<<3)+(j<<1)+w-'0';
w=getchar();
}
return f*j;
}
const int N=20001,M=100001;
int head[N],to[M],fro[M],len[M],tail=1;
int n,m,s,t,cnt,sum[101][101],X[4]={0,0,1,-1},Y[4]={1,-1,0,0};
int dep[N],fir[N],ans;
inline int turn(int x,int y){return (x-1)*m+y;}
inline void addline(int x,int y,int z){
to[++tail]=y;
fro[tail]=head[x];
head[x]=tail;
len[tail]=z;
to[++tail]=x;
fro[tail]=head[y];
head[y]=tail;
return ;
}
bool bfs(){
for(int i=1;i<=cnt;i++)dep[i]=0;
dep[s]=1;
deque<int>p;
p.push_front(s);
while(!p.empty()){
int u=p.front();p.pop_front();
for(int k=head[u];k;k=fro[k]){
int x=to[k];
if(dep[x]||!len[k])continue;
dep[x]=dep[u]+1;
p.push_back(x);
}
}
return dep[t];
}
int dfs(int u,int flo){
if(u==t||!flo)return flo;
int ansn=0;
for(int k=fir[u];k;k=fro[k],fir[u]=k){
int x=to[k];
if(dep[x]<=dep[u]||!len[k])continue;
int j=dfs(x,min(flo,len[k]));
ansn+=j,flo-=j;
len[k]-=j,len[k^1]+=j;
}
return ansn;
}
signed main(){
n=rd(),m=rd();
s=n*m+1,t=cnt=n*m+2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=rd();
ans+=sum[i][j];
if((i+j)&1){
addline(s,turn(i,j),sum[i][j]);
for(int a=0;a<=3;a++){
int x=i+X[a],y=j+Y[a];
if(x<1||x>n||y<1||y>m)continue;
addline(turn(i,j),turn(x,y),INT_MAX);
}
}
else addline(turn(i,j),t,sum[i][j]);
}
}
while(bfs()){
for(int i=1;i<=cnt;i++)fir[i]=head[i];
ans-=dfs(s,INT_MAX);
}
printf("%d",ans);
return 0;
}