记录编号	490099	评测结果	AAAAAAAAAA
题目名称	[HAOI 2017]新型城市化	最终得分	100
用户昵称	Ays	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2018-03-07 14:20:14	内存使用	3.06 MiB

#include<bits/stdc++.h>
#define maxd 10005
#define inf 0x3f3f3f3f
#define en 10003
using namespace std;
int n,m,black[maxd],d[maxd];
struct ro{
	int flow,to;
};
struct node{
	int x,y;
} lis[150005],pr[150005];
vector<ro> edge;
vector<int> a[maxd],aa[maxd];
queue<int> q;
int dfn[maxd],low[maxd],idx,instack[maxd],where[maxd],idxx;
stack<int> s;
struct rule{
	bool operator()(const node &s1,const node &s2){
		if(s1.x==s2.x) return s1.y<s2.y;
		return s1.x<s2.x;
	}
};
void tarjan(int u){
	dfn[u]=low[u]=++idx;
	s.push(u);instack[u]=1;
	for(int i=0;i<a[u].size();i++){
		ro c=edge[a[u][i]];
		if(c.flow<=0) continue;
		int to=c.to;
		if(!dfn[to]){
			tarjan(to);
			low[u]=min(low[u],low[to]);
		} else if(instack[to]) low[u]=min(low[u],dfn[to]);
	}
	if(low[u]==dfn[u]){
		idxx++;
		while(s.top()!=u){
			int top=s.top();s.pop();
			where[top]=idxx;
			instack[top]=0;
		}
		where[s.top()]=idxx;
		instack[s.top()]=0;s.pop();
	}
}

void find(){
	int ans=0;
	for(int i=0;i<=n;i++) if(!dfn[i]) tarjan(i);
	if(!dfn[en]) tarjan(en);
	for(int u=1;u<=n;u++){
		if(!black[u])continue;
//		cout<<u<<" u"<<endl;
		for(int i=0;i<a[u].size();i++){
			ro c=edge[a[u][i]];
			if(c.flow>0) continue;
			if(where[u]==where[c.to]) continue;
			pr[++ans].x=u;pr[ans].y=c.to;
			if(pr[ans].x>pr[ans].y) swap(pr[ans].y,pr[ans].x); 
		}
	}
	sort(pr+1,pr+ans+1,rule());
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++){
		printf("%d %d\n",pr[i].x,pr[i].y);
	}
}

//--------------------
bool bfs(){
	memset(d,-1,sizeof(d));
	d[0]=0;
	q.push(0);
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int i=0;i<a[now].size();i++){
			ro c=edge[a[now][i]];
			if(d[c.to]!=-1||c.flow<=0) continue;
			d[c.to]=d[now]+1;
			q.push(c.to);
		}
	}
	return (d[en]!=-1);
}
int dfs(int u,int flow){
	if(u==en) return flow;
	int cnt=0;
	for(int i=0;i<a[u].size();i++){
		ro c=edge[a[u][i]];
		if(c.flow<=0||d[c.to]!=d[u]+1) continue;
		int cc=dfs(c.to,min(flow,c.flow));
		flow-=cc;
		cnt+=cc;
		edge[a[u][i]].flow-=cc;
		edge[a[u][i]^1].flow+=cc;
		if(flow==0) break;
	}
	if(cnt==0) d[u]=-1;
	return cnt;
}


void dinic(){
	int mdzz=0;
	while(bfs()) mdzz+=dfs(0,inf);
//	cout<<mdzz<<" dinic"<<endl;
}
//-----------------------
void getb(int u,int v){
	ro ss;ss.flow=1;ss.to=v;
	edge.push_back(ss);
	a[u].push_back(edge.size()-1);
	ss.to=u;ss.flow=0;
	edge.push_back(ss);
	a[v].push_back(edge.size()-1);
}

void dfs1(int u,int ca){
	black[u]=ca;
	for(int i=0;i<aa[u].size();i++){
		int to=aa[u][i];
		if(black[to]!=-1) continue;
		if(ca==0) dfs1(to,1);
		else dfs1(to,0);
	}
}

void blackwhite(){
	for(int i=1;i<=n;i++)
	if(black[i]==-1) dfs1(i,0);
	for(int i=1;i<=n;i++)
		if(black[i]) getb(0,i);
		else getb(i,en);
	for(int i=0;i<m;i++){
		int s1=lis[i].x,s2=lis[i].y;
		if(black[s1]) getb(s1,s2);
		else getb(s2,s1);
	}
}
void sc(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&lis[i].x,&lis[i].y);
		aa[lis[i].x].push_back(lis[i].y);
		aa[lis[i].y].push_back(lis[i].x);
	}
}
///---------------

int main(){
	freopen("newcity.in","r",stdin);
	freopen("newcity.out","w",stdout);
	sc();
	memset(black,-1,sizeof(black));
	blackwhite();
	dinic();
	find();
	return 0;
}