HDU6073 Matching In Multiplication

题目大意

给定一个$X$部和$Y$部都有$n$个点的带边权二分图,$X$部的每一个点都会和$Y$部的两个不同的点有连边。
对于这个二分图的一个完美匹配,定义它的权重是所有匹配边的边权乘积。
你需要计算这个二分图所有完美匹配的权重之和,答案对$998244353$取模。
题目保证一定存在完美匹配。

$1\leq n\leq 3\times10^5$


题目分析

%Werkeytom_FTD多校时当场切掉
首先我们要转化一下模型:对于$x_i$,如果其连向$y_{i,1}$和$y_{i,2}$,且边权分别是$c_{i,1}$和$c_{i,2}$,那么我们在新的图中连$(y_{i,1},y_{i,2})$边权为$c_{i,2}$,$(y_{i,2},y_{i,1})$边权为$c_{i,1}$。在原图中$x_i$如果匹配了$y_{i,1}$,那么相当于我们选择了$(y_{i,2},y_{i,1})$这一条边,反之亦然。
可以发现我们这样会得到一副$n$个点$n$条无向边(将一对有向边看成一条)的新图,原图的一个完美匹配,其实就对应于新图的一个边定向(一对边中选择一条)方案,这个方案满足所有点的入度都是$1$
由于题目保证一定存在完美匹配,所以这副图的每一个连通块一定都是一棵环套树(如果不是,不可能有满足条件的定向方案)。
然后就很方便了,因为树边一定是唯一定向的,而环有正反两种方案。对于每一个连通块我们都统计出两种方案各自的权重$a$和$b$,答案乘上$a+b$就好了。
时间复杂度$O(n)$。
直接将图看成$2n$个点$2n$条边的环套树可能也可以做?


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int P=998244353;
const int N=300005;
const int E=N<<1;
int last[N],cir[N],pts[N],used[N];
int tov[E],nxt[E],len[E];
bool vis[N];
int T,n,tot,ans;
inline void insert(int x,int y,int z){tov[++tot]=y,len[tot]=z,nxt[tot]=last[x],last[x]=tot;}
int dfs(int x,int e=0)
{
int ret=0;
vis[cir[++cir[0]]=pts[++pts[0]]=x]=1;
for (int i=last[x],y,tmp;i;i=nxt[i])
if (i-1>>1!=e)
{
if (vis[y=tov[i]]) return y;
tmp=dfs(y,i-1>>1);
if (tmp) ret=tmp;
}
if (!ret) cir[cir[0]--]=0;
return ret;
}
void calc(int x)
{
vis[x]=1;
for (int i=last[x],y;i;i=nxt[i])
if (!vis[y=tov[i]]) ans=1ll*ans*len[i]%P,calc(y);
}
void go(int x,int &ret,int cur)
{
for (int i=last[x],y;i;i=nxt[i])
if (used[i-1>>1]!=cur&&!vis[y=tov[i]])
used[i-1>>1]=cur,go(y,ret=1ll*ret*len[i]%P,cur);
}
void clear(){memset(last,0,sizeof last),tot=0;}
int main()
{
freopen("match.in","r",stdin),freopen("match.out","w",stdout);
for (T=read();T--;clear())
{
n=read();
for (int i=1,x,l,y,r;i<=n;++i) x=read(),l=read()%P,y=read(),r=read()%P,insert(x,y,r),insert(y,x,l),used[i]=vis[i]=0;
ans=1;
for (int p=1,cp,a,b;p<=n;++p)
{
if (vis[p]) continue;
cir[0]=pts[0]=0,cp=dfs(p);
for (int i=1;i<=pts[0];++i) vis[pts[i]]=0;
cir[0]=pts[0]=0,dfs(cp);
for (int i=1;i<=pts[0];++i) vis[pts[i]]=0;
for (int i=1;i<=cir[0];++i) vis[cir[i]]=1;
for (int i=1;i<=cir[0];++i) calc(cir[i]);
a=b=0;
for (int i=1;i<=cir[0];++i) vis[cir[i]]=0;
for (int i=last[cp],y;i;i=nxt[i])
if (!vis[y=tov[i]])
if (!a) go(y,a=len[i],used[i-1>>1]=(p<<1)-1);
else go(y,b=len[i],used[i-1>>1]=p<<1);
for (int i=1;i<=cir[0];++i) vis[cir[i]]=1;
ans=1ll*ans*((a+b)%P)%P;
}
printf("%d\n",ans);
}
fclose(stdin),fclose(stdout);
return 0;
}