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(1T15), denoting the number of test cases.

In each test case, there is an integer n(1n300000) 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(1vi,jn,1wi,j109), 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中点相连。
那么这个图就是若干个环套树组成的。而且分析一下可以知道一定是偶环和偶链,且环和链的公共节点一定是V中的。
而每个环都有两种选择方案可以认为是a1和a2,而链上只有一种选择方案。所以答案就是若干个(a1+a2)*c的乘积。直接把环抠出来,然后在按照类似于拓扑序的关系处理链上的情况。至于为什么要考虑拓扑序,因为链可能是多个链交叉而成的,那么这个多叉的公共点一定是V中的点,我们只能在一条链上选一条边和他匹配,否则就会乱掉。比赛的时候就是因为没考虑需要做拓扑序的处理链的情况而错了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注