Description 给出一个2n个点的二分图，左边一排点每个点出度为2连向右边n个点，保证存在完美匹配，问所有完美匹配的边权乘积之和 Input 第一行一整数T表示用例组数，每组用例首先输入一整数n表示二分图一排点的点数，之后n行第i行给出四个整数v1,w1,v2,w2表示左边第i个点连向右边的v1和v2，边权分别为w1,w2 (1<=T<=15,1<=n<=3e5,1,=w1,w2<=1e9) Output 对于每组用例，输出所有完美匹配边权乘积之和 Sample Input 1 2 2 1 1 4 1 4 2 3 Sample Output 16 Solution 考虑右边的点u，如果其入度为1，那么在所有完美匹配中该点都是与这条边的另一个端点v匹配，所以可以直接把这条边边权乘到答案中，然后v的另一条边就没有用了，直接删掉，把这条边另一个端点的入度减一，如此处理掉所有入度为1的点，那么左右两边点数应该相同，设为m，左边点出度为2m则右边点入度也为2m，而每个点的入度至少为2且完美匹配存在，故每个点的入度均为2，对于一个连通块，固定一条边就会固定一个完美匹配，剩下的边也可以构成另一个完美匹配，且该连通块只有这两种完美匹配，把这两个匹配的边权乘积加起来乘到答案里即可 Code
#include<cstdio> #include<cstring> #include<queue> using namespace std; namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror=0; inline char nc() { static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch=='\n'||ch=='\r'||ch=='\t'; } inline void read(int &x) { char ch; while(blank(ch=nc())); if(IOerror)return; for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0'); } #undef BUF_SIZE }; using namespace fastIO; typedef long long ll; typedef pair<int,int>P; const int maxn=600005,mod=998244353; struct node { int v,next,w; }e[maxn<<1]; int T,n,head[maxn],tot,du[maxn],vis[maxn<<1]; void add(int u,int v,int w) { e[tot].v=v,e[tot].w=w,e[tot].next=head[u],head[u]=tot++; } int main() { read(T); while(T--) { read(n); tot=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(du,0,sizeof(du)); for(int i=1;i<=n;i++) { int v,w; for(int j=0;j<2;j++) { read(v),read(w); v+=n; du[v]++; add(i,v,w),add(v,i,w); } } queue<int>que; for(int i=n+1;i<=2*n;i++) if(du[i]==1)du[i]=0,que.push(i); int ans=1; while(!que.empty()) { int u=que.front();que.pop(); int v; for(int i=head[u];~i;i=e[i].next) if(!vis[i]) { vis[i]=vis[i^1]=1,ans=(ll)ans*e[i].w%mod,v=e[i].v; break; } for(int i=head[v];~i;i=e[i].next) if(!vis[i]) { vis[i]=vis[i^1]=1,u=e[i].v; break; } du[u]--; if(du[u]==1)du[u]=0,que.push(u); } for(int i=n+1;i<=2*n;i++) if(du[i]==2) { int sum1=1,sum2=1; int u=i,v; do { du[u]=0; for(int i=head[u];~i;i=e[i].next) if(!vis[i]) { vis[i]=vis[i^1]=1,v=e[i].v,sum1=(ll)sum1*e[i].w%mod; break; } for(int i=head[v];~i;i=e[i].next) if(!vis[i]) { vis[i]=vis[i^1]=1,u=e[i].v,sum2=(ll)sum2*e[i].w%mod; } }while(u!=i); ans=(ll)ans*(sum1+sum2)%mod; } printf("%d\n",ans); } return 0; }