记录编号	228585	评测结果	AAAAAAAAAA
题目名称	[Ural 1099] 工作安排	最终得分	100
用户昵称	铁策	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2016-02-19 13:39:51	内存使用	0.26 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 501
int father[MAXN];
int getfather(int x)
{
	if (father[x]==x)
		return x;
	else
		return (father[x]=getfather(father[x]));
}
void uni(int a,int b)
{
	a=getfather(a);
	b=getfather(b);
	if (a!=b)
		father[a]=b;
}
int n,m,t;
vector<int> edge[MAXN];
int queue[MAXN]={0},rear;
int match[MAXN]={0},next[MAXN],mark[MAXN],vis[MAXN];
inline int lca(int x,int y)
{
	static int t=0;
	t++;
	while (true)
	{
		if (x)
		{
			x=getfather(x);
			if (vis[x]==t)
				return x;
			vis[x]=t;
			if (match[x])
				x=next[match[x]];
			else
				x=0;
		}
		swap(x,y);
	}
}
void group(int a,int p)
{
	while (a!=p)
	{
		int b=match[a],c=next[b];
		if (getfather(c)!=p)
			next[c]=b;
		if (mark[b]==2)
		{
			queue[rear++]=b;
			mark[b]=1;
		}
		if (mark[c]==2)
		{
			queue[rear++]=c;
			mark[c]=1;
		}
		uni(a,b);
		uni(b,c);
		a=c;
	}
}
void aug(int s)
{
	memset(next,0,sizeof(next));
	memset(mark,0,sizeof(mark));
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++)
		father[i]=i;
	mark[s]=1;
	queue[0]=s;
	rear=1;
	for (int front=0;!match[s] && front<rear;front++)
	{
		int x=queue[front];
		for (int j=0;j<(int)edge[x].size();j++)
		{
			int y=edge[x][j];
			if (match[x]==y || getfather(x)==getfather(y) || mark[y]==2)
				continue;
			if (mark[y]==1)
			{
				int r=lca(x,y);
				if (getfather(x)!=r)
					next[x]=y;
				if (getfather(y)!=r)
					next[y]=x;
				group(x,r);
				group(y,r);
			}
			else if (!match[y])
			{
				next[y]=x;
				for (int u=y;u;)
				{
					int v=next[u];
					int t=match[v];
					match[v]=u;
					match[u]=v;
					u=t;
				}
				break;
			}
			else
			{
				next[y]=x;
				queue[rear++]=match[y];
				mark[match[y]]=1;
				mark[y]=2;
			}
		}
	}
}
int main()
{
	freopen("WorkScheduling.in","r",stdin);
	freopen("WorkScheduling.out","w",stdout);
	scanf("%d",&n);
	int x,y; 
	while (scanf("%d%d",&x,&y)==2)
	{
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for (int i=1;i<=n;i++)
		if (!match[i])
			aug(i);
	int sum=0;
	for (int i=1;i<=n;i++)
		if (match[i])
			sum++;
	cout<<sum<<endl;
	bool vised[255]={0};
	for (int i=1;i<=n;i++)
	{
		if (!vised[i] && match[i])
		{
			cout<<i<<" "<<match[i]<<endl;
			vised[i]=vised[match[i]]=1;
		}
	}
	return 0;
}