HDU-6073: Matching In Multiplication

拓扑排序

Problem Description

In the mathematical discipline of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. A matching in a graph is a set of edges without common vertices. A perfect matching is a matching that each vertice is covered by an edge in the set.

Little Q misunderstands the definition of bipartite graph, he thinks the size of U is equal to the size of V, and for each vertex p in U, there are exactly two edges from p. Based on such weighted graph, he defines the weight of a perfect matching as the product of all the edges' weight, and the weight of a graph is the sum of all the perfect matchings' weight.

Please write a program to compute the weight of a weighted ''bipartite graph'' made by Little Q.

Input

The first line of the input contains an integer$T(1≤T≤15)$, denoting the number of test cases.

In each test case, there is an integer$n(1≤n≤300000)$ in the first line, denoting the size of U. The vertex in U and V are labeled by $1,2,...,n$.

For the next n lines, each line contains 4 integers $v_{i,1},w_{i,1},v_{i,2},w_{i,2}(1≤v_i,j≤n,1≤w_i,j≤10^9)$, denoting there is an edge between $U_i$ and $V_{vi,1}$, weighted $w_{i,1}$, and there is another edge between $U_i$ and $V_{vi,2}$, weighted $w_{i,2}$.

It is guaranteed that each graph has at least one perfect matchings, and there are at most one edge between every pair of vertex.

Output

For each test case, print a single line containing an integer, denoting the weight of the given graph. Since the answer may be very large, please print the answer modulo 998244353.

Sample Input

1
2
2 1 1 4
1 4 2 3

Sample Output

16

题意：给你一个二分图，左边为U，右边为V，输入一个n，表示U和V集合里分别有n个点，接下来n行，每行四个数，$v_1，w_1，v_2，w_2$，该行为第i行，表示$U_i$和$V_{v1}$相连，边权为$w_1$，$U_i$和$V_{v2}$相连，边权为$w_2$。那么也就是说，U集合中的每个点的度都为2，V集合不确定。将连线方案的边权相乘得到一个值，求所有方案的值的和为多少。

分析：首先找出V集合中度为1的点，那么它就只有一种连线，不断拓扑下去，将所有度为1的点都连好之后，剩下所有点的度都为2了，那么U和V连接一定能形成若干个简单环，每个环就有两种方案（间隔选取边）。

• 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 6e5 + 10;
const int mod = 998244353;
int in[maxn], n, f;
int vis[maxn];
LL ans[2];
struct node
{
    int to, len;
    node (int to = 0, int len = 0) : to (to), len (len) {}
};
vector<node> V[maxn];
queue<int> q;
LL topsort()
{
    LL ans = 1;
    for (int i = n + 1; i <= 2 * n; i++)
        if (in[i] == 1)
        {
            vis[i] = 1;
            q.push (i);
        }
    while (!q.empty() )
    {
        int u = q.front();
        q.pop();
        vis[u] = 1, in[u]--;
        for (int i = 0; i < V[u].size(); i++)
        {
            int v = V[u][i].to;
            if (vis[v]) continue;
            if (u > n) ans = ans * (LL) V[u][i].len % mod;
            in[v]--;
            if (in[v] == 1) q.push (v);
        }
    }
    return ans;
}
void dfs (int rt, int fa, int u, int f)
{
    vis[u] = 1;
    int flag = 0;
    for (int i = 0; i < V[u].size(); i++)
    {
        int v = V[u][i].to;
        int len = V[u][i].len;
        if (v == rt && v != fa) ans[f] = ans[f] * (LL) len % mod;
        if (vis[v]) continue;
        flag = 1;
        ans[f] = ans[f] * (LL) len % mod;
        dfs (rt, u, v, f ^ 1);
    }
}
void clr()
{
    memset (in, 0, sizeof (in) );
    memset (vis, 0, sizeof (vis) );
    while (!q.empty() ) q.pop();
    for (int i = 0; i <= n * 2; i++)
        V[i].clear();
}
int main()
{
    int t;
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d", &n);
        clr();
        for (int u = 1; u <= n; u++)
        {
            int v1, len1, v2, len2;
            scanf ("%d %d %d %d", &v1, &len1, &v2, &len2);
            in[v1 + n]++, in[v2 + n]++, in[u] = 2;
            V[u].push_back (node (v1 + n, len1) );
            V[u].push_back (node (v2 + n, len2) );
            V[v1 + n].push_back (node (u, len1) );
            V[v2 + n].push_back (node (u, len2) );
        }
        LL ans1 = topsort();
        for (int i = 1; i <= 2 * n; i++)
        {
            if (vis[i]) continue;
            ans[0] = ans[1] = 1;
            dfs (i, 0, i, 0);
            ans1 = (ans1 * ( (ans[0] + ans[1]) % mod) ) % mod;
        }
        printf ("%lld\n", ans1);
    }
}