HDU 6073 Matching In Multiplication (拓扑排序+搜索 求二分图所有完美匹配价值和)

题目链接

2017多校第四场1007

题目大意

给定一个二分图，集合U和V各有n个点(n ≤ 300000)，集合U的每个点都连出两条边。保证至少有一个完美匹配。对于一个完美匹配，价值是边权之积，要求所有完美匹配的价值和。

分析

拿到这道题一开始就先从二分图匹配的算法去思考，但没想出来OTL。。。 其实可以换个角度思考。 如果一个点的度数为1的话，那么它的匹配方案肯定是固定的，因此我们可以先通过拓扑排序去掉集合V中度数为1的点，对V中度数为1的点都在U中找一个点与之匹配，也将其删除。那么这些对答案ans的贡献为ans*common。 (common为这些唯一确定边权的乘积) 对于拓扑排序后剩下的点，由于集合U中点的度数都为2，集合V中点的度数都≥2，所以集合V的每个点的度数肯定也都为2。由于不存在奇点，所以必是欧拉回路。所以剩下的图由若干个环组成。 而对于每一个环，它的完美匹配只有两种情况，即都间隔取边，设第一种情况的边权乘积为 Xi ，第二种情况的边权乘积为 Yi ，则由乘法分配率可知，这些环对答案的贡献为ans* ∏cnti=1 ( Xi + Yi ) 其中cnt为环数。 综上， ans = common * ∏cnti=1 ( Xi + Yi )

附官方题解：

代码

#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; typedef long long int LL; const int MAXN=900010; const int MAXM=1200010; const int MOD=998244353; struct Edge { int to,next; LL w; }e[MAXM]; int n,edgenum,head[MAXN],ind[MAXN],cnt,node[MAXN],loop[MAXN]; LL common; bool vis[MAXN]; void Add_Edge(int u,int v,LL w) { ind[v]++; e[++edgenum].to=v; e[edgenum].w=w; e[edgenum].next=head[u]; head[u]=edgenum; } void TopoSort()///拓扑去掉所有能唯一确定的配对，找出剩下成环的结点 { queue<int> Q; for (int i=1;i<=2*n;i++) if (ind[i]==1) Q.push(i); while (!Q.empty()) { int u=Q.front(); Q.pop(); vis[u]=true; for (int t=head[u];t!=-1;t=e[t].next) { int v=e[t].to; if (!vis[v]) { LL w=e[t].w; common*=w; common%=MOD; vis[v]=true;/// for (int tt=head[v];tt!=-1;tt=e[tt].next) { int k=e[tt].to; ind[k]--; if (!vis[k]&&ind[k]==1) Q.push(k); } //break； } } } cnt=0; for (int i=1;i<=2*n;i++) if (!vis[i]) node[++cnt]=i;///node[]记录成环的结点 } LL dist(int u,int v)///算u到v的距离 { for (int t=head[u];t!=-1;t=e[t].next) if (e[t].to==v) return e[t].w; return 0; } int next(int u)///找环上与u相邻的一个点 { for (int t=head[u];t!=-1;t=e[t].next) { int v=e[t].to; if (!vis[v]) return v; } return 0; } void Solve() { LL ans=1; for (int i=1;i<=cnt;i++) { int u=node[i];///u为某一个环的第一个结点 if (!vis[u]) { int len=0; vis[u]=true; loop[++len]=u;///loop[]记录一个环 for (int j=next(u);j;j=next(j))///DFS遍历环 { loop[++len]=j; vis[j]=true; } loop[len+1]=loop[1]; LL x=1,y=1; /*间隔取边的两种方案*/ for (int j=1;j<=len;j+=2) x=x*dist(loop[j],loop[j+1])%MOD; for (int j=2;j<=len;j+=2) y=y*dist(loop[j],loop[j+1])%MOD; ans=ans*(x+y)%MOD; } } printf("%I64d\n",ans*common%MOD); } int main() { int T,v1,v2,i; LL w1,w2; scanf("%d",&T); while (T--) { scanf("%d",&n); edgenum=0; memset(head,-1,sizeof(head)); memset(ind,0,sizeof(ind)); for (i=1;i<=n;i++) { scanf("%d%lld%d%lld",&v1,&w1,&v2,&w2); Add_Edge(i,v1+n,w1);///注意二分图的建图 Add_Edge(v1+n,i,w1); Add_Edge(i,v2+n,w2); Add_Edge(v2+n,i,w2); } common=1; memset(vis,false,sizeof(vis)); TopoSort(); Solve(); } return 0; }

总结： 1.这种用拓扑解决匹配问题的思想值得记录 2.注意拓扑排序的BFS写法 3.注意二分图的建图(V中结点的编号为i+n) 4.注意long long型与格式对应符的对应(因为这个不知道WA了多少次。。。)