HDU-6073 Matching In Multiplication - 2017 Multi-University Training Contest - Team 4(拓扑+连通块处理)
题意：
"完美匹配"被认为是图中所有的点都被匹配的集合内的边所覆盖，一个"完美匹配"的权重是该匹配中所有边权的乘积，而一个"二分图"的权重是图中所有"完美匹配"的求和。
思路：
题目给的是二分图，但有一些限制，所以容易会想从二分图出发处理。实际上被骗了，由于左部的点度数都为2，所以去分析右部的点，发现当其度数等于1时，与其关联的边必选，所以需要以拓扑的思想去除所有这些度数为1的点及其相关联的左部的点及相应的边。然后剩余图就会是一个左部右部点数相同，且所有的点的度数都为2的图。
然后就去寻找图中的连通分量，寻找无向图的连通分量一般是去找点双连通分量，但这题不需要也不适用。事实上剩余图上所有连通的点就是一个连通分量，所以就又转化为了寻找连通块，并在寻找的过程中计算该连通块的方案值。寻找完连通块后，每一个连通块能贡献出两个值，再根据加法的结合率乘法的分解率，得到答案就等于每个连通块的两个值相加和后的乘积，再乘上必须选择的方案值(度数为1的点所造成的)即可。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod = 998244353;
const int maxn = 6e5+5;
struct node
{
LL w;
int v, next;
} edge[maxn*2];
int no, head[maxn];
int bad[maxn], deg[maxn]; //bad记录删除的点，deg记录点的度数
int vis[maxn];
int T, N, NN;
queue<int> q;
vector<int> vtt;
LL ans, must;
inline void init()
{
no = 0;
for(int i = 1; i <= NN; ++i)
vis[i] = bad[i] = deg[i] = 0, head[i]=-1;
}
inline void add(int u, int v, LL w)
{
edge[no].v = v; edge[no].w = w;
edge[no].next = head[u]; head[u] = no++;
}
LL dfs(int cur, int father)
{
vtt.push_back(cur);
vis[cur] = 1;
for(int k = head[cur], kk; k != -1; k = edge[k].next)
{
int v = edge[k].v;
if(v == father) continue;
if(bad[v] || vis[v]) continue;
vis[v] = 1; vtt.push_back(v);
for(kk = head[v]; kk != -1; kk = edge[kk].next)
if(!bad[edge[kk].v] && edge[kk].v != cur) break;
return dfs(edge[kk].v, v)*edge[k].w%mod;
}
return 1;
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d", &T);
while(T--)
{
scanf("%d", &N);
NN = N<<1; init();
for(int i = 1; i <= N; ++i)
{
int v, w;
scanf("%d %d", &v, &w);
add(i, N+v, w); add(N+v, i, w);
++deg[i], ++deg[N+v];
scanf("%d %d", &v, &w);
add(i, N+v, w); add(N+v, i, w);
++deg[i], ++deg[N+v];
}
must = 1; //所有必选边造成的权重
for(int i = 1; i <= N; ++i)
if(deg[N+i] == 1) q.push(N+i);
while(!q.empty())
{
int u = q.front(); q.pop();
bad[u] = 1;
for(int k = head[u]; k != -1; k = edge[k].next)
{
int v = edge[k].v;
if(bad[v]) continue;
must = must*edge[k].w%mod;
bad[v] = 1;
for(int kk = head[v]; kk != -1; kk = edge[kk].next)
{
if(bad[edge[kk].v]) continue;
if(--deg[edge[kk].v] == 1)
q.push(edge[kk].v);
}
}
}
ans = must;
for(int i = 1; i <= N; ++i)
{
//确定左部顶点的一条边便确定了整个连通块的所有边
if(vis[i] || bad[i]) continue;
LL ans1 = 0;
for(int k = head[i], kk; k != -1; k = edge[k].next)
{
int v = edge[k].v;
vtt.clear();
vis[v] = 1;
for(kk = head[v]; kk != -1; kk = edge[kk].next)
if(!bad[edge[kk].v] && edge[kk].v != i) break;
ans1 = (ans1+dfs(edge[kk].v, v)*edge[k].w%mod)%mod;
vis[v] = 0;
for(int j = 0; j < vtt.size(); ++j)
vis[vtt[j]] = 0;
//清空当前连通块的标记，操作另一条边
vtt.push_back(v);
}
for(int j = 0; j < vtt.size(); ++j)
vis[vtt[j]] = 1;
ans = ans*ans1%mod;
}
printf("%lld\n", ans);
}
return 0;
}
继续加油~