Educational Codeforces Round 108(Rated for Div. 2) E - Off by One（一种一般图的边最大匹配，好题）

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

CF1519E

Weblink

https://codeforces.com/contest/1519/problem/E

Problem

Solution

显然同一个直线上的点，$(x,y)$，$x,y$ 同除 $\gcd (x,y)$ ，得到的是同一个点，所以我们可以在输入的时候处理一下每个点上移一步$(x+1,y)$，下移一步 $(x,y+1)$ 到达的是哪条直线，我们直接映射一下，这样就可以 $O(n)$ 建图。什么？你说 $x,y$ 不一定是整数？$x=\frac{a}{b},y=\frac{c}{d}$，例如 $(x,y+1)=(\frac{a}{b},\frac{c}{d}+1)$ 显然我们直接将点同乘 $b\times d$ ，因为不管乘多少，最后除去 $\gcd$ 以后都代表同一个直线。

即：

( a b , c d + 1 ) = ( a b × b   d , ( c d + 1 ) × b   d ) = ( a × d , b × ( c + d ) )

$$\begin{aligned}(\cfrac{a}{b},\cfrac{c}{d}+1)&=(\cfrac{a}{b}\times b\ d,(\cfrac{c}{d}+1)\times b\ d)&\\&=(a\times d,b\times(c+d))\end{aligned}$$ (ba​,dc​+1)​=(ba​×b d,(dc​+1)×b d)=(a×d,b×(c+d))​​

( a b + 1 , c d ) = ( ( a b + 1 ) × b   d , c d × b   d ) = ( ( a + b ) × d , b × c ) )

$$\begin{aligned}(\cfrac{a}{b}+1,\cfrac{c}{d})&=((\cfrac{a}{b}+1)\times b\ d,\cfrac{c}{d}\times b\ d)&\\&=((a+b)\times d,b\times c))\end{aligned}$$ (ba​+1,dc​)​=((ba​+1)×b d,dc​×b d)=((a+b)×d,b×c))​​

建图之后我们计算最大的匹配边数即可。好像是一个最大匹配？带花树！但是很难处理，每一个点，因为有两个移动策略，所以每一个点会拓展成两个点，也就代表着两条直线，所以把题目中的模型抽离出来，即为：给定一个无向图，每次匹配为选定两条没有用过的相邻的边，将他们匹配，求最大的匹配数以及匹配的方案数。

直接做无向图有点难搞，显然我们可以利用数据简化的思想，先来考虑树的做法，显然对于一颗节点数为 $n$ 的树，最大匹配边数为 $\lfloor \frac{n}{2}\rfloor$，即除了一条直接与根节点相连的边不确定以外，其他的边一定能够两两配对，因为对于一个节点，如果度数为偶数 $2k$，显然形成 $k$ 个匹配，若为奇数 $2k-1$，我们可以将它与它的父结点匹配，剩余的点就为偶数个，相互匹配既可。

那么拓展到一个无向图，我们只需要将无向图转换为一个树就行啦，当然图不一定是连通的，所以是一个森林hhh 。我们选择DFS序生成树，这样一个无向图就被分为了若干个生成树，有树边和非树边，我们直接按照时间戳，按照深度从大到小，从低到高匹配，可以保证匹配数一定可以达到 $\lfloor \frac{n}{2}\rfloor$ 的上界。

具体的代码实现的话，我们有一个取巧的方法，设 match[x] 表示是否存在一条与 $x$ 相连且还没有匹配的边，这样我们只需要看一下子节点和父结点是否有可以匹配的边就行了。

因为每条边只能用一次，所以我们用完之后直接把边删掉就行了。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define x first 
#define y second

const int N = 500007;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

map<PLL, int> mp;
vector<PII> ans;
PII match[N];
int cnt;
int n, m;
bool vis[N];
int head[N], ver[N], edge[N], nex[N], tot;


int get_id(ll x, ll y)
{
   
	ll d = __gcd(x, y);
	x /= d;
	y /= d;
	if(mp.find({
   x, y}) == mp.end())
		mp[{
   x, y}] = ++ cnt;
	return mp[{
   x, y}];
}

void add(int x, int y, int id)
{
   
	ver[tot] = y;
	nex[tot] = head[x];
	edge[tot] = id;
	head[x] = tot ++ ;
}

int dfs(int x)
{
   
	vis[x] = 1;
	for(int i = head[x]; ~i; i = nex[i]) {
   
		int y = ver[i], id = edge[i];
		ver[i] = ver[i ^ 1] = 0;
		if(y) {
   
			if(vis[y] == 0)
				dfs(y);
			if(match[y].x) {
   
				ans.push_back({
   id, match[y].y});
				match[y] = {
   0, 0};
			}
			else if(match[x].x) {
   
				ans.push_back({
   match[x].y, id});
				match[x] = {
   0, 0};
			}
			else match[x] = {
   y, id};
		}
	}
}

int main()
{
   
	memset(head, -1, sizeof head);
	scanf("%d", &n);
	for(int i =1; i <= n; ++ i) {
   
		int a, b, c, d, x, y;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		x = get_id((1ll * a + b) * d, 1ll * b * c);
		y = get_id(1ll * a * d, (1ll * c + d) * b);
		add(x, y, i);
		add(y, x, i);
	}
	
	for(int i = 1; i <= cnt; ++ i) 
		if(vis[i] == 0) 	
			dfs(i);
	printf("%d\n", ans.size()); 
	for(auto i : ans) {
   
		printf("%d %d\n", i.first, i.second);
	}
	return 0;
}

转载：https://blog.csdn.net/weixin_45697774/article/details/116308361