传送门 ↬\looparrowright

题目描述

有一个 mm 行 nn 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

输入格式

第一行是两个用空格隔开的整数，分别代表方格图的行数 mm 和列数 nn。
第 22 到第 (m+1)(m + 1) 行，每行 nn 个整数，第 (i+1)(i + 1) 行的第 jj 个整数代表方格图第 ii 行第 jj 列的的方格中的数字 ai,ja_{i, j}。

输出格式

输出一行一个整数，代表和最大是多少。

输入输出样例

输入 #1

3 3
1 2 3
3 2 3
2 3 1

输出 #1

11

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证 1⩽n,m⩽1001 \leqslant n, m \leqslant 100，1⩽ai,j⩽1051 \leqslant a_{i, j} \leqslant 10^5。

提示

请注意输入的第一行先读入 mm 再读入 nn。

分析

首先明确题意：在一个 m×nm\times n 的方格图中取若干个数，设取出的数组成可重集 S\mathbb S，S\mathbb S 中任意两个数所在放个不能在相邻（共享同一条边），求 S\mathbb S 中所有元素和的最大值。
可以考虑一开始取所有方格，再删除权值和尽量小的方格，使得剩下的方格合法。假设取了方格 xx，与其相邻的四个方格就都不可取了，可以注意到，与其相邻的四个方格的横纵坐标（行为横坐标，列为纵坐标）之和同 xx 的横纵坐标之和相差 11，相差 11 意味着奇偶性不相同。可见，横纵坐标之和的奇偶性相同的两个点一定可以同时选取，而横纵坐标之和不同的两点可能会产生冲突。根据这一特性，可以建立二分图，将横纵坐标之和为偶数的点放入左部，横纵坐标之和为奇数的点放入右部。
二分图问题往往可以用网络流求解。建立超级源点 ss 和超级汇点 tt，ss 向各个左部点连边，边权为对应方格的数字；各个右部点向 tt 连边，边权为对应方格的数字；ss 的出边和 tt 的入边都存在，代表一开始选取所有方格中的数；若割去 ss 的一条入边，那么该边指向的节点所代表的方格就不会被选取。接着在左右两部节点之间建边，左部各个点向其互相冲突的至多四个（上下左右）右部点连边；这时，一定存在从 ss 到 tt 的路径，这条路径一定会包含一对互相冲突的节点，设为 a,ba,b，意味着存在 ss 到 aa 的边和 bb 到 tt 的边，即两个冲突的方格同时被选取；我们的任务是割去一些 ss 的出边和 tt 的入边，使得 ss 和 tt 互不相通，且割去的边的边权要尽量小，这就联想到了最小割。将左右两部之间的边的边权设为 +∞+\infty，该网络最小割即为要舍弃的方格中的数的总和，所有方格中数字的和减去舍弃方格中的数的总和即为答案。
最后，最大流等于最小割，建完图跑一遍 Dinic\text{Dinic} 算法即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P2774
Date: 7/27/2020
Description: Minimum Cut
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_POINT=10023;
const int MAX_EDGE=100024;
const int inf=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
struct E
{
	int to;
	int cap;
	int Next=-1;
}edge[MAX_EDGE];
int head[MAX_POINT],tot;
int s,t;
int depth[MAX_POINT];
int m,n;
void init();
inline void add_edge(int,int,int);
inline int ID(int,int);
bool bfs();
int dfs(int,int);
int Dinic();
int main()
{
	int i,j,k;
	int sum=0;
	cin>>m>>n;
	init();
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			int val;
			scanf("%d",&val);
			sum+=val;
			if((i+j)&1) add_edge(ID(i,j),t,val);//右部
			else//左部
			{
				add_edge(s,ID(i,j),val);
				for(k=0;k<4;k++)
				{
					int x=i+dx[k];//行
					int y=j+dy[k];//列
					if(x<1||x>m||y<1||y>n) continue;
					add_edge(ID(i,j),ID(x,y),inf);
				}
			}
		}
	}
	cout<<sum-Dinic()<<endl;
	return 0;
}
void init()
{
	tot=1;
	memset(head,-1,sizeof(head));
	s=0;
	t=n*m+1;
}
inline int ID(int x,int y) {return (x-1)*n+y;}
inline void add_edge(int u,int v,int cap)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].Next=head[u];
	head[u]=tot;
	//建立反边
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool bfs()
{
	memset(depth,0,sizeof(depth));
	queue<int>q;
	q.push(s);
	depth[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			//残量网络上构建分层图
			if(edge[i].cap&&!depth[y])
			{
				q.push(y);
				depth[y]=depth[x]+1;
				if(y==t) return 1;//汇点可达
			}
		}
	}
	return 0;
}
int dfs(int x,int flow)//当前节点 当前流量
{
	//dfs 返回残量网络上可增广的流量
	if(x==t) return flow;
	int rest=flow;//rest 剩余流量
	int temp;
	for(register int i=head[x];~i&&rest;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(edge[i].cap&&depth[y]==depth[x]+1)
		{
			temp=dfs(y,min(rest,edge[i].cap));
			if(!temp) depth[y]=0;//剪枝 去掉增广完毕的点
			edge[i].cap-=temp;
			edge[i^1].cap+=temp;
			rest-=temp;
		}
	}
	return flow-rest;
}
int Dinic()
{
	int maxflow=0;
	while(bfs()) maxflow+=dfs(s,inf);
	return maxflow;
}

后记

位于第 xx 行，第 yy 列的点的编号为 (x−1)n+y(x-1)n+y；一开始没搞对，导致有一个测试点一直过不去。