记录编号	224234	评测结果	AAAAAAAAAA
题目名称	[Ural 1099] 工作安排	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-02-15 23:53:04	内存使用	0.67 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
const int SIZEN=300;
int N;
vector<int> S[SIZEN];
int g[SIZEN][SIZEN]={0};
int match[SIZEN]={0};
int Q[SIZEN];
int next[SIZEN],belong[SIZEN],vis[SIZEN];
int mark[SIZEN];
int siz;
bool ok=0;
int t=0;
void read()
{
	scanf("%d",&N);
	int x,y;
	while(scanf("%d%d",&x,&y)==2)
	{
		if(x!=y&&!g[x][y])
		{
			S[x].push_back(y);
			S[y].push_back(x);
		}
		g[x][y]=g[y][x]=1;
	}
}
int findb(int x)
{
	if(belong[x]==x) return x;
	return belong[x]=findb(belong[x]);
}
void unit(int a,int b)
{
	a=findb(a);
	b=findb(b);
	if(a!=b) belong[a]=b;
}
int LCA(int x,int y)
{
	t++;
	while(true)
	{
		if(x!=-1)
		{
			x=findb(x);
			if(vis[x]==t) return x;
			vis[x]=t;
			if(match[x]!=-1) x=next[match[x]];
			else x=-1;
		}
		swap(x,y);
	}
}
void group(int x,int y)
{
	while(x!=y)
	{
		//if(ok==1) cout<<x<<endl;
		int b=match[x],c=next[b];
		if(findb(c)!=y) next[c]=b;
		if(mark[b]==2) mark[Q[siz++]=b]=1;
		if(mark[c]==2) mark[Q[siz++]=c]=1;
		unit(x,b),unit(b,c);
		x=c;
	}
}
void bfs(int s)//增广
{
	for(int i=1;i<=N;i++) next[i]=-1,belong[i]=i,mark[i]=0,vis[i]=0;
	mark[s]=1;Q[0]=s;siz=1;//cout<<match[1]<<endl;
	//cout<<s<<endl;
	for(int front=0;match[s]==-1&&front<siz;front++)
	{
		int x=Q[front];
		//if(s==9) cout<<x<<endl;
		for(int i=0;i<S[x].size();i++)
		{
			int v=S[x][i];
			//if(s==9) cout<<mark[8]<<endl;
			if(match[x]==v) continue;//x被匹配到了y上
			if(findb(x)==findb(v)) continue;//x于y在同一朵花上
			if(mark[v]==2) continue;//形成了偶环
			if(mark[v]==1)//形成了奇环，缩环为点
			{
				int r=LCA(x,v);
				if(findb(x)!=r) next[x]=v;
				if(findb(v)!=r) next[v]=x;
				group(x,r);//把x-r缩为点
				//if(x==5&&s==9) cout<<x<<" "<<v<<" "<<r<<endl;
				group(v,r);
			}
			else if(match[v]==-1)
			{
				next[v]=x;
				for(int u=v;u!=-1;)
				{
					int y=next[u];
					int mv=match[y];
					match[y]=u;match[u]=y;
					u=mv;
				}
				break;
			}
			else
			{
				next[v]=x;
				Q[siz++]=match[v];
				mark[match[v]]=1;
				mark[v]=2;
			}
			
		}
	}
}
void work()
{
	int ans=0;
	for(int i=1;i<=N;i++) match[i]=-1;
	for(int i=1;i<=N;i++) if(match[i]==-1) bfs(i);
	for(int i=1;i<=N;i++) if(match[i]!=-1) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=N;i++) if(match[i]>i) printf("%d %d\n",i,match[i]);
}
int main()
{
	freopen("WorkScheduling.in","r",stdin);
	freopen("WorkScheduling.out","w",stdout);
	read();
	work();
	return 0;
}