二分图+生成树构造：留下一条边：AT_arc119_d

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

https://www.luogu.com.cn/problem/AT_arc119_d

首先，我们可以发现，同行和同列的红色格子会相互影响。因此我们可以考虑连边。这里我们容易想到两种连边方式：

红色格子之间连边。
位于 $(i,j)$ 的红色格子，把第 $i$ 行和第 $j$ 列连边。

考虑第一种连边方式。一条边的意义是什么？一行还是一列？如果是表示一行或者一列，那么这行有多个红色格子又要如何体现？我们发现这种连边方式无法解释。

因此我们考虑另一种连边方式：行向列连边。这种连边就容易理解多了。一条边代表一个红点，它的意义是可以用它来消去两边其中一个点，也就是消去一行和一列。但这个东西看起来又有点怪怪的，因为与我们还要考虑红色点之间会互相影响。我们再重新考虑一下。一条边能去删一个点的前提条件应该是左右两边的点都还没被删。

这里其实我们可以换一种理解方式，我们删除一个边和对应的点，同时删除这个点连出去的所有边。

通过这种理解方式，我们就可以确定删红点数量的上界。我们这里对连通块进行分块考虑。对于一个 $k$ 个点的连通块，我们最多可以操作 $k-1$ 次。每次操作可以删掉一行和一列。也就是这个连通块恰好剩下一行或者一列没有被删。

显然对于每个连通块都满足。但对于剩下的，我们是删行还是删列呢？我们可以先把其他删掉，然后剩下 $W$ 行 $H$ 列。如果行多，那么我们删列优。如果列多，我们删行更优。

因此我们现在求出了最优答案了。显然考虑方案。

观察上面那个形式像什么。 $k$ 个点， $k-1$ 条边，这形成了一棵树。同时这棵树一个是一个二分图。我们从叶子开始每条边删掉下面那个点即可。最后留下一对白点和黑点，我们就按照上面贪心的方法来删。

至于如何得到一棵合法的生成树，根据上面的构造方案，显然每个生成树都是合法的。因此问题得以解决。

#define pb push_back
#define fi first
#define se second
#define N 2510
struct node {
	int x; pair<int, int>p; 
};
vector<node>G[N<<1]; 
int f[N<<1]; 
char str[N], c; 
int n, m, i, j, k, T, ans, tot, H, W;
pair<int, int>V[N<<1]; 

int fa(int x) {
	if(f[x] == x) return x; 
	return f[x] = fa(f[x]); 
}

void add_edge(int u, int v) {
	if(fa(u) == fa(v)) return ; 
	f[fa(u)] = fa(v); ++ans; 
	G[u].pb({v, {i, j}}); G[v].pb({u, {i, j}}); 
}

void dfs(int x, int fa) {
	for(auto t : G[x]) if(t.x != fa) {
		int y = t.x, flg=0; 
		if(!V[tot].fi) V[tot] = {t.p.fi, t.p.se}, flg=1; 
		dfs(y, x); 
		if(flg) continue; 
		else if(y<=n) printf("X %d %d\n", t.p.fi, t.p.se), --H; 
		else printf("Y %d %d\n", t.p.fi, t.p.se), --W; 
	}
}

int main()
{
	n=H=read(); m=W=read(); 
	for(i=1; i<=n+m; ++i) f[i]=i; 
	for(i=1; i<=n; ++i) {
		scanf("%s", str+1); 
		for(j=1; j<=m; ++j) 
			if(str[j] == 'R') add_edge(i, j + n); 
	}
	printf("%d\n", ans); 
	for(i=1; i<=n+m; ++i) if(fa(i) == i && G[i].size()) {
		++tot; dfs(i, 0); 
	}
	c = (W < H ? 'Y' : 'X'); 
	for(i=1; i<=tot; ++i) printf("%c %d %d\n", c, V[i].fi, V[i].se); 
	return 0;
}