http://acm.hdu.edu.cn/showproblem.php?pid=6073 给定一个二分图，左侧每个点都有两条边 求你他所有完美匹配 中各边之积的和。 1 先找右边只有一个边连接的，这种点肯定只有一种，并且这种关系会影响下一个，所以我们用topsort来弄，剩下的都是环了。 而对于环，若想完成完全匹配（顶点完全覆盖），则需要间隔的取边（画图发现qwq） 计算的过程是根据乘法原理qwq 错了20多次，因为在dfs的过程中的取余的过程中错了55 一直tle 因为点比较多，用邻接表也超时了qwq
#include <bits/stdc++.h> /* 1 topsort 判定度数为1的情况。 2 然后k环，k个集合。 每一个求多重集 */ using namespace std; typedef long long ll; const long long mod=998244353; const int maxn=3e5+100; struct Node{ int from; int to; ll cost; int next; int bh;//给每个边标号，因为我发现记录点无法完成。 Node(){}; Node(int _a,int _b,int _c){to=_a;cost=_b;bh=_c;}; }; int len; Node node[maxn*5]; int head[maxn*2]; void add(int a,int b,int c,int d){ node[len].from=a; node[len].to=b; node[len].cost=c; node[len].bh=d; node[len].next=head[a]; head[a]=len++; } ll cc[2]; bool vis[maxn*4]; bool vis2[maxn*2]; int du[maxn*2]; void dfs(int pre,int use){ vis2[pre]=true; for(int i=head[pre];i!=-1;i=node[i].next){ int s=node[i].to; int sss=node[i].bh; if(vis[sss]) continue; cc[use]=(cc[use]*node[i].cost)%mod;// // 错误的 方法是 先计算cc 在取模，这样在取模前可能已经超时了 //cout<<use<<"!!"<<cc[use]<<endl; while(cc[use]>mod) cc[use]-=mod; if(!vis[sss]){ vis[sss]=true; vis[sss^1]=true; dfs(s,1-use); } } } int main() { //freopen("f:\\ttt\\data.txt","r",stdin); //freopen("f:\\ttt\\out2.txt","w",stdout); int m; int t; int a; ll b; scanf("%d",&t); while(t--){ scanf("%d",&m); int cnt=0; memset(head,-1,sizeof(head)); len=0; memset(du,0,sizeof(du)); memset(vis,false,sizeof(vis)); memset(vis2,false,sizeof(vis2)); for(int i=1;i<=m;i++){ scanf("%d%lld",&a,&b); //G[i].push_back(Node(a+m,b,cnt++)); add(i,a+m,b,cnt++); add(a+m,i,b,cnt++); //G[a+m].push_back(Node(i,b,cnt++)); du[i]++,du[a+m]++; scanf("%d%lld",&a,&b); //G[i].push_back(Node(a+m,b,cnt++)); //G[a+m].push_back(Node(i,b,cnt++)); add(i,a+m,b,cnt++); add(a+m,i,b,cnt++); du[i]++,du[a+m]++; } //cout<<"??????"<<endl; queue<int>q; for(int i=1;i<=m*2;i++){ if(du[i]==1){ q.push(i); vis2[i]=true; } } ll ans=1; while(!q.empty()){ int u=q.front(); q.pop(); vis2[u]=true; for(int i=head[u];i!=-1;i=node[i].next){ int v=node[i].to; int bc=node[i].bh; if(vis[bc]) continue; if(vis2[v]) continue; while(node[i].cost>mod) node[i].cost-=mod; ans=(ans*node[i].cost)%mod; while(ans>mod) ans-=mod;//取模 vis[bc]=true; vis[bc^1]=true; vis2[v]=true; for(int j=head[v];j!=-1;j=node[j].next){ int vv=node[j].to; int bbh=node[j].bh; du[vv]--; vis[bbh]=true; vis[bbh^1]=true; if(du[vv]==1){ q.push(vv); vis2[vv]=true; } } } } //cout<<ans<<endl; int sum=0; for(int i=1;i<=2*m;i++){ cc[0]=1;cc[1]=1; if(!vis2[i]){ dfs(i,0); //if(cc[0]+cc[1]!=0) ans=(ans*(cc[0]+cc[1])%mod)%mod; while(ans>mod) ans-=mod; } //cout<<"过程"<<cc[0]<<" "<<cc[1]<<endl; //cout<<"过程中的ans:"<<ans<<endl; } printf("%lld\n",ans); } return 0; }