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

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

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

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

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

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

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

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

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

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

#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 longstruct 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 LOCALfreopen("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;
}