POJ3155 Hard Life [最大密度子图]

 

题意：最大密度子图

---

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=,M=,INF=1e9;

const double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,u[N],v[N],s,t;

struct edge{

    int v,ne;

    double c,f;

}e[M<<];

int cnt,h[N];

inline void ins(int u,int v,double c){

    cnt++;

    e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].c=;e[cnt].f=;e[cnt].ne=h[v];h[v]=cnt;

}

int cur[N],d[N],vis[N];

int q[N],head,tail;

bool bfs(){

    head=tail=;

    memset(vis,,sizeof(vis));

    d[s]=;vis[s]=;q[tail++]=s;

    while(head!=tail){

        int u=q[head++];

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v;

            if(!vis[v]&&e[i].c>e[i].f){

                vis[v]=;d[v]=d[u]+;

                q[tail++]=v;

                if(v==t) return true;

            }

        }

    }

    return false;

}

double dfs(int u,double a){

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

    double flow=,f;

    for(int &i=cur[u];i;i=e[i].ne){

        int v=e[i].v;

        if(d[v]==d[u]+&&(f=dfs(v,min(e[i].c-e[i].f,a)))>){

            flow+=f;

            e[i].f+=f;

            e[((i-)^)+].f-=f;

            a-=f;

            if(a==) break;

        }

    }

    if(a) d[u]=-;

    return flow;

}

double dinic(){

    double flow=;

    while(bfs()){

        for(int i=s;i<=t;i++) cur[i]=h[i];

        flow+=dfs(s,INF);

    }

    //printf("dinic %lf\n",flow);

    return flow;

}

void bfsSol(){

    head=tail=;

    memset(vis,,sizeof(vis));

    q[tail++]=s;vis[s]=;

    while(head!=tail){

        int u=q[head++];

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v;

            if(!vis[v]&&e[i].c>e[i].f){

                vis[v]=;

                q[tail++]=v;

            }

        }

    }

}

bool check(double x){

    cnt=;

    memset(h,,sizeof(h));

    for(int i=;i<=n;i++) ins(i,t,x);

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

        ins(s,n+i,);

        ins(n+i,u[i],INF);

        ins(n+i,v[i],INF);

    }

    return m-dinic()>eps;//eps

}

void solve(){

    double l=1.0/n,r=m,eps=1.0/(n*n),ans=;

    while(r-l>eps){

        double mid=(l+r)/;//printf("erfen %lf %lf %lf\n",l,r,mid);

        if(check(mid)) ans=max(ans,mid),l=mid+eps;

        else r=mid-eps;

    }

    //printf("hi %lf\n",l);

    check(ans);

    bfsSol();

    int num=;

    for(int i=;i<=n;i++) if(vis[i]) num++;

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

    for(int i=;i<=n;i++) if(vis[i]) printf("%d\n",i);

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();m=read();s=;t=n+m+;

    if(!m){printf("1\n1");return ;}

    for(int i=;i<=m;i++) u[i]=read(),v[i]=read();

    solve();

}

1月24日代码..二分各种处理精度

---

今天又写了一次，只要$dinic$中判断$a==0$加一个精度就可以过了...

另一种做法不学了...

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=,M=,INF=1e9;

const double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,u[N],v[N],s,t;

struct edge{

    int v,ne;

    double c,f;

}e[M<<];

int cnt,h[N];

inline void ins(int u,int v,double c){

    cnt++;

    e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].c=;e[cnt].f=;e[cnt].ne=h[v];h[v]=cnt;

}

bool vis[N];

int d[N],q[N],head,tail;

int cur[N];

bool bfs(){

    memset(vis,,sizeof(vis));

    head=tail=;

    d[s]=;vis[s]=;q[tail++]=s;

    while(head!=tail){

        int u=q[head++];

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v;

            if(!vis[v]&&e[i].c>e[i].f){

                vis[v]=;

                q[tail++]=v;

                d[v]=d[u]+;

                if(v==t) return true;

            }

        }

    }

    return false;

}

double dfs(int u,double a){

    if(u==t||abs(a)<eps) return a;

    double flow=,f;

    for(int &i=cur[u];i;i=e[i].ne){

        int v=e[i].v;

        if(d[v]==d[u]+&&(f=dfs(v,min(e[i].c-e[i].f,a)))>){

            flow+=f;

            e[i].f+=f;

            e[((i-)^)+].f-=f;

            a-=f;

            if(a==) break;

        }

    }

    if(a) d[u]=-;

    return flow;

}

double dinic(){

    double flow=;

    while(bfs()){

        for(int i=s;i<=t;i++) cur[i]=h[i];

        flow+=dfs(s,INF);

    }

    return flow;

}

void bfsSol(){

    memset(vis,,sizeof(vis));

    head=tail=;

    q[tail++]=s;

    while(head!=tail){

        int u=q[head++];

        for(int i=h[u];i;i=e[i].ne)

            if(!vis[e[i].v]&&e[i].c>e[i].f)

                vis[e[i].v]=,q[tail++]=e[i].v;

    }

}

bool check(double g){

    cnt=;memset(h,,sizeof(h));

    for(int i=;i<=n;i++) ins(i,t,g);

    for(int i=;i<=m;i++) ins(s,n+i,),ins(n+i,u[i],INF),ins(n+i,v[i],INF);

    return m-dinic()>eps;

}

void solve(){

    double l=1.0/n,r=m,eps=1.0/n/n;

    while(r-l>eps){

        double mid=(l+r)/2.0;//printf("mid %lf %lf %lf\n",l,r,mid);

        if(check(mid)) l=mid;

        else r=mid;

    }

    check(l);

    bfsSol();

    int ans=;

    for(int i=;i<=n;i++) if(vis[i]) ans++;

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

    for(int i=;i<=n;i++) if(vis[i]) printf("%d\n",i);

}

int main(){

    //freopen("in","r",stdin);

    n=read();m=read();

    if(!m){printf("1\n1");return ;}

    s=;t=n+m+;

    for(int i=;i<=m;i++) u[i]=read(),v[i]=read();

    solve();

}