「CF859E」Desk Disorder

传送门

Luogu

解题思路

一眼想到二分图：但是求不了最大匹配方案数 oho。

于是考虑这么建图：

直接将一个人可以去的两把椅子连边，然后原图中的2n个点就会形成许多联通块，这个可以分步计数。又因为每个联通块只会是一棵树或是环套树，所以分类讨论一个联通块内如何计数：

若该联通块是一棵树（边数=点数-1），显然方案数就是点数（每次考虑那个点不被匹配即可）
若该联通块是一棵环套树（边数=点数），环上的点只能用环上的点匹配，那么每一棵树的方案固定，环上有两种方案，所以方案数就是2，但是如果环是一个子环 oho ，只有一种方案，因为环上的这个点只有一种匹配方式。

具体实现可以在线加边并用并查集维护联通块大小,联通块的祖先,以及是否成环,最后输出答案即可。

细节注意事项

不要写挂细节啊

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 200010;

const int p = 1000000007;

int n, fa[_], cnt[_], idp[_];

inline int findd(int x)

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

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n);

	for (rg int i = 1; i <= 2 * n; ++i)

		fa[i] = i, cnt[i] = 1, idp[i] = 1;

	int res = 1;

	for (rg int x, y, fx, fy, i = 1; i <= n; ++i) {

		read(x), read(y), fx = findd(x), fy = findd(y);

		idp[fx] = 0;

		if (x == y) continue;

		if (fx == fy) res = 2ll * res % p;

		cnt[fy] += cnt[fx], fa[fx] = fy;

	}

	for (rg int i = 1; i <= 2 * n; ++i)

		if (idp[i]) res = 1ll * res * cnt[i] % p;

	printf("%d\n", res);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF859E」Desk Disorder

解题思路

细节注意事项

参考代码

最新文章

热门文章