今天多校的第一锅……
这套题真是神奇，明明都是Claris出的，涉及图论的居然有4道……
而且就这道题来说，有一个卡点真的是很让人觉得奇妙。
题意：
给你一个两边点数相同的二分图，左边的点都会连接右边两个不同的点。
求 每一个完美匹配的边权积 的和。
思路：
真特么神题……
一开始我看到这题，潜意识的想到网络流，看到点数这么多认定不可能是网络流。又通过每个左边集合的点都有两个选择，互相矛盾想到2-sat，但需要输出所有可行解又十分困难。于是我猜测，最多只有两个方案。但是被队友反驳了……最后就没出……
其实基本思路已经对了。的确是求2-sat的所有可行解。但是会有一些优化的地方。
一开始，我们对于右侧的点，如果他的入度为 1 ，那么我们的选择是确定的。用这个方式对整张图进行拓扑排序。最后获得左右两侧都有 m 个点，并且右侧的点的入度都大于等于 2 。
因为此时左侧只有 m 个点了 ，那么左侧的出度和也就是右侧的入度和 就是 2m ，因此右侧的每个点的入度都为 2。
对于这样的图，图中的每一个强联通分量内，他的可行方案的确是两个，自行yy即可。我也证明不来……但十分显然
剩下的就是我们对于每一个强联通分量都有指数次的选择。
这是我在想这道题一直想不出来的卡点……每个强联通分量内都有两个方案，如果有 n 个强联通分量就有 ( 2^{n} ) 个方案，我根本不可能将他们计算出来。当时我是这么想得，许颂嘉也是这么说的
但实际上，我们只要将每个强联通内的两个方案值相加的结果互相乘起来就好了……
比如说 有强联通分量 a b 方案数分别是 a1 , a2 , b1 , b2 。
那么总共的方案就是 ( a1\times b1 + a1 \times b2 + a2 \times b1 + a2 \times b2 )
合并一下就是 ( \left( a1 + a2 \right) \times \left( b1 + b2 \right) )
得解。
AC Code
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
using namespace std;
const int mod = 998244353;
const int maxn = 6e6 + 10;
int idx, n, ans;
int head[maxn], deg[maxn];
bool vis[maxn];
queue<int> que;
struct node {
int to, next, weight;
} edges[maxn << 1];
void addEdge(int u, int v, int w)
{
edges[idx] = (node){ v, head[u], w }, head[u] = idx++;
edges[idx] = (node){ u, head[v], w }, head[v] = idx++;
deg[u]++, deg[v]++;
}
int findNext(int x, int& w)
{
for (int id = head[x]; ~id; id = edges[id].next)
if (!vis[edges[id].to]) {
w = edges[id].weight;
return edges[id].to;
}
return -1;
}
int findEdge(int u, int v)
{
for (int id = head[u]; ~id; id = edges[id].next)
if (edges[id].to == v)
return edges[id].weight;
return 1;
}
int main()
{
int T, v, w;
scanf("%d", &T);
while (T--) {
scanf("%d", &n), n <<= 1, ans = 1, idx = 0;
memset(head, -1, sizeof head);
memset(deg, 0, sizeof deg);
memset(vis, false, sizeof vis);
each(i, n) scanf("%d %d", &v, &w), addEdge(i / 2 + 1, v + n / 2, w);
range(i, n / 2 + 1, n) if (deg[i] == 1) que.push(i);
while (!que.empty()) {
int u = que.front(), v;
que.pop();
for (int id = head[u]; ~id; id = edges[id].next) {
v = edges[id].to;
if (!vis[v]) {
vis[u] = vis[v] = true;
ans = ans * 1LL * edges[id].weight % mod;
break;
}
}
for (int id = head[v]; ~id; id = edges[id].next)
if (!vis[u = edges[id].to] && --deg[u] == 1)
que.push(u);
}
range(i, 1, n) if (!vis[i])
{
int a = 1, b = 1, id = 1, cur, pre = i;
vis[i] = true;
for (cur = findNext(i, w); ~cur; cur = findNext(cur, w)) {
que.push(w);
vis[cur] = true;
pre = cur;
}
que.push(findEdge(pre, i));
while (!que.empty()) {
id& 1 ? a = a * 1LL * que.front() % mod : b = b * 1LL * que.front() % mod;
id++;
que.pop();
}
ans = ans * 1LL * (a + b) % mod;
}
printf("%d\n", ans);
}
return 0;
}