Rockdu's Blog

从前一个和谐的班级，所有人都是搞OI的。有 nn 个是男生，有 00 个是女生。男生编号分别为 1,…,n1,…,n。

现在老师想把他们分成若干个两人小组写动态仙人掌，一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。

有若干个这样的条件：第 vv 个男生和第 uu 个男生愿意组成小组。

请问这个班级里最多产生多少个小组？

输入格式

第一行两个正整数，n,mn,m。保证 n≥2n≥2。

接下来 mm 行，每行两个整数 v,uv,u 表示第 vv 个男生和第 uu 个男生愿意组成小组。保证 1≤v,u≤n1≤v,u≤n，保证 v≠uv≠u，保证同一个条件不会出现两次。

输出格式

第一行一个整数，表示最多产生多少个小组。

接下来一行 nn 个整数，描述一组最优方案。第 vv 个整数表示 vv 号男生所在小组的另一个男生的编号。如果 vv 号男生没有小组请输出 00。

样例一

input

10 20
9 2
7 6
10 8
3 9
1 10
7 1
10 9
8 6
8 2
8 1
3 1
7 5
4 7
5 9
7 8
10 4
9 1
4 8
6 3
2 5

output

5
9 5 6 10 2 3 8 7 1 4

样例二

input

5 4
1 5
4 2
2 1
4 3

output

2
2 1 4 3 0

限制与约定

1≤n≤5001≤n≤500，1≤m≤1247501≤m≤124750。

时间限制：1s1s

空间限制：256MB256MB

下载

样例数据下载

一般图最大匹配的模板，本人技术水平有限，感觉写不出网上那么好的博客，所以就贴一个吧。

一般图最大匹配

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e3 + 5;
const int maxm = 124750 + 5;
int n, m, u, v;
struct edge {
	int v, next;
}e[maxm << 1];
int head[maxn], cnt, fa[maxn];

void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

namespace DSU {
	int fa[maxn];
	void init(int x) {for(register int i = 1; i <= x; ++i) fa[i] = i;}
	int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	void combine(int a, int b) {fa[find(a)] = find(b);}
}

int type[maxn], match[maxn], pre[maxn], tid[maxn], id;

int LCA(int u, int v) {
	for(++id;;swap(u, v)) 
	if(u) {
		u = DSU::find(u);
		if(tid[u] == id) return u;
		else tid[u] = id, u = pre[match[u]];
	}
}

void Bloom(int u, int v, int lca, queue<int > * q) {
	while(DSU::find(u) != lca) {
		pre[u] = v, v = match[u];
		if(DSU::find(u) == u) DSU::fa[u] = lca;
		if(DSU::find(v) == v) DSU::fa[v] = lca;
		if(type[v] == 1) type[v] = 0, q -> push(v);
		u = pre[v];
	}
}

bool AGM(int u) { //  augmentation;
	DSU::init(n);
	memset(type, -1, sizeof(int) * (n + 1));
	memset(pre, 0, sizeof(int) * (n + 1));
	queue<int > q; q.push(u);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(DSU::find(u) == DSU::find(v)) continue;
			if(type[v] == -1) {
				if(!match[v]) {
					while(u) {
						int t = match[u];
						match[match[v] = u] = v;
						u = pre[v = t];
					}
					return 1;
				}
				type[v] = 1, pre[v] = u;
				type[match[v]] = 0, q.push(match[v]);
			} else if(type[v] == 0) {
				int lca = LCA(u, v);
				Bloom(u, v, lca, &q);
				Bloom(v, u, lca, &q);
			}
		}
	}
	return 0;
}

int ans = 0;

int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= m; ++i)
		scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
	for(register int i = 1; i <= n; ++i)
		if(!match[i]) ans += AGM(i);
	printf("%d\n", ans);
	for(register int i = 1; i <= n; ++i)
		printf("%d ", match[i]);
	return 0;
} 

#include
#include
#include
#include
using namespace std;
const int maxn = 1e3 + 5;
const int maxm = 124750 + 5;
int n, m, u, v;
struct edge {
	int v, next;
}e[maxm << 1];
int head[maxn], cnt, fa[maxn];

void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

namespace DSU {
	int fa[maxn];
	void init(int x) {for(register int i = 1; i <= x; ++i) fa[i] = i;}
	int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	void combine(int a, int b) {fa[find(a)] = find(b);}
}

int type[maxn], match[maxn], pre[maxn], tid[maxn], id;

int LCA(int u, int v) {
	for(++id;;swap(u, v)) 
	if(u) {
		u = DSU::find(u);
		if(tid[u] == id) return u;
		else tid[u] = id, u = pre[match[u]];
	}
}

void Bloom(int u, int v, int lca, queue<int > * q) {
	while(DSU::find(u) != lca) {
		pre[u] = v, v = match[u];
		if(DSU::find(u) == u) DSU::fa[u] = lca;
		if(DSU::find(v) == v) DSU::fa[v] = lca;
		if(type[v] == 1) type[v] = 0, q -> push(v);
		u = pre[v];
	}
}

bool AGM(int u) {
	DSU::init(n);
	memset(type, -1, sizeof(int) * (n + 1));
	memset(pre, 0, sizeof(int) * (n + 1));
	queue q; q.push(u);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(register int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if(DSU::find(u) == DSU::find(v)) continue;
			if(type[v] == -1) {
				if(!match[v]) {
					while(u) {
						int t = match[u];
						match[match[v] = u] = v;
						u = pre[v = t];
					}
					return 1;
				}
				type[v] = 1, pre[v] = u;
				type[match[v]] = 0, q.push(match[v]);
			} else if(type[v] == 0) {
				int lca = LCA(u, v);
				Bloom(u, v, lca, &q);
				Bloom(v, u, lca, &q);
			}
		}
	}
	return 0;
}

int ans = 0;

int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= m; ++i)
		scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
	for(register int i = 1; i <= n; ++i)
		if(!match[i]) ans += AGM(i);
	printf("%d\n", ans);
	for(register int i = 1; i <= n; ++i)
		printf("%d ", match[i]);
	return 0;
}