【UOJ】#79. 一般图最大匹配

题解

板子！我相信其实没人来看我的板子！但是为了防止我忘记，我还是要写点什么

我们考虑二分图，为什么二分图就能那么轻松地写出匹配的代码呢？因为匹配只会发生在黑点和白点之间，我们找寻增广路，必然是一黑一白一黑一白这么走

然而，一般图由于有了奇环，事情变得不妙了啊

奇环上的所有点，可以是……任意的奇偶性（起点到它的距离的奇偶性，可以是非简单路径）

那么我们就让任意奇偶性的点可以进行匹配就可以了，我们通过pre维护出一条路径到达根节点

怎么维护呢？缩花！

花？什么是花？

花就是奇环，我们找到花托（两个点的最近公共祖先），从两个点构建一条能走到花托的路径

如何构建

对于(u,v)和花托f

我们让u的pre走到v，然后令u跳到u匹配点的pre,v变成u的匹配点，继续这个操作，同时把这个匹配点改成偶点(可进行增广）

对v走到花托走到f进行类似的操作

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define enter putchar('\n')

#define space putchar(' ')

#define MAXN 505

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

	res = 0;char c = getchar();T f = 1;

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {putchar('-');x = -x;}

	if(x >= 10) {

		out(x / 10);

	}

	putchar('0' + x % 10);

}

struct node {

	int to,next;

}E[MAXN * MAXN * 2];

int sumE,head[MAXN];

int N,M,fa[MAXN],pre[MAXN],matk[MAXN],sta[MAXN];

int Q[MAXN],L,R;

void add(int u,int v) {

	E[++sumE].to = v;

	E[sumE].next = head[u];

	head[u] = sumE;

}

int getfa(int x) {

	return fa[x] == x ? x : fa[x] = getfa(fa[x]);

}

int lca(int x,int y) {

	static int vis[MAXN],Tim;

	++Tim;

	while(1) {//每个点都尝试走一步

		x = getfa(x);

		if(x) {

			if(vis[x] == Tim) {

				return x;

			}

			else vis[x] = Tim,x = pre[matk[x]];

		}

		swap(x,y);

	}

}

void blossom(int u,int v,int flower_root) {

	while(getfa(u) != flower_root) {

		pre[u] = v;

		//我们每个点既然都是奇偶难分（雾）

		//就构建出一条这个点走到花托的交错路

		//构建方法就是顺着匹配边往上跳

		//这个时候我们碰到的匹配点还都以为自己是偶点= =（奇怪的叙述）

		int m = matk[u];

		if(sta[m] == 1) {sta[m] = 0;Q[++R] = m;}

		//把所有以为自己是奇点的人告诉他们可以当偶点啦

		if(u == fa[u]) fa[u] = flower_root;

		if(m == fa[m]) fa[m] = flower_root;

		v = m,u = pre[m];

	}

}

bool match(int s) {

	//sta : -1 未访问 0:偶点（起始点）  1:奇点

	//pre : 交错树上的父亲，任意一点顺着当前自己的匹配点的pre会走到树根，也就是还原出了交错路

	L = 1,R = 0;Q[++R] = s;

	memset(sta,-1,sizeof(sta));

	memset(pre,0,sizeof(pre));

	sta[s] = 0;//起点是偶点

	for(int i = 1 ; i <= N ; ++i) fa[i] = i;

	while(L <= R) {

		int u = Q[L++];

		for(int i = head[u] ; i ; i = E[i].next) {

			int v = E[i].to;

			if(sta[v] == -1) {

				pre[v] = u;sta[v] = 1;

				if(!matk[v]) {

					for(int j = u , k = v,last; ; j = pre[k = last]) {

						last = matk[j],matk[j] = k;matk[k] = j;

						if(!last) break;

					}//顺着pre节点找交错路，全部取反

					return 1;

				}

				sta[matk[v]] = 0;

				Q[++R] = matk[v];

			}

			else if(getfa(v) != getfa(u) && !sta[v]) {

				int f = lca(u,v);blossom(u,v,f);blossom(v,u,f);

				//两个偶点，缩花，两条路径爬到父亲

			}

		}

	}

	return 0;

}

void Init() {

	read(N);read(M);

	int u,v;

	for(int i = 1 ; i <= M ; ++i) {

		read(u);read(v);

		add(u,v);add(v,u);

	}

}

void Solve() {

	int ans = 0;

	for(int i = 1 ; i <= N ; ++i) {

		if(!matk[i] && match(i)) ++ans;

	}

	out(ans);enter;

	for(int i = 1 ; i <= N ; ++i) {

		out(matk[i]);

		if(i == N) enter;

		else space;

	}

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	Init();

	Solve();

}

//5aaC5p6c5oiR5LiK5LiN5LqGdGh177yM5oiR5bCx5YaN5Lmf6KeB5LiN5Yiw54yr6ZSf5LqG

//4oCm4oCm54yr6ZSf55yf5Y+v54ix

巴特西

【UOJ】#79. 一般图最大匹配

题解

代码

最新文章

热门文章