ACM模版
描述
题解
这是我做过的为数不多的二分图的问题中最有趣的一道了，首先确定的是左边的点和右边的点集数目是一样的，另外，我们确定左边的每个点向右边的点伸出两条路，那么，我们可以知悉，左边的点的度全部为
2
，因为至少有一个完美匹配，所以右边的点度数全部大于等于 1。那么此时，我们可以首先对右边点的度数为
1
的进行删点，删边，还有对应连边的左边的点，为什么呢？因为当度数为 1 时，路径是固定的，我们可以直接去掉，只考虑路径不唯一的，所以左右两边各删除
x
个点，那么两边都剩下 y 个点，并且右边的度数全部大于
1
，这时，因为我们知道左边的点的度数一定是 2y，右边当然也是，所以可以肯定右边所有点的度数也是
2
<script type="math/tex" id="MathJax-Element-598">2</script>，那么，很明显的是，只有两种方案，问题也就没什么了，差不多解决了。
给大家提供一下官方题解参考，大同小异：
这个题必须赞一下，思维十分紧凑的一个题，好题！！！
代码
const
int MAXN =
3e5 *
2 +
10;
const
int MOD =
998244353;
int n, cnt;
int q[MAXN];
int hed[MAXN];
int deg[MAXN];
int v[MAXN <<
1];
int val[MAXN <<
1];
int nxt[MAXN <<
1];
bool vis[MAXN];
inline void add(
int x,
int y,
int z)
{
deg[
x]++;
deg[
y]++;
v[++cnt] =
y;
val[cnt] = z;
nxt[cnt] = hed[
x];
hed[
x] = cnt;
v[++cnt] =
x;
val[cnt] = z;
nxt[cnt] = hed[
y];
hed[
y] = cnt;
}
inline
int go(
int x)
{
for (
int i = hed[
x]; i; i = nxt[i])
{
if (!vis[v[i]])
{
return v[i];
}
}
return 0;
}
inline
int get(
int x,
int y)
{
for (
int i = hed[
x]; i; i = nxt[i])
{
if (v[i] ==
y)
{
return val[i];
}
}
return 0;
}
void init()
{
cnt =
0;
int x = n <<
1;
for (
int i =
1; i <=
x; i++)
{
hed[i] = deg[i] = vis[i] =
0;
}
}
int main()
{
// freopen(
"/Users/zyj/Desktop/input.txt",
"r", stdin);
int T;
scanf(
"%d", &T);
while (T--)
{
scanf(
"%d", &n);
init();
int y, w;
for (
int i =
1; i <= n; i++) //
1 ~ n U n+
1 ~
2n V
{
scanf(
"%d%d", &
y, &w);
add(i,
y + n, w);
scanf(
"%d%d", &
y, &w);
add(i,
y + n, w);
}
n <<=
1;
int t =
0;
for (
int i = (n >>
1) +
1; i <= n; i++)
{
if (deg[i] ==
1)
{
q[++t] = i;
}
}
int ans =
1, h =
1;
while (h <= t)
{
int u =
q[h++], w =
0;
for (
int i = hed[u]; i; i = nxt[i])
{
if (!vis[v[i]])
{
w = v[i];
ans =
1LL * ans * val[i] % MOD;
break;
}
}
vis[u] = vis[w] =
1;
for (
int i = hed[w]; i; i = nxt[i])
{
u = v[i];
if (!vis[u])
{
deg[u]--;
if (deg[u] ==
1)
{
q[++t] = u;
}
}
}
}
for (
int i =
1; i <= n; i++)
{
if (!vis[i])
{
vis[
q[t = 1] = i] =
1;
for (
int j = go(i); j; j = go(j))
{
vis[
q[++t] = j] =
1;
}
q[t + 1] =
q[1];
y = w =
1;
for (
int j =
1; j <= t; j +=
2)
{
y =
1LL *
y * get(
q[j],
q[j + 1]) % MOD;
}
for (
int j =
2; j <= t; j +=
2)
{
w =
1LL * w * get(
q[j],
q[j + 1]) % MOD;
}
ans =
1LL * ans * (
y + w) % MOD;
}
}
printf(
"%d\n", ans);
}
return 0;
}
