记录编号	193924	评测结果	AAAAAAAAAAA
题目名称	奶牛的电信	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2015-10-15 19:49:53	内存使用	0.51 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x7fffffff/2,SIZEN=210;
int N,M,S,T,tot=0;
deque<int> s[2*SIZEN];
int e[2*SIZEN],H[2*SIZEN],ans=0;
bool visit[2*SIZEN]={0};
deque<int> Q,an;
class miku
{
public:
	int fr,to,cap,flow;
	miku(){}
	miku(int a,int b,int c,int d)
	{
		fr=a,to=b,cap=c,flow=d;
	}
}E[16*SIZEN];
void dfs(int x)
{
	visit[x]=1;
	//cout<<x<<" "<<visit[x]<<endl;
	for(int i=0;i<s[x].size();i++)
	{
		miku v=E[s[x][i]];
		if(v.cap<=v.flow||visit[v.to]) continue;
		dfs(v.to);
	}
}
void add(int fr,int to,int cap)
{
	s[fr].push_back(tot);
	E[tot++]=miku(fr,to,cap,0);
	s[to].push_back(tot);
	E[tot++]=miku(to,fr,0,0);
}
void read()
{
	int st,ed;
	scanf("%d%d%d%d",&N,&M,&st,&ed);
	S=st;T=ed+N;
	add(st,st+N,INF);add(ed,ed+N,INF);
	for(int i=1;i<=N;i++) 
	{
		if(i==st||i==ed) continue;
		add(i,i+N,1);
	}
	int fr,to;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&fr,&to);
		add(fr+N,to,INF/SIZEN);add(to+N,fr,INF/SIZEN);
	}
}
void push(int x,int t)
{
	miku &v=E[t];
	int flow=min(e[x],v.cap-v.flow);
	e[x]-=flow;v.flow+=flow;e[v.to]+=flow;E[t^1].flow-=flow;
	if(v.to!=S&&v.to!=T&&e[v.to]>0) Q.push_back(v.to);
}
void use_up(int x)
{
	int mi;
	while(e[x])
	{
		mi=INF;
		//cout<<x<<" "<<H[x]<<" "<<e[x]<<endl;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.cap<=v.flow) continue;
			if(H[v.to]==H[x]-1)
			{
				//cout<<"v:"<<v.to<<" "<<v.cap<<" "<<v.flow<<" "<<H[v.to]<<endl;
				push(x,s[x][i]);
				if(!e[x]) break;
			}
			else if(H[v.to]<mi) mi=H[v.to];
		}
		if(!e[x]) break;
		H[x]=mi+1;
	}
}
int maxflow()
{
	memset(e,0,sizeof(e));
	memset(H,0,sizeof(H));
	H[S]=2*N;if(H[S]>20) H[S]=20;e[S]=INF;
	for(int i=0;i<s[S].size();i++) push(S,s[S][i]);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		//cout<<x<<endl;
		use_up(x);
	}
	return e[T];
}
void work()
{
	int cnt=ans,pos=0;
	for(int i=1;i<=N;i++)
	{
		if(i==S||i==T-N) continue;
		for(int j=0;j<tot;j++)
		{
			E[j].flow=0;
			if(E[j].fr==i&&E[j].to==i+N) {pos=j;E[j].cap=0;}
		}
		int now=maxflow();
		if(now==cnt-1)
		{
			cnt=now;
			an.push_back(i);
		}
		else E[pos].cap=1;
		if(an.size()==ans) break;
	}
	for(int i=0;i<an.size();i++) printf("%d ",an[i]);
}
int main()
{
	freopen("telecow.in","r",stdin);
	freopen("telecow.out","w",stdout);
	read();
	ans=maxflow();
	printf("%d\n",ans);
	//for(int i=1;i<=2*N;i++) cout<<visit[i]<<" ";
	//cout<<endl;
	work();
	return 0;
}