记录编号	249923	评测结果	AAAAAAAAAA
题目名称	[Ural 1099] 工作安排	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-04-13 21:36:06	内存使用	0.89 MiB

#include<stdio.h>
bool link[255][255];
int n,m,ans,shu,tim,first[255];
int l,r,q[255],ma[255],st[255],f[255],pre[255],vis[255];
struct edge{int v,nx;}o[70010];
inline void add(int u,int v){o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;}
inline int lca(int x,int y){
	for(++tim;vis[x]!=tim;x^=y,y^=x,x^=y)if(x)
		vis[x]=tim,x=f[pre[ma[x]]];
	return x;
}
inline void up(int x,int y,int j){
	for(;f[x]!=j;x=pre[y=ma[x]]){
		pre[x]=y,f[x]=j,f[ma[x]]=j;
		if(st[ma[x]]>0)q[++r]=ma[x];
	}
}
inline bool match(int x){
	for(int i=1;i<=n;++i)f[i]=i,st[i]=-1;
	q[l=r=0]=x,st[x]=0;
	while(l<=r){
		x=q[l++];
		for(int i=first[x],j,k;i;i=o[i].nx)
		    if(st[o[i].v]<0){
				st[o[i].v]=1,pre[o[i].v]=x;
				if(!ma[o[i].v]){
					for(j=x,i=o[i].v;j;j=pre[i=k])
						k=ma[j],ma[j]=i,ma[i]=j;
					return 1;
				}
				st[ma[o[i].v]]=0,q[++r]=ma[o[i].v];
		    }else if(f[o[i].v]!=f[x]&&!st[o[i].v]){
				int j=lca(o[i].v,x);
				up(o[i].v,x,j),up(x,o[i].v,j);
				for(j=1;j<=n;++j)f[j]=f[f[j]];
		    }
	}
	return 0;
}
int main(){
	freopen("WorkScheduling.in","r",stdin);
	freopen("WorkScheduling.out","w",stdout);
	scanf("%d",&n);
	for(int x,y;scanf("%d%d",&x,&y)==2;add(x,y),add(y,x));
	for(int i=1;i<=n;++i)ans+=!ma[i]&&match(i);
	printf("%d\n",ans<<1);
	for(int i=1;i<=n;++i)
	    if(ma[i]&&!link[i][ma[i]])
			link[i][ma[i]]=link[ma[i]][i]=1,printf("%d %d\n",i,ma[i]);
	//while(1);
}