HDU 6073 Matching In Multiplication 思维（拓扑）

传送门：HDU6073

题意：给出一个二分图的两个顶点集合，每个顶点集合的大小为n，输入v1，w1，v2，w2，表示集合U中的i顶点与集合V中的v1，v2顶点相连，且边的权值为w1，w2。求两个集合的所有完备匹配的权值之和。一个完备匹配的权值为该匹配所有边的权值相乘，且数据保证至少存在一个完美匹配。

思路：官方题解说的很明白了：

首先如果一个点的度数为$1$，那么它的匹配方案是固定的，继而我们可以去掉这一对点。通过拓扑我们可以不断去掉所有度数为$1$的点。

那么剩下的图中左右各有$m$个点，每个点度数都不小于$2$，且左边每个点度数都是$2$，而右侧总度数是$2m$，因此右侧只能是每个点度数都是$2$。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。

时间复杂度$O(n)$。

代码：

#include<bits/stdc++.h> #define ll long long #define pb push_back #define fi first #define se second #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define rep(i,x,n) for(int i=x;i<n;i++) #define per(i,n,x) for(int i=n;i>=x;i--) using namespace std; typedef pair<int,int>P; const int MAXN=600010; const int mod = 998244353; int gcd(int a,int b){return b?gcd(b,a%b):a;} int in[MAXN << 1]; struct node{ int v, w; node(){} node(int _v, int _w) : v(_v), w(_w){} }mp[MAXN * 2][10]; ll ans = 0; int q[MAXN << 1]; bool vis[MAXN << 1]; void toposort(int n) { int s = 1, t = 0; for(int i = 1; i <= n; i++) if(in[i] == 1) q[++t] = i; while(s <= t) { int u = q[s++], v; for(int i = 1; i <= mp[u][0].w; i++) { v = mp[u][i].v; if(vis[v]) continue; ans = (ans * mp[u][i].w) % mod; break; } vis[u] = vis[v] = 1; for(int i = 1; i <= mp[v][0].w; i++) { in[mp[v][i].v]--; if(in[mp[v][i].v] == 1) q[++t] = mp[v][i].v; } } } int check(int u) { for(int i = 1; i <= mp[u][0].w; i++) if(!vis[mp[u][i].v]) return mp[u][i].v; return -1; } int get(int u, int v) { for(int i = 1; i <= mp[u][0].w; i++) if(mp[u][i].v == v) return mp[u][i].w; } int main() { int T, n; cin >> T; while(T--) { int u, v, w, c; scanf("%d", &n); ans = 1; for(int i = 1; i <= n; i++) { scanf("%d %d %d %d", &u, &w, &v, &c); in[i] += 2; in[u + n]++; in[v + n]++; mp[i][++mp[i][0].w] = node(u + n, w); mp[i][++mp[i][0].w] = node(v + n, c); mp[u + n][++mp[u + n][0].w] = node(i, w); mp[v + n][++mp[v + n][0].w] = node(i, c); } n <<= 1; toposort(n); int t; for(int i = 1; i <= n; i++) { t = 1; if(vis[i]) continue; u = i; q[t] = u; vis[u] = 1; while(1) { u = check(u); if(u == -1) break; q[++t] = u; vis[u] = 1; } q[t + 1] = i;//将整个环放入队列 ll x, y; x = y = 1; for(int j = 1; j <= t; j += 2) x = (x * get(q[j], q[j + 1])) % mod; for(int j = 2; j <= t; j += 2) y = (y * get(q[j], q[j + 1])) % mod; ans = (ans * (x + y)) % mod; } cout << ans << endl; for(int i = 1; i <= n + n; i++) mp[i][0].w = in[i] = vis[i] = 0; } return 0; }