洛谷P2774 ：方格取数问题（ 网络流24题 奇偶建图+最小割）

https://www.luogu.org/problemnew/show/P2774

题目描述

在一个有 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

解题思路：

设i和j分别为数的横坐标和纵坐标，把（i+j）%2==1染为黑色，否则染为白色，把黑色点和相邻白色点建边，权值为INF，

源点和黑点建边，权值为黑点的值， 汇点和白点建边， 权值为白点的值，求出最小割后，用所有的点值的和减去最小割。

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
#include <vector>
#define N 12000
using namespace std;
struct edge{
	int v;
	int w;
	int rev;
};

vector<edge>e[N];
int n, m, inf=0x9f9f9f, dis[N], iter[N], a[N][N];

void add(int u, int v, int w)
{
	e[u].push_back(edge{v, w, e[v].size()});
	e[v].push_back(edge{u, 0, e[u].size()-1});
}
void bfs(int s)
{
	int u, v;
	queue<int>q;
	memset(dis, -1, sizeof(dis));
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(v=0; v<e[u].size(); v++)
		{
			edge G = e[u][v];
			if(G.w && dis[G.v]<0)
			{
				q.push(G.v);
				dis[G.v]=dis[u] + 1;
			}
		}
	}
}

int dfs(int s, int t, int f)
{
	if(s==t)
		return f;
	for(int &i=iter[s]; i<e[s].size(); i++)
	{
		edge &G = e[s][i];
		if(G.w>0 && dis[s]<dis[G.v])
		{
			int d=dfs(G.v, t, min(f, G.w));
			if(d>0)
			{
				G.w -= d;
				e[G.v][G.rev].w += d;
				return d;
			}
		}
	}
	return 0;
}

int Dinic(int s, int t)
{
	int d, sum=0;
	while(1)
	{
		bfs(s);
		if(dis[t] == -1)
			return sum;
		memset(iter, 0, sizeof(iter));
		while((d=dfs(s, t, inf)) > 0)
			sum+=d;
	}
}

int main()
{
	int i, j, k, tx, ty, sum;
	int nexts[4][2]={1,0, 0,1, -1,0, 0,-1};
	while(scanf("%d%d", &n, &m)!=EOF)
	{
		sum=0;
		for(i=1; i<=n; i++)
			for(j=1; j<=m; j++)
				scanf("%d", &a[i][j]);
		for(i=1; i<=n; i++)
		{
			for (j=1; j<=m; j++)
			{
				sum+=a[i][j];
				if((i+j)%2==1)
				{
					add(0, (i-1)*m+j, a[i][j]);
					for(k=0; k<4; k++)
					{
						tx=i+nexts[k][0];
						ty=j+nexts[k][1];
						if(tx>0 && ty>0 && tx<=n && ty<=m && (tx+ty)%2==0)
							add((i-1)*m+j, (tx-1)*m+ty, inf);
					}
				}	
				else
					add((i-1)*m+j, n*m+1, a[i][j]);	
			}
		}
		
		printf("%d
", sum - Dinic(0, n*m+1));
	}
	return 0;
}