「网络流 24 题」方格取数
题解:对每个点进行染色,将第一个染为黑色,然后相邻的为白色,这样交替染色然后将整个方格分成黑白两种不同的颜色,从源点向每个白色的方块连容量为权值的边,从黑色向汇点连接容量为权值的边,从白色的向相邻的黑色的点连容量为无穷大的边,跑最大点权独立集
#include <bits/stdc++.h>
const int MAXN = 1000000,INF = 10000000;
const int fx[] = {1,-1,0,0},fy[]={0,0,1,-1};
using namespace std;
int n,m,s,t,e = 2,sum;
int d[MAXN],cur[MAXN],head[MAXN],data[100][100];
bool b[100][100];
struct node{
int v,c,f,next;
}edge[MAXN];
inline void addedge(int u,int v,int w){
edge[e] = (node){v,w,0,head[u]};head[u] = e++;
edge[e] = (node){u,0,0,head[v]};head[v] = e++;
}
inline bool check(int x,int y){
if(x < 1 || x > m) return false;
if(y < 1 || y > n) return false;
return true;
}
inline void init()
{
scanf("%d%d",&m,&n);
s = 0;t = m * n + 1;
for(int i = 1;i <= m;i++)
for(int j = 1;j <= n;j++){
scanf("%d",&data[i][j]);
sum += data[i][j];
}
b[1][1] = 1;
for(int i = 1;i <= m;i++)
for(int j = 1;j <= n;j++){
if(j == 1 && i != 1) b[i][j] = b[i-1][j] ^ 1;
else b[i][j] = b[i][j-1] ^ 1;
}
for(int i = 1;i <= m;i++)
for(int j = 1;j <= n;j++)
if(b[i][j]) addedge(s,(i-1)*n+j,data[i][j]);
else addedge((i-1)*n+j,t,data[i][j]);
for(int i = 1;i <= m;i++)
for(int j = 1;j <= n;j++)
for(int k = 0;k <= 3;k++)
if(check(i+fx[k],j+fy[k])&&b[i][j])
addedge((i-1)*n+j,(i+fx[k]-1)*n+j+fy[k],INF);
}
queue<int>Q;
inline bool bfs(){
memset(d,0,sizeof(d));
d[s] = 1;Q.push(s);
while(!Q.empty()){
int x = Q.front();Q.pop();
for(int i = head[x];i;i = edge[i].next){
node E = edge[i];
if(!d[E.v] && E.c > E.f){
d[E.v] = d[x] + 1;
Q.push(E.v);
}
}
}
return d[t] ? true : false;
}
int dfs(int x,int a){
if(x == t || a == 0) return a;
int flow = 0,f;
for(int &i = cur[x];i;i = edge[i].next){
node &E = edge[i];
if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c - E.f,a))) > 0){
E.f += f;
edge[i^1].f -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
inline int max_flow(){
int flow = 0;
while(bfs()){
for(int i = s;i <= t;i++) cur[i] = head[i];
flow += dfs(s,INF);
}
return flow;
}
int main()
{
init();
sum -= max_flow();
printf("%d\n",sum);
return 0;
}