记录编号	94636	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NERRC 2006][POJ3155]生活的艰辛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2014-04-01 22:04:32	内存使用	0.37 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const int SIZEN=130;
const double eps=1e-7,dINF=1e12;
double searchpre=eps;
class EDGE{
public:
	int from,to;
	double cap,flow;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
int id[SIZEN][SIZEN]={0};
int S,T,N;
int depth[SIZEN]={0},cur[SIZEN]={0};
void addedge(int from,int to,double cap){
	EDGE temp;
	temp.from=from,temp.to=to,temp.cap=cap,temp.flow=0.0;
	edges.push_back(temp);
	temp.from=to,temp.to=from,temp.cap=temp.flow=0.0;
	edges.push_back(temp);
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
	id[from][to]=tot;
}
bool BFS(void){
	bool visit[SIZEN]={0};
	queue<int> Q;
	Q.push(S);
	depth[S]=0,visit[S]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			EDGE &now=edges[c[x][i]];
			if(!visit[now.to]&&now.cap>now.flow+eps){//可以走
				visit[now.to]=true;
				depth[now.to]=depth[x]+1;
				Q.push(now.to);
			}
		}
	}
	return visit[T];
}
double DFS(int x,double a){//结点S,剩余流量a
	if(x==T||a<=eps) return a;
	double flow=0,cf;//flow是送出的流量
	for(int i=cur[x];i<c[x].size();i++){
		EDGE &now=edges[c[x][i]];
		if(depth[x]+1==depth[now.to]){//可以继续送
			cf=DFS(now.to,min(a,now.cap-now.flow));
			if(cf>eps){
				now.flow+=cf;
				edges[c[x][i]^1].flow-=cf;
				flow+=cf,a-=cf;
				if(a<eps){
					cur[x]=i+1;
					break;
				}
			}
		}
	}
	if(flow<eps) depth[x]=-1;
	return flow;
}
double Dinic(void){
	double flow=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		flow+=DFS(S,dINF);
	}
	return flow;
}
int n,m;
double lastchange=0.0;
void rebuild(double g){
	for(int i=0;i<edges.size();i++) edges[i].flow=0.0;//所有边流量清空
	for(int i=1;i<=n;i++){
		EDGE &now=edges[id[i][T]];
		now.cap-=2.0*lastchange;
		now.cap+=2.0*g;
	}
	lastchange=g;
}
int check(double g){
	rebuild(g);
	double ans=Dinic();
	ans=((m+0.0)*(n+0.0)-ans)/2.0;
	if(ans>eps) return 1;//猜小了
	else return -1;//猜大了
}
bool visit[SIZEN]={0};
void DFS(int x){
	if(visit[x]) return;
	visit[x]=true;
	for(int i=0;i<c[x].size();i++){
		EDGE &now=edges[c[x][i]];
		if(now.cap>now.flow+eps) DFS(now.to);
	}
}
void answer(void){
	DFS(S);
	vector<int> ans;
	for(int i=1;i<=n;i++) if(visit[i]) ans.push_back(i);
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);
}
double find(double left,double right){
	if(right-left<=searchpre) return left;
	double mid=(left+right)/2.0;
	int flag=check(mid);
	if(flag==1) return find(mid,right);
	else return find(left,mid);
}
void work(void){
	double ans=find(0,m+0.0);
	check(ans);
	if(ans<eps){
		printf("1\n1\n");
		return;
	}
	else answer();
}
int degree[SIZEN]={0};
void init(void){
	scanf("%d%d",&n,&m);
	searchpre=1.0/(n+0.0)/(n+0.0);
	int a,b;
	S=0,T=N=n+1;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		degree[a]++,degree[b]++;
		addedge(a,b,1.0);
		addedge(b,a,1.0);
	}
	for(int i=1;i<=n;i++){
		addedge(S,i,m+0.0);
		addedge(i,T,m-degree[i]+0.0);
	}
	lastchange=0.0;
}
int main(){
	freopen("hardlife.in","r",stdin);
	freopen("hardlife.out","w",stdout);
	init();
	work();
	return 0;
}