牛客挑战赛53E题解 ＆ 带花树学习笔记

登录—专业IT笔试面试备考平台_牛客网

显然就是一个点能和两个坐标距离它（2，0）或（2，1）的点匹配，求最大匹配数。

之前一直以为一般图最大匹配是np的，一直在分析这题有没有什么格点图的特殊性质，结果比赛结束才知道一般图最大匹配有一个叫带花树的算法（很久之前听过但压根没去学这种冷门算法...）

之前一篇贴了带花树板子以及大佬的链接，这里稍微说下个人理解。

带花树思想和匈牙利算法一致，仍然是不断地找增广路，问题在于增广路中会出现奇数个点组成地环，这个东西定义为“花”，即我们把里面的点类似缩连通分量一样缩在一起，可以发现我们可以通过调整花内匹配边的情况，能使得花中匹配情况为恰好一个点（可以是花中任意一点）未匹配，其余点都匹配上。缩花完成后（可能花套花）之后变成一棵树，直接类似匈牙利算法找增广路，找到后把路径上的花依次打开并赋匹配边情况。

不难理解，但是感觉自己去实现要头秃，所以对着网上大佬写的模仿了个板子......（求lca大概是找到花中第一个被搜索到的点（也称花托），并查集维护缩在一个花里的点）

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v, x) for(auto v:x)
#define VI vector<int>
#define VLL vector<ll>
//define double long double
#define all(x) (x).begin(),(x).end()
using namespace std;
const double eps = 1e-10;//1e-12
const int N = 610;
const ll mod = 998244353;//1e9 + 7;

const int dx[] = {0, 0, 1, 1, -1, -1, 2, -2, 2, -2, 2, -2};
const int dy[] = {2, -2, 2, -2, 2, -2, 0, 0, 1, 1, -1, -1};

int tot, m, val[30][30], ans[30][30];
VI adj[N];
int match[N], fa[N], vis[N], pre[N];
queue<int>que;

int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);}

int calc_lca(int x, int y)
{
	static int buk[N];
	static int nw;
	++nw;
	while(1)
	{
		if(x)
		{
			x = find(x);
			if(buk[x] == nw)
				return x;
			buk[x] = nw;
			x = pre[match[x]];
		}
		swap(x, y);
	}
}

void shrink(int x, int y, int lca)
{
	while(find(x) != lca)
	{
		pre[x] = y, y = match[x];
		if(vis[y] == 2)
		{
			vis[y] = 1;
			que.push(y);
		}
		if(find(x) == x)
			fa[x] = lca;
		if(find(y) == y)
			fa[y] = lca;
		x = pre[y];
	}
}

bool aug(int s)
{
	for(int i = 1; i <= tot; i++)
		fa[i] = i;
	memset(vis, 0, sizeof vis);
	memset(pre, 0, sizeof pre);
	while(!que.empty())
		que.pop();
	vis[s] = 1;
	que.push(s);
	while(!que.empty())
	{
		int nw = que.front();
		que.pop();
		trav(nxt, adj[nw])
		{
			if(find(nw) == find(nxt) || vis[nxt] == 2)
				continue;
			if(!vis[nxt])
			{
				vis[nxt] = 2;
				pre[nxt] = nw;
				if(!match[nxt])
				{
					for(int x = nxt, y; x; x = y)
					{
						y = match[pre[x]];
						match[x] = pre[x];
						match[pre[x]] = x;
					}
					return 1;
				}
				vis[match[nxt]] = 1, que.push(match[nxt]);
			}
			else
			{
				int lca = calc_lca(nw, nxt);
				shrink(nw, nxt, lca);
				shrink(nxt, nw, lca);
			}
		}
	}
	return 0;
}

void sol()
{
	int n;
	cin >> n >> m;
	int nx, ny;
	cin >> nx >> ny;
    tot = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			val[i][j] = ++tot;
		}
	}
	for(int i = 1; i <= tot; i++)
		adj[i].clear(), match[i] = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(i == nx && j == ny)
				continue;
			for(int d = 0; d < 12; d++)
			{
				int ni = i + dx[d];
				int nj = j + dy[d];
				if(ni == nx && nj == ny)
					continue;
				//cerr << i << ' ' << j << ' ' << ni << ' ' << nj << '\n';
				if(ni >= 1 && ni <= n && nj >= 1 && nj <= m)
					adj[val[i][j]].pb(val[ni][nj]);
			}
		}
	}
	//int ans = 0;
	for(int i = 1; i <= tot; i++)
	{
		if(!match[i])
			aug(i);
	}
	//cout << ans << '\n';
	int num = 0;
	for(int i = 1; i <= n; i++)
	{	
		for(int j = 1; j <= m; j++)
		{
			int v = match[(i - 1) * m + j];
			if(v == 0)
				ans[i][j] = -1;
			else
			{
				if(v > (i - 1) * m + j)
				{
					++num;
					ans[i][j] = num;
					ans[(v - 1) / m + 1][(v - 1) % m + 1] = num;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--)
	{
		sol();
	}
}