题目链接
题意
存在两个点集
U,V
,点集
U
中的每个点均向 V 连出两条带权无向边，选择特定的边能使
U,V
构成一个完全二分图。定义一个完全二分图的值为其所有边权值的乘积，求解
U,V
能构成的所有完全二分图的值的和。
分析
注意到要构成完全二分图，即每个点要且仅被一条边所连接。所以考虑度数不确定的点集
V
，对于所有度数为1的点均是仅一种选择，小编采用搜索的方法对所有度数为1的点进行与确认，通过0，1交换的方式鉴别对应边是否肯定会被选中。递归的去除完所有度数为1的点后，剩下的部分必然组成 k 个联通块，同时每个点的度数
≥2
。设剩余
m
个点，点集 U 中的每个点度数为2，即剩余
2m
条边，而点集
V
中有 m 个点，且度数
≥2
，显然
V
中每个点的度数也均为2。连通块中所有点的度数均为2，则该联通块必然是一个环，那么构建完全二分图在该联通块中只需要间隔着取边即可，共2中方案。剩下的问题是如何计算，我们发现对于两个联通块，假设其建图后值分别为 a,b 和
c,d
。那么最后的值为
ac+ad+bc+bd=a(c+d)+b(c+d)=(a+b)(c+d)
。故对每个联通块分别计算就能得到最后的答案了。详细不理解的对方可以看代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 300300
#define eps 1e-7
#define lson rt<<1
#define rson rt<<1|1
#define LL long long
const int mod=
998244353;
struct Edge{
int v;
LL w;
Edge(){}
Edge(
int _v,LL _w):v(_v),w(_w){}
};
vector<Edge> edge;
vector<int> g[MAXN*
2];
int deg[MAXN*
2];
int vis[MAXN*
2];
LL cnt[
2];
LL ans;
void addedge(
int u,
int v,LL w){
g[u].push_back(edge.size());
edge.push_back(Edge(v,w));
deg[u]++;
}
void dfs(
int u,
int f,
int flg){
vis[u]=
1;
for(
int i=
0;i<g[u].size();++i){
Edge &e = edge[g[u][i]];
if(vis[e.v])
continue;
deg[e.v]--;
if(flg)
ans=(ans*e.w)%mod;
if(deg[e.v]==
1)
dfs(e.v,u,
1-flg);
}
}
void dfs2(
int u,
int f,
int idx){
for(
int i=
0;i<g[u].size();++i){
Edge &e = edge[g[u][i]];
if(e.v==f || vis[e.v])
continue;
vis[e.v]=
1;
cnt[idx]=(cnt[idx]*e.w)%mod;
dfs2(e.v,u,
1-idx);
}
}
int main(){
int T,n,v;
LL w;
cin>>T;
while(T--){
scanf(
"%d",&n);
edge.clear();
memset(vis,
0,
sizeof(vis));
for(
int i=
1;i<=
2*n;++i){
g[i].clear();
deg[i]=
0;
}
for(
int i=
1;i<=n;++i){
for(
int k=
0;k<
2;++k){
scanf(
"%d %I64d",&v,&w);
v+=n;
addedge(i,v,w);
addedge(v,i,w);
}
}
ans=
1;
for(
int i=n+
1;i<=
2*n;++i)
if(deg[i]==
1)
dfs(i,
0,
1);
for(
int i=
1;i<=
2*n;++i)
if(!vis[i]){
cnt[
0]=cnt[
1]=
1;
dfs2(i,
0,
0);
ans=(ans*(cnt[
0]+cnt[
1]))%mod;
}
printf(
"%I64d\n",ans);
}
}
