crazy_cloud's Blog
0%

HDU6073 Matching In Multiplication

Posted on Edited on In

题目大意

给定一个 \(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;
}