一、题目
二、解法
显然是分数规划问题，我们二分答案 (g)，那么需要检查：
[frac{sum e}{sum v}geq g
ightarrow sum e-sum vcdot ggeq0
]
第一种思路是转最大权闭合子图问题（选边），也就是选一条边就必须选对应的两个点，那么我们把边建成点跑二分图即可，但是这种方法建出来图的点数太多了。
第二种思路是考虑选取一个点集，那么内部的边是全部都要选的，计算边数可以考虑简单容斥。边数乘二等于点度数(-)只有一个点在点集的边数，后面那个东西可以考虑成割边。
因为要求最大权值，我们把它取负之后跑最小割即可，要给所有权值加上 (inf) 防止负权：
最后注意一下精度问题即可，(eps) 开 (10^{-8})，从起点开始 ( t dfs) 即可构造方案。
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int M = 1005;
#define db double
#define eps 1e-8
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,tot,ans,S,T,f[M],cur[M];
int vis[M],dis[M],a[M],b[M],d[M];
struct edge{int v;db c;int next;}e[10*M];
void add(int u,int v,db c)
{
e[++tot]=edge{v,c,f[u]},f[u]=tot;
e[++tot]=edge{u,0,f[v]},f[v]=tot;
}
int bfs()
{
for(int i=0;i<=T;i++) dis[i]=0;
queue<int> q;q.push(S);dis[S]=1;
while(!q.empty())
{
int u=q.front();q.pop();
if(u==T) return 1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dis[v] && e[i].c>eps)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return 0;
}
db dfs(int u,db ept)
{
if(u==T) return ept;
db flow=0,tmp=0;
for(int &i=cur[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1 && e[i].c>eps)
{
tmp=dfs(v,min(e[i].c,ept));
if(tmp<=eps) continue;
flow+=tmp;
ept-=tmp;
e[i].c-=tmp;
e[i^1].c+=tmp;
if(ept<=eps) break;
}
}
return flow;
}
db work(db g)
{
db res=0;S=0;T=n+1;tot=1;
for(int i=0;i<=T;i++) f[i]=0;
for(int i=1;i<=n;i++)
add(S,i,m),add(i,T,m+2*g-d[i]);
for(int i=1;i<=m;i++)
add(a[i],b[i],1),add(b[i],a[i],1);
while(bfs())
{
for(int i=0;i<=T;i++) cur[i]=f[i];
res+=dfs(S,m);
}
return res;
}
void dfs2(int u)
{
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v] && e[i].c>eps)
{
vis[v]=1;
dfs2(v);
}
}
}
signed main()
{
while(~scanf("%d %d",&n,&m))
{
for(int i=1;i<=n;i++)
vis[i]=d[i]=0;
for(int i=1;i<=m;i++)
{
a[i]=read(),b[i]=read();
d[a[i]]++;d[b[i]]++;
}
if(!m)
{
puts("1");puts("1");
continue;
}
db l=0,r=m,EPS=1.0/n/n,tmp=0;
while(r-l>EPS)
{
db mid=(l+r)/2,res=work(mid);
res=(n*m-res)/2;
if(res>eps) tmp=mid,l=mid;
else r=mid;
}
work(tmp);
dfs2(S);ans=0;
for(int i=1;i<=n;i++) ans+=vis[i];
printf("%d
",ans);
for(int i=1;i<=n;i++) if(vis[i])
printf("%d
",i);
}
}