浮点数好毒瘤啊

这个题调了好多次精度才过。。
做法就是一顿推公式。记住一个结论就是： 对于一张原图，新加S,T两点。给原图的每个点都add(S,i,V,0),add(i,T,2g-di+V,0)//g是二分的密度，di代表这个点的度数。V是为了防止负数出现
对于原图的边add(u,v,1,1)
然后有：C[S,T]=Vn + 2g|V’|-2|E’| //这里V是上面的含义，V’是选中的点，E’是子图的边数，那么对于每一个二分的g,我们去check是否满足C[S,T]-Vn<0，若满足就说明g可行。
至于详细的推导嘛。。。看y总的视频讲解以及胡伯涛那篇论文《最小割在信息学奥赛中的应用》

#include<bits/stdc++.h>
using namespace std;

const int N=10010,M=200010;
int q[N],d[N],cur[N],dg[N];
double f[M],sum;
int e[M],ne[M],idx,h[N],n,m,S,T,VV;

struct E{
    int a,b;
}edge[10010];

void add(int a,int b,double c,double d)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=d,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{

    memset(d,-1,sizeof d); 
    q[0]=S,cur[S]=h[S],d[S]=0;
    int hh=0,tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
double find(int u,double limit)
{
    if(u==T ) return limit;
    double flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i]>0)
        {
            double t=find(ver,min(f[i],limit-flow));
            if(t<1e-8) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

bool dinic(double mid)
{
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=m;i++)
    {
        int a=edge[i].a,b=edge[i].b;
        add(a,b,1,1);
    }
    for(int i=1;i<=n;i++) add(S,i,VV,0),add(i,T,VV+2*mid-dg[i],0);
    double r=0,flow;
    while(bfs()  ) while(flow=find(S,0x3f3f3f3f)) r+=flow;
    return 0<sum-r;
}
bool st[N];
vector<int> ans;
void dfs(int u)
{
   // printf("now fuck %d\n",u);
   if(u!=S) ans.push_back(u);
   st[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        if(!st[e[i]]&&f[i]>0) dfs(e[i]);
    }
}
int main()
{
    cin>>n>>m;
    VV=m+10;
    sum=n*VV;
    S=n+2,T=n+4;
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        edge[i]={a,b};
        dg[a]++;
        dg[b]++;
    }
    double l=0,r=m;
    while(r-l>1e-8)
    {
        double mid=(l+r)/2;
        if(dinic(mid)) l=mid;
        else r=mid;
    }
    dinic(l);dfs(S);
    //printf("%.6lf\n",l);
    if(ans.size()==0)
    {
        cout<<1<<endl<<1;
    }
    else {

        printf("%d\n",ans.size());
        for(int i=1;i<=n;i++) if(st[i]) printf("%d\n",i);
    }
    return 0;
}