题目链接：

题意：

给你2*n个点，左边n个点每个点都有两条边，求所有完美匹配的边权乘积的和，题目保证至少有一个完美匹配。

题解：

首先我们先找出各个连通块，每个连通块只要度不是为1的话肯定都是为2的。

所以就先用拓扑排序将度为1的点对处理掉，这些点对只有一种选择，然后剩下的就是度为2的连通块。

随便从一个点开始走，沿着边走，肯定能回到起点，这就是一个欧拉回路。

将走的这些边编号，编号为奇数的为一组，编号为偶数的为一组，这两组就是这个连通块的两种匹配方式。

然后将每个连通块的答案都乘起来就行了。

1 #include
      
        2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 using namespace std; 4  5 const int N=6e5+7,P=998244353; 6 int t,n,ed,g[N],v[N*2],nxt[N*2],w[N*2],vis[N*2]; 7 int cnt,in[N],ans,Q[N],hd,tl; 8  9 void adg(int x,int y,int z){
    in[y]++,v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}10 11 inline int go(int x){12     for(int i=g[x];i;i=nxt[i])13         if(!vis[v[i]])return v[i];14     return 0;15 }16 inline int get(int x,int y){
    for(int i=g[x];i;i=nxt[i])if(v[i]==y)return w[i];}17 18 int main(){19     scanf("%d",&t);20     while(t--)21     {22         ed=0,cnt=0,ans=1,hd=1,tl=0,scanf("%d",&n);23         F(i,1,n<<1)g[i]=0,in[i]=0,vis[i]=0;24         int a,b,c,d;25         F(i,1,n)26         {27             scanf("%d%d%d%d",&a,&b,&c,&d);28             adg(i,a+n,b),adg(n+a,i,b);29             adg(i,c+n,d),adg(c+n,i,d);30         }31         F(i,n+1,n<<1)if(in[i]==1)Q[++tl]=i;32         while(hd<=tl)33         {34             int x=Q[hd++],y;35             for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])36                 y=v[i],ans=1ll*ans*w[i]%P;37             vis[x]=vis[y]=1;38             for(int i=g[y];i;i=nxt[i])if(!vis[v[i]])39                 if(--in[v[i]]==1)Q[++tl]=v[i];40         }41         int an[2];42         F(i,1,n)if(!vis[i])43         {44             Q[tl=1]=i,vis[i]=1;45             for(int j=go(i);j;j=go(j))vis[Q[++tl]=j]=1;46             Q[tl+1]=i,an[0]=an[1]=1;47             F(j,1,tl)an[j&1]=1ll*an[j&1]*get(Q[j],Q[j+1])%P;48             ans=1ll*ans*(an[0]+an[1])%P;49         }50         printf("%d\n",ans);51     }52     return 0;53 }