POJ3155[Hard Life]

最大密度子图,推荐读一下2007年国家集训队论文(胡伯涛《最小割模型在信息学竞赛中的应用》)。


恩,还有因为做NOI2006的最大获利/profit,我不得不学了ISAP和Dinic,因为Relabel-to-front过不了!而且HLPP也过不了!所以这里就用ISAP了。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-19


DESCRIPTION:


网络流 乱做


http://acm.pku.edu.cn/JudgeOnline/problem?id=3155


*/


#include <stdio.h>


#include <string.h>


 


const int oo=(~0u)>>1;


const int MAXV=1102;


const int MAXE=6200;


typedef struct struct_edge* edge;


struct struct_edge{int v,c;edge n,b;};


struct_edge pool[MAXE];


edge top=pool;


int S,T,V;


edge adj[MAXV];


int d[MAXV],dn[MAXV+1];


void add_edge(int u,int v,int c)


{


     top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;


     top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;


     adj[u]->b=adj[v],adj[v]->b=adj[u];


}


int augment(int u,int e)


{


    if (u==T) return e;


    if (d[S]==V) return 0;


    int f=0,mind=V-1;


    for (edge i=adj[u];i;i=i->n)


        if (i->c)


        {


           if (d[u]==d[i->v]+1)


           {


              int df=augment(i->v,e<i->c?e:i->c);


              i->c-=df;


              i->b->c+=df;


              e-=df;


              f+=df;


              if (e==0) return f;


           }


           if (mind>d[i->v]) mind=d[i->v];


        }


    if (f) return f;


    else


    {


        if (!–dn[d[u]]) d[S]=V;


        else dn[d[u]=mind+1]++;


        return 0;


    }


}


int sap()


{


    int f=0;


    dn[0]=V;


    while (d[S]<V) f+=augment(S,oo);


    return f;


}


 


const int MAXN=100,MAXM=1000;


const int XX=MAXN*MAXN*MAXN;


int n,m;


int a[MAXM],b[MAXM];


bool visited[MAXN+MAXM+2];


int total;


 


void build_network(int rate)


{


     memset(adj,0,sizeof(adj));


     memset(d,0,sizeof(d));


     memset(dn,0,sizeof(dn));


     top=pool;


     S=n+m,T=m+n+1,V=n+m+2;


     for (int i=0;i<n;i++)


         add_edge(S,i,rate);


     for (int i=0;i<m;i++)


         add_edge(a[i]-1,n+i,oo),


         add_edge(b[i]-1,n+i,oo),


         add_edge(n+i,T,XX);


}


void dfs(int u)


{


     visited[u]=true;


     for (edge i=adj[u];i;i=i->n)


         if (!visited[i->v]&&i->c)


            dfs(i->v);


}


void read()


{


     scanf(“%d%d”,&n,&m);


     for (int i=0;i<m;i++)


         scanf(“%d%d”,a+i,b+i);


}


void write()


{


     if (!m)


     {


        printf(“%d\n%d\n”,1,1);


        return;


     }


     int L=0*XX,R=m*XX,best;


     do


     {


       int mid=(L+R)>>1;


       build_network(mid);


       int g=m*XX-sap();


       if (g<=0) R=mid;


       else L=mid,best=L;


     }


     while (L+1!=R);


     build_network(best);


     sap();


     dfs(S);


     for (int i=0;i<n;i++)


         if (!visited[i]) total++;


     printf(“%d\n”,total);


     for (int i=0;i<n;i++)


         if (!visited[i])


            printf(“%d\n”,i+1);


}


 


int main()


{


    read();


    write();


}