记录编号	262956	评测结果	AAAAAAAAAA
题目名称	[Ural 1099] 工作安排	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-05-23 13:12:20	内存使用	4.29 MiB

#include<cstdio>//O(n^3)，神板子，码量不大 
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int maxl=99999999;
const int maxn=510; 
int n,m,i,j,s,v,match[maxn],ance[maxn*2][maxn],dist[maxn*2],ans,color;
//[1,n]代表S型点，[n+1,2*n]代表T型点
//ance[i][j]表示i的dist为j的祖先的原编号，hash[i][j]表示j（原编号）是否是i的祖先 
vector <int> l[maxn];
int hash[maxn*2][maxn];

int z[maxn*2],r;
void change(int x){
	ans++;
	for (int i=dist[x];i>0;i-=2){
		match[ance[x][i]]=ance[x][i-1];
		match[ance[x][i-1]]=ance[x][i];
	}
}
void extend(int x){
	int i,j,k,v=(x>n?x-n:x);
	if (x>n){//若为T型点 
		if (match[v]==0){//发现单身，增广 
			change(x);return;
		}
		k=match[v];
		if (hash[x][k]!=color&&dist[k]>dist[x]+1){//十分类似于dijsktra的松弛操作 
			dist[k]=dist[x]+1;
			for (j=1;j<=dist[x];j++)
				hash[k][ance[k][j]=ance[x][j]]=color;
			hash[k][ance[k][dist[k]]=k]=color;
			z[++r]=k;
		}
	}
	else
	for (i=0;i<(int)l[v].size();i++){//十分类似于dijsktra的松弛操作 
		k=n+l[v][i];
		if (hash[x][l[v][i]]!=color&&dist[k]>dist[x]+1){
			dist[k]=dist[x]+1;
			for (j=1;j<=dist[x];j++)
				hash[k][ance[k][j]=ance[x][j]]=color;
			hash[k][ance[k][dist[k]]=l[v][i]]=color;
			z[++r]=k;
		} 
	}
}
void bfs(int x){
	color=z[r=1]=x;						//初始化 
	for (int i=1;i<=2*n;i++) dist[i]=maxl;
	dist[x]=1;hash[x][x]=color;ance[x][1]=x;
	for (int i=1;i<=r;i++){			//广搜 
		extend(z[i]);
		if (match[x]!=0) return; 
	}
}

int main()
{
	freopen("WorkScheduling.in","r",stdin);
	freopen("WorkScheduling.out","w",stdout);
	scanf("%d",&n);
	while(~scanf("%d%d",&s,&v)){
		l[s].push_back(v);
		l[v].push_back(s);
	}
	for (i=1;i<=n;i++)
	if (match[i]==0)
		bfs(i);
	printf("%d\n",ans*2);
	for (i=1;i<=n;i++)
	if (match[i]!=0&&i<match[i])
		printf("%d %d\n",i,match[i]);
	return 0;
}