题意： 定义一个二分图的完美匹配的值是当前匹配中所有的边值相乘，而一个图的完美匹配就是所有可能的完美匹配的值的和。
题解： 首先考虑入度为1的点，这样的点肯定会被每一种完美匹配算上，先用拓扑排序的方法把所有的入度为1的点相应的边值乘上，得到rans
接下来需要想到的一点就是，除去入度为1的点，剩下的点都在一个环内，然后对于每个环，匹配的方案都只有两种，那么我们就只要在乘上每个环的rans = rans*（ans[1]+ans[2]）
代码：
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> using namespace std; #define clr(a, b) memset(a, b, sizeof(a)) #define pb(a) push_back(a) #define fir first #define se second #define LL long long #define ll long long typedef pair<int, int> pii; typedef pair<LL, int> pli; typedef pair<LL, LL> pll; const LL inf = 0x3f3f3f3f3f3f3f3f; const int maxn = 300100; double eps = 0.000001; double PI = acos(-1); LL mod = 998244353;; struct node { int p; LL w; node(int p,LL w):p(p),w(w){}; }; vector<node> g[maxn*2]; int n,in[maxn*2],vis[maxn*2]; LL ans[3]; LL ss() { queue<int> q; ll ret = 1; clr(vis,0); for(int i = n+1;i <= n*2;i++) { if(in[i] == 1) q.push(i),vis[i] = 1; } while(!q.empty()) { int u = q.front(); q.pop(); for(node tmp : g[u]) { int v = tmp.p; if(vis[v]) continue; in[v]--; if(in[v] == 1) q.push(v),vis[v] = 1; if(u > n) ret = ret*tmp.w%mod; } } return ret; } void dfs(int u,int mark,int fa,int s) { vis[u] = 1; for(node tmp : g[u]) { int v = tmp.p; if(v == s && v != fa) ans[mark] = ans[mark]*tmp.w%mod; if(vis[v]) continue; ans[mark] = ans[mark]*tmp.w%mod; dfs(v,mark^1,u,s); } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); clr(in,0); for(int i = 0;i <= n*2;i++) g[i].clear(); for(int i = 1;i <= n;i++) { int v1,v2; LL w1,w2; scanf("%d%I64d%d%I64d",&v1,&w1,&v2,&w2); g[i].pb(node(v1+n,w1)); g[i].pb(node(v2+n,w2)); g[v1+n].pb(node(i,w1)); g[v2+n].pb(node(i,w2)); in[i] += 2; in[v1+n]++,in[v2+n]++; } LL rans = ss(); //拓扑排序计算所有入度为1的边值 for(int i = 1;i <= n;i++) { if(!vis[i]) { //遍历每一个环的结果 ans[0] = ans[1] = 1; dfs(i,0,0,i); rans = rans*((ans[0]+ans[1])%mod)%mod; //cout<<ans[0]<<'-'<<ans[1]<<endl; } } printf("%I64d\n",rans); } }