记录编号	190785	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NERRC 2006][POJ3155]生活的艰辛	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2015-10-04 15:44:06	内存使用	0.43 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<deque>
#include<cstring>
using namespace std;
const int SIZEN=110,SIZEM=1010,maxn=0x7fffffff/2,SIZEC=50;
const double zero=1e-8;
int N,M,H[SIZEN],d[SIZEN],tot,S,T;
bool visit[SIZEN]={0};
int father[SIZEN]={0};
double e[SIZEN],U=0;
deque<int> s[SIZEN],Q;
class poi
{
public:
	int fr,to;
}P[SIZEM];
class miku
{
public:
	int fr,to;
	double cap,flow;
	miku(){}
	miku(int a,int b,double c,double d)
	{
		fr=a;to=b;cap=c;flow=d;
	}
}E[4*(SIZEN+SIZEM)];
void read()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&P[i].fr,&P[i].to);
		d[P[i].fr]++,d[P[i].to]++;
	}
	U=M;S=0;T=N+1;
}
void add(int fr,int to,double 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 gragh(double a)
{
	tot=0;
	for(int i=S;i<=T;i++) s[i].clear();
	for(int i=1;i<=M;i++)
	{
		add(P[i].fr,P[i].to,1);
		add(P[i].to,P[i].fr,1);
	}
	for(int i=1;i<=N;i++)
	{
		add(S,i,U);add(i,T,U+2.0*a-d[i]);
	}
}
void push(int x,int t)
{
	miku &v=E[t];
	double 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]>zero) Q.push_back(v.to);
}
void use_up(int x)
{
	int mi;
	while(e[x]>zero)
	{
		mi=maxn;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.cap-v.flow<zero) continue;
			if(H[v.to]==H[x]-1)
			{
				push(x,s[x][i]);
				if(e[x]<zero) break;
			}
			else if(H[v.to]<mi) mi=H[v.to];
		}
		if(e[x]<zero) break;
		H[x]=mi+1;
	}
}
double maxflow()
{
	memset(e,0,sizeof(e));memset(H,0,sizeof(H));
	e[0]=maxn;H[0]=N;if(H[0]>20) H[0]/=6;
	for(int i=0;i<s[0].size();i++) push(0,s[0][i]);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		use_up(x);
	}
	return e[T];
}
void dfs(int x)
{
	if(x==T) return;
	visit[x]=1;
	for(int i=0;i<s[x].size();i++)
	{
		miku v=E[s[x][i]];
		if(visit[v.to]==0&&(v.cap-v.flow)>zero) {father[v.to]=x;dfs(v.to);}
	}
}
void print()
{
	dfs(S);
	int ans=0;
	for(int i=1;i<=N;i++)
		if(visit[i]==1) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=N;i++)
		if(visit[i]==1) printf("%d\n",i);
}
void work()
{
	double l=1.0/N,r=M,tem=1.0/(N*N);
	for(int i=1;i<=50;i++)
	{
		if((r-l)<tem) break;
		double mid=(l+r)/2;
		gragh(mid);
		if(((double)U*N-maxflow())/2.0>zero) l=mid;
		else r=mid;
		if((r-l)<tem) break;
	}
	gragh(l);maxflow();
	if(r<zero)
	{
		printf("1\n1\n");
	}
	else print();
}
int main()
{
	freopen("hardlife.in","r",stdin);
	freopen("hardlife.out","w",stdout);
	read();
	work();
	return 0;
}