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 vi,1,wi,1,vi,2,wi,2(1≤vi,j≤n,1≤wi,j≤109), denoting there is an edge between Ui and Vvi,1, weighted wi,1, and there is another edge between Ui and Vvi,2, weighted wi,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 ，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。 但是小Q错误的理解了二分图的定义，以为二分图的两个顶点集u和v的大小相等，u中的每个顶点p都可以引出两条边，它定义了一个二分图的权重就是每个完美匹配的权重相加，每个完美匹配的权重是这个完美匹配中所有边的乘积。 解题思路：首先如果一个点的度数为1，那么它的匹配方案是固定的，继而我们可以去掉这一对点。通过拓扑我们可以不断去掉所有度数为1的点。那么剩下的图中左右各有m个点，每个点度数都不小于2，且左边每个点度数都是2，而右侧总度数是2m，因此右侧只能是每个点度数都是2。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。 CODE：
#include<bits/stdc++.h> using namespace std; const int mod = 998244353; const int N = 300000 + 10; struct Edge { int nxt, to, w; bool mrk; } e[N*4];///构造领接链表的边结点 int T, n, head[N*2], cnt, deg[N*2], used[N*2]; ///T表示测试数据的组数，n表示节点个数，head表示头结点，deg记录每个结点的度，used表示这个节点是否被匹配过 long long part[2];///part表示最后剩的那两部分 void addedge(int u, int v, int w) {///构造领接链表 e[++cnt].nxt = head[u]; e[cnt].to = v; e[cnt].w = w; e[cnt].mrk = 0; head[u] = cnt; } void dfs(int cur, int idx) { ///因为要隔着取所以我们可以用part[0]表示一种情况，part[1]表示另一种情况，然后每次改变idx的值 used[cur] = 1;///表示这个顶点已经找过了，不能再找，所以要标记一下 for(int i=head[cur];i;i=e[i].nxt) { if(e[i].mrk) continue;///如果这个顶点已经被用了，就跳过 e[i].mrk = e[i^1].mrk = 1;///没有则标记，并把它对应的那个点也标记了 (part[idx] *= e[i].w) %= mod;///每个完美匹配的累乘 dfs(e[i].to, 1-idx);///递归寻找另一个完美匹配边 } } int main() { scanf("%d", &T); while(T-- && scanf("%d", &n)!=EOF) { memset(head, 0, sizeof(head)); memset(deg, 0, sizeof(deg)); memset(used, 0, sizeof(used)); cnt = 1; for(int u=1, v, w;u<=n;u++) for(int i=1;i<=2;i++) { scanf("%d %d", &v, &w); addedge(u, v+n, w); addedge(v+n, u, w); deg[u]++, deg[v+n]++; } long long ans = 1; queue<int> que; for(int v=n+1;v<=n+n;v++) if(deg[v] == 1) que.push(v); while(!que.empty())///对所有度为1的点进行拓扑排序，并去掉度为1节点 { int v = que.front(); que.pop(); used[v] = 1;///标记度为1的节点 for(int i=head[v];i;i=e[i].nxt) { if(e[i].mrk) continue; e[i].mrk = e[i^1].mrk = 1; used[ e[i].to ] = 1;///因为该节点与度为1的节点相连，所以也要去掉 (ans *= e[i].w) %= mod; for(int j=head[ e[i].to ];j;j=e[j].nxt)///将于这个点相连的所有边去掉，判断去掉便后，剩余节点的度是否为1，如果为1也要加入队列中 { e[j].mrk = e[j^1].mrk = 1; deg[e[j].to]--; if(deg[ e[j].to ] == 1) que.push(e[j].to); } } } //cout<<"ans: "<<ans<<endl; for(int u=1;u<=n;u++) { if(used[u]) continue; part[0] = part[1] = 1; dfs(u, 0);///调用dfs计算剩余的完美匹配 (ans *= (part[0]+part[1]) % mod) %= mod; } printf("%lld\n", ans); } }