【POJ3155】Hard Life-01分数规划+最小割

测试地址：Hard Life
题目大意：有一个无向图，要从里面选出一个子图，使得边数和点数的比最大，输出一个合法方案。
做法：本题需要用到01分数规划+最小割。
首先要求比值最大，我们立刻想到01分数规划的套路，二分比值，这样就变成判定性问题：存不存在一个子图使得 $| E | - k | V | > 0$ 。
怎么样选出一个合法的子图？注意到，如果我们选了一条边，那么这条边的两个端点必须全部选上，而且选一条边的收益是 $1$ ，选一个点的成本是 $k$ 。要求收益最大的话，这显然就是一个最大权闭合子图的模型了。求出最大流后，沿着残余网络能到达的点就是我们选择的子图的边和点了。
这题有一个非常恶心的地方就是精度。因为你在二分的时候，左右端点无限逼近最优点，但只要稍微偏移一点，就根本不存在方案，所以我们令出二分后的左端点为 $l$ ，我们应该令 $k = l - e p s$ 再做一次最大流，这样就能保证一定能取到一个方案。注意上述问题后，再特判答案为 $0$ 的情况（即 $m = 0$ ）即可。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
const double inf=1000000000.0;
const double eps=1e-8;
int n,m,S,T,first[2010]={0},tot=1,last;
int lvl[2010],cur[2010],h,t,q[2010];
int cnt,ans[2010];
bool vis[2010]={0};
struct edge
{
    int v,next;
    double f;
}e[50010];

void insert(int a,int b,double f)
{
    e[++tot].v=b,e[tot].next=first[a],e[tot].f=f,first[a]=tot;
    e[++tot].v=a,e[tot].next=first[b],e[tot].f=0.0,first[b]=tot;
}

void init()
{
    scanf("%d%d",&n,&m);
    S=n+m+1,T=n+m+2;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        insert(S,n+i,1.0);
        scanf("%d%d",&a,&b);
        insert(n+i,a,inf);
        insert(n+i,b,inf);
    }
    last=tot;
    for(int i=1;i<=n;i++)
        insert(i,T,0.0);
}

bool makelevel()
{
    for(int i=1;i<=T;i++)
        lvl[i]=-1,cur[i]=first[i];
    lvl[S]=0;
    h=t=1;
    q[1]=S;
    while(h<=t)
    {
        int v=q[h++];
        for(int i=first[v];i;i=e[i].next)
            if (e[i].f>eps&&lvl[e[i].v]==-1)
            {
                lvl[e[i].v]=lvl[v]+1;
                q[++t]=e[i].v;
            }
    }
    return lvl[T]!=-1;
}

double maxflow(int v,double maxf)
{
    double ret=0.0,f;
    if (v==T) return maxf;
    for(int i=cur[v];i;i=e[i].next)
    {
        if (e[i].f>eps&&lvl[e[i].v]==lvl[v]+1)
        {
            f=maxflow(e[i].v,min(maxf-ret,e[i].f));
            ret+=f;
            e[i].f-=f;
            e[i^1].f+=f;
            if (maxf-ret<eps) break;
        }
        cur[v]=i;
    }
    if (ret<eps) lvl[v]=-1;
    return ret;
}

bool dinic()
{
    double maxf=0.0;
    while(makelevel()) maxf+=maxflow(S,inf);
    return (double)m-maxf>eps;
}

void findsol()
{
    h=t=1;
    q[1]=S;
    while(h<=t)
    {
        int v=q[h++];
        for(int i=first[v];i;i=e[i].next)
            if (e[i].f>eps&&!vis[e[i].v])
            {
                vis[e[i].v]=1;
                q[++t]=e[i].v;
            }
    }
}

void modify(double x)
{
    tot=1;
    for(int i=1;i<=m;i++)
    {
        e[++tot].f=1.0,e[++tot].f=0.0;
        e[++tot].f=inf,e[++tot].f=0.0;
        e[++tot].f=inf,e[++tot].f=0.0;
    }
    for(int i=1;i<=n;i++)
        e[++tot].f=x,e[++tot].f=0.0;
}

void work()
{
    if (!m) {printf("1
1");return;}
    double l=0.0,r=(double)m;
    while(r-l>=eps)
    {
        double mid=(l+r)/2.0;
        modify(mid);
        if (dinic()) l=mid;
        else r=mid;
    }

    modify(l-eps);
    dinic();
    findsol();
    cnt=0;
    for(int i=last+1,j=1;i<=tot;i+=2,j++)
        if (vis[j]) ans[++cnt]=j;

    printf("%d
",cnt);
    for(int i=1;i<=cnt;i++)
        printf("%d
",ans[i]);
}

int main()
{
    init();
    work();

    return 0;
}