记录编号	155734	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NERRC 2006][POJ3155]生活的艰辛	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2015-03-30 08:50:52	内存使用	0.32 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============
struct adj{
	int from,to;
	double cap,flow;
	adj (int from=0,int to=0,double cap=0,double flow=0):from(from),to(to),cap(cap),flow(flow){}
};
///==============var declaration=================
const int MAXN=110;
int n,m,S,T,tot=0;
bool FindAns=false;
int d[MAXN],cur[MAXN],pa[MAXN],deg[MAXN],gap[MAXN];
double low,high,mid;
vector <int> G[MAXN];
vector <adj> Edge;
///==============function declaration============
void MakeGraph();
bool MaxFlow();
void add_edge(int from,int to,double cap,double flow);
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("hardlife.in","r",stdin);
   freopen("hardlife.out","w",stdout);
	//#endif 
	scanf("%d%d",&n,&m);T=n+1;
	if (m==0){
		printf("1\n1\n");
		return 0;
	}
	for(int i=1;i<=m;i++){
		int s,e;scanf("%d%d",&s,&e);
		G[s].push_back(tot++);G[e].push_back(tot++);
		Edge.push_back(adj(s,e,1,0));Edge.push_back(adj(e,s,1,0));
		deg[s]++;deg[e]++;
	}
	for(int i=1;i<=n;i++){
		add_edge(S,i,0,0);
		add_edge(i,T,0,0);
	}
	low=0,high=n;
	while (low+0.00000001<=high){
		mid=(low+high)/2;
		MakeGraph();
		if (MaxFlow())
			low=mid;
		else
			high=mid;
	}
	mid=low;
	MakeGraph();FindAns=true;
	MaxFlow();
   return 0;
}
///================fuction code====================
void add_edge(int from,int to,double cap,double flow){
	G[from].push_back(tot++);G[to].push_back(tot++);
	Edge.push_back(adj(from,to,cap,flow));
	Edge.push_back(adj(to,from,0,0));
}
void MakeGraph(){
	for(int i=0;i<tot;i++){
		adj &e=Edge[i];
		if (e.from==S)
			e.cap=m;
		else if (e.to==T)
			e.cap=m+2*mid-deg[e.from];
		e.flow=0;
	}
}
void BFS(){
	queue <int> Q;Q.push(T);
	memset(gap,0,sizeof(gap));memset(d,-1,sizeof(d));
	memset(cur,0,sizeof(d));d[T]=0;
	while (!Q.empty()){
		int x=Q.front();Q.pop();
		int siz=G[x].size();gap[d[x]]++;
		for(int i=0;i<siz;i++){
			adj &e=Edge[G[x][i]];
			if (d[e.to]==-1){
				d[e.to]=d[x]+1;
				Q.push(e.to);
			}
		}
	}
}
double argument(){
	int x=T;double flow=1000000000000000000.0;
	while (x!=S){
		adj &e=Edge[pa[x]];
		flow=min(e.cap-e.flow,flow);
		x=e.from;
	}
	x=T;
	while (x!=S){
		Edge[pa[x]].flow+=flow;
		Edge[pa[x]^1].flow-=flow;
		x=Edge[pa[x]].from;
	}
	return flow;
}
bool MaxFlow(){
	BFS();
	double flow=0;
	int x=S;
	while (d[S]<=T){
		if (x==T){
			flow+=argument();
			x=S;
		}
		int siz=G[x].size();bool suc=false;
		for(int i=cur[x];i<siz;i++){
			adj &e=Edge[G[x][i]];
			if (d[e.to]==d[x]-1&&e.cap>e.flow){
				pa[e.to]=G[x][i];cur[x]=i;
				x=e.to;suc=true;break;
			}
		}
		if (!suc){
			int mind=T;
			for(int i=0;i<siz;i++){
				adj &e=Edge[G[x][i]];
				if (e.cap>e.flow)
					mind=min(mind,d[e.to]);
			}
			if (--gap[d[x]]==0) break;
			gap[d[x]=mind+1]++;
			cur[x]=0;
			if (x!=S)
				x=Edge[pa[x]].from;
		}
	}
	if (!FindAns)
		return m*n-flow>0;
	int anssiz=0;
	queue <int> Q;Q.push(S);
	bool vis[MAXN];memset(vis,false,sizeof(vis));
	while (!Q.empty()){
		int x=Q.front();Q.pop();
		if (x>=1&&x<T) anssiz++;
		int siz=G[x].size();
		for(int i=0;i<siz;i++){
			adj &e=Edge[G[x][i]];
			if ((e.cap-e.flow)>eps&&!vis[e.to])
				Q.push(e.to),vis[e.to]=true;
		}
	}
	printf("%d\n",anssiz);
	for(int i=1;i<=n;i++)
		if (vis[i])
			printf("%d\n",i);
}