poj3155 最大密度子图

求最大密度子图

记得在最后一次寻找的时候记得将进入的边放大那么一点点，这样有利于当每条边都满流的情况下会选择点

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

#include <vector>

#include <queue>

#include <cmath>

using namespace std;

const int maxn=;

const double eps=0.00000001;

const double INF=*;

vector<int>ans;

struct Dinic

{

     struct Edge

     {

         int from,to;

         double cap,flow;

         Edge(int cfrom=,int cto=,double ccap=,double cflow=)

         {

             from=cfrom; to=cto; cap=ccap; flow=cflow;

         }

     };

     int n,m,s,t;

     vector<Edge>edges;

     vector<int>G[maxn];

     bool vis[maxn];

     int d[maxn];

     int cur[maxn];

     void init(int n)

     {

         this->n=n;

         m=;

         edges.clear();

         for(int i=; i<=n; i++)G[i].clear();

     }

     void AddEdge(int from,int to,double cap)

     {

           edges.push_back(Edge(from,to,cap,));

           edges.push_back(Edge(to,from,,));

           m+=;

           G[from].push_back(m-);

           G[to].push_back(m-);

     }

     bool BFS()

     {

         memset(vis,false,sizeof(vis));

         queue<int>Q;

         Q.push(s);

         d[s]=;

         vis[s]=;

         while(!Q.empty())

         {

             int x=Q.front(); Q.pop();

             for(int i=; i<G[x].size(); i++)

             {

                 Edge &e =edges[G[x][i]];

                 if(vis[e.to]==false&&e.cap>e.flow)

                 {

                     vis[e.to]=;

                     d[e.to]=d[x]+;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     double DFS(int x, double a)

     {

         if(x==t||a==)return a;

        double flow=,f;

        for(int &i=cur[x]; i<G[x].size(); i++)

        {

            Edge &e=edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

            {

                e.flow+=f;

                edges[G[x][i]^].flow-=f;

                flow+=f;

                a-=f;

                if(a==)break;

            }

        }

        return flow;

     }

     double Maxflow(int s,int t)

     {

         this->s=s; this->t=t;

         double flow=;

         while(BFS())

         {

             memset(cur,,sizeof(cur));

             flow+=DFS(s,INF);

         }

         return flow;

     }

     void finde(int x)

     {

         vis[x]=;

         ans.push_back(x);

         for(int i=;i<G[x].size(); i++)

         {

             Edge &e=edges[G[x][i]];

             if(vis[e.to]||e.cap<=e.flow)continue;

             finde(e.to);

         }

     }

     void solve()

     {

         memset(vis,false,sizeof(vis));

         vis[s]=;

         vis[t]=;

         for(int i=; i<G[s].size(); i++)

         {

             Edge &e=edges[G[s][i]];

             if(vis[e.to]||e.cap<=e.flow)continue;

                finde(e.to);

         }

     }

}T;

int d[maxn];

int A[],B[];

double U;

void build(int n,int m,double g,int op=)

{

    T.init(n+);

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

    {

        T.AddEdge(n+,i,U+op*eps*);

        T.AddEdge(i,n+,U+g*-d[i]);

    }

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

    {

        T.AddEdge(A[i],B[i],);

        T.AddEdge(B[i],A[i],);

    }

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)==)

    {

        if(m==)

        {

            printf("1\n1\n");continue;

        }

        memset(d,,sizeof(d));

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

        {

            scanf("%d%d",&A[i],&B[i]);

            d[A[i]]++;d[B[i]]++;

        }

        U=m;

        double cL=0.0,cR=1.0*m;

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

        {

            double mid=(cL+cR)/;

            build(n,m,mid);

            double ans=T.Maxflow(n+,n+);

            ans=(U*n-ans)/;

            if(ans>) cL=mid;

            else cR=mid;

        }

        build(n,m,cL,);

        T.Maxflow(n+,n+);

        ans.clear();

        T.solve();

        sort(ans.begin(),ans.end());

        int ge=unique(ans.begin(),ans.end())-ans.begin();

        printf("%d\n",ge);

        for(int i=; i<ge;i++)

            printf("%d\n",ans[i]);

    }

    return ;

}