8.29T2 国际象棋（构造：棋盘拆分成小方阵）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141686046

http://cplusoj.com/d/senior/p/NODSX2303B

暴力显然，因为肯定是从奇点到偶点，所以二分图匹配一下就好

首先我们手模一下，比如（11,11），我们可以手模出一个情况，也就是DInic跑出来的情况：

在这里插入图片描述

看起来很有规律，但却很难分析，那让我们看另一种方法：

在这里插入图片描述

是不是看起来没有什么规律？其实不然：

在这里插入图片描述

是了！这种拆分方式好像分成了一个个方阵，而方阵之间是独立的！

更厉害的是，只有右下角会有1个0，其他都没有0

更厉害的是，其他方阵至少有1条边长为4，而手玩一下边长为4的方阵是无敌的！

那我们就做完了！直接按4来划分。最后如果余1或余2就很前面或左边的合并一下即可

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1010
int n, m, i, j, k, T;
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; 
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 
int TOT, l1, l2; 
struct node {
	int xi, xj, yi, yj; 
};
vector<node> V[10][10], Ans; 
int a[N][N]; 

namespace Flow {
	#define int long long
	struct mf_graph {
		struct node {
			int x, y, z, n; 
		}; 
		vector<node>d; 
		vector<int>h, H, dep; 
		queue<int>q; 
		int k; 
		int u, v, w, S, T, ans=0; 
		void reset(int n) {
			h.clear(); d.clear(); H.clear(); dep.clear(); 
			h.resize(n+5); k=1; d.resize(2); 
			H.resize(n+5); dep.resize(n+5); 
		}
		void cun(int x, int y, int z) {
			++k; d.pb({x, y, z, h[x]}); 
			d[k].n=h[x]; h[x]=k;
		}
		void print(int n, int m) {
			for(auto t : d) if(t.x && t.y && !t.z) {
				if(t.x == S || t.y == S || t.x == T || t.y == T) continue; 
				int xi = t.x / m + 1, xj = t.x % m; if(xj == 0) --xi, xj = m; 
				int yi = t.y / m + 1, yj = t.y % m; if(yj == 0) --yi, yj = m; 
				if((xi + xj) & 1) {
					V[n][m].pb({xi, xj, yi, yj}); 
//					printf("%lld %lld %lld %lld\n", xi, xj, yi, yj); 
				}
			}
		}
		void add_edge(int x, int y, int z) {
			cun(x, y, z); cun(y, x, 0); 
		}
		int bfs() {
			while(!q.empty()) q.pop(); 
			fill(dep.begin(), dep.end(), -1); 
			h=H; 
			dep[S]=1; q.push(S); 
			while(!q.empty()) {
				u=q.front(); q.pop(); 
				for(int g=h[u]; g; g=d[g].n) {
					v=d[g].y; w=d[g].z; 
					if(w<=0 || dep[v]!=-1) continue; 
					dep[v]=dep[u]+1; q.push(v); 
				}
			}
			return dep[T]!=-1; 
		}
		int dfs(int x, int w) {
			if(x==T) return w;
			if(!w) return 0; 
			int ans=0, s; 
			for(int &i=h[x]; i; i=d[i].n) {
				int y=d[i].y, z=d[i].z;  
				if(dep[y]!=dep[x]+1) continue; 
				if(z<=0) continue; 
				s=dfs(y, min(w, z)); ans+=s; w-=s; 
				d[i].z-=s; d[i^1].z+=s; 
				if(!w) break;  
			}
			return ans; 
		}
		int flow(int SS, int TT) {
			S=SS; T=TT; H=h; ans=0; 
			while(bfs()) ans+=dfs(S, 1e18); 
			return ans; 
		}
	}; 	
	#undef int
}
using namespace Flow; 
int SS, TT, x, y; 

int zh(int x, int y) {
	return (x - 1) * m + y; 
}

void print(int bn, int bm, int n, int m, int o = 0) {
	for(auto t : V[n][m]) {
		int xi = t.xi + bn - 1, xj = t.xj + bm - 1, yi = t.yi + bn - 1, yj = t.yj + bm - 1; 
		a[xi][xj] = a[yi][yj] = ++TOT; 
		if(o) Ans.pb({xi, xj, yi, yj}); 
		if(!o) printf("%d %d %d %d\n", xi, xj, yi, yj); 
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	for(n = 1; n <= 7; ++n)
		for(m = 1; m <= 7; ++m) {
			TOT = 0; 
			mf_graph G; G.reset(n * m + 2); 
			SS = n * m + 1; TT = SS + 1; 
			for(i = 1; i <= n; ++i)	
				for(j = 1; j <= m; ++j) {
					if((i + j) & 1) {
						G.add_edge(SS, zh(i, j), 1); 
						for(k = 0; k < 8; ++k) {
							x = i + dx[k]; y = j + dy[k]; 
							if(x < 1 || y < 1 || x > n || y > m) continue; 
							G.add_edge(zh(i, j), zh(x, y), 1); 
						}
					}
					else G.add_edge(zh(i, j), TT, 1);
				}
			k = G.flow(SS, TT); 
			G.print(n, m); 
		}
	T = read(); 
	while(T--) {
		n = read(); m = read(); Ans.clear(); TOT = 0; 
		if(n == 1 || m == 1) { printf("0\n"); continue; }
		for(i = 1; i <= n; ++i) for(j = 1; j <= m; ++j) a[i][j] = 0; 
		if(n == 2) {
			for(i = 1; i <= m; i += 4) {
				l1 = 4; 
				if(i + 2 > m) continue; 
				if(i + 2 == m) l1 = 3; 
				if(i + 5 >= m) l1 = m - i + 1; 
				print(1, i, 2, l1, 1); 
			}
			printf("%d\n", Ans.size()); 
			for(auto t : Ans) printf("%d %d %d %d\n", t.xi, t.xj, t.yi, t.yj); 
			for(i = 1; i <= n; ++i, debug("\n")) for(j = 1; j <= m; ++j) debug("%3d ", a[i][j]); 
			continue; 
		}
		if(m == 2) {
			for(i = 1; i <= n; i += 4) {
				l1 = 4; 
				if(i + 2 > n) continue; 
				if(i + 2 == n) l1 = 3; 
				if(i + 5 >= n) l1 = n - i + 1; 
				print(i, 1, l1, 2, 1); 
			}
			printf("%d\n", Ans.size()); 
			for(auto t : Ans) printf("%d %d %d %d\n", t.xi, t.xj, t.yi, t.yj); 
			for(i = 1; i <= n; ++i, debug("\n")) for(j = 1; j <= m; ++j) debug("%3d ", a[i][j]); 
			continue; 
		}
		printf("%d\n", n * m / 2); 
		for(i = 1; i <= n; i += 4)
			for(j = 1; j <= m; j += 4) {
				l1 = l2 = 4; 
				if(i + 2 > n) continue; 
				if(j + 2 > m) continue; 
				if(i + 2 == n) l1 = 3; 
				if(j + 2 == m) l2 = 3; 
				if(i + 5 >= n) l1 = n - i + 1; 
				if(j + 5 >= m) l2 = m - j + 1; 
//				debug("[%d %d] (%d %d)\n", i, j, l1, l2); 
				print(i, j, l1, l2); 
			}
		for(i = 1; i <= n; ++i, debug("\n")) for(j = 1; j <= m; ++j) debug("%3d ", a[i][j]); 
	}

	return 0;
}