HDU 6073 Matching In Multiplication

本文由 Ocrosoft 于 2017-08-08 10:43:02 发表

Matching In Multiplication

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1669    Accepted Submission(s): 508

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
 

Solution
2017 Multi-University Training Contest – Team 4
题意:给你一个二分图,每一集合里的 点数量 都为n,且其中一个集合里每个点的度数都为2.然后对于每一种完美匹配,算出边权值的乘积,然后再将每一种匹配的乘积加起来,输出最后结果。
思路:U集合里的点 度数都为二,V集合里的点度数未知,但加起来肯定为2*n,对于V集合里度数为1的点,它的匹配对象是固定的,所以我们用拓扑排序将度数为1的点全部挖出,算出乘积res。然后对于剩下 的图,假设总节点为2*m,则V集合总度数为2*m,由于此时V集合里已经,没有度数为1的点,所以V集合里点的度数都为2,这说明这个图每个连通块是个环,在环上间隔着取即可,一共两种方案。比如对于两个联通块,他俩的两种方案乘积分别是(a1,a2),(b1,b2),则答案为a1*b1+a1*b2+a2*b1+a2*b2,化简后为(a1+a2)*(b1+b2),最后在乘以res即可。

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 300000 + 10;
const int MAXN = maxn * 4;
const int MOD = 998244353;
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
#define log(msg) cout<<msg<<endl
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { x.first += y.first, x.second += y.second; return x; }
Pii operator -=(Pii &x, const Pii &y) { x.first -= y.first, x.second -= y.second; return x; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

vector<Pii> edge[maxn * 2];
int inDeg[maxn * 2];
bool vis[maxn * 2];
LL ans[2];
int sp; // start point
int main()
{
	int casTot;
	scanf("%d", &casTot);
	while (casTot--)
	{
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n * 2; ++i)inDeg[i] = 0, vis[i] = false, edge[i].clear();
		for (int i = 1, v1, w1, v2, w2; i <= n; ++i)
		{
			scanf("%d%d%d%d", &v1, &w1, &v2, &w2);
			v1 += n, v2 += n;
			edge[i].push_back(Pii(v1, w1));
			edge[v1].push_back(Pii(i, w1));
			edge[i].push_back(Pii(v2, w2));
			edge[v2].push_back(Pii(i, w2));
			inDeg[i] += 2;
			++inDeg[v1], ++inDeg[v2];
		}

		queue<int> q;
		LL delMul = 1;
		for (int i = n + 1; i <= 2 * n; ++i)
		{
			if (inDeg[i] == 1)
			{
				q.push(i);
				vis[i] = true;
			}
		}
		while (!q.empty())
		{
			int t = q.front();
			q.pop();
			for (auto p : edge[t])
			{
				int v = p.first;
				if (vis[v])continue;
				if (--inDeg[v] == 1)q.push(v), vis[v] = true;
				if (t > n)delMul = (delMul * 1LL * p.second) % MOD;
			}
		}

		function<void(int, int, int)> Dfs;
		Dfs = [&](int u, int ap, int fa)
		{
			vis[u] = true;
			for (auto p : edge[u])
			{
				int v = p.first;
				if (v == sp&&v != fa)
					ans[ap] = (ans[ap] * 1LL * p.second) % MOD;
				if (vis[v])continue;
				ans[ap] = (ans[ap] * 1LL * p.second) % MOD;
				Dfs(v, ap ^ 1, u);
			}
		};
		for (int i = 1; i <= n; i++)
		{
			if (!vis[i])
			{
				ans[0] = ans[1] = 1;
				Dfs(sp = i, 0, 0);
				delMul = (delMul*((ans[0] + ans[1]) % MOD)) % MOD;
			}
		}
		print(delMul);
	}
	return 0;
}
 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6073 Matching In Multiplication

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址