题解 UVA1389 【Hard Life】

· · 题解

最大密度子图模板题。

最大密度子图，即求出原图的一个子图 G'=\{V',E'\}，最大化 \frac{E'}{V'}。

设选出来 n' 个点，有 m' 条边。我们可以非常直接地想到分数规划。二分答案 \lambda\le \frac{m'}{n'}，则 n'\lambda-m\le 0。由于

我们考虑如何建图。既然有 n 又有 m，那么把每条边和每个点都作为一个网络图上的点。边和点的关系是，选了边就一定要选对应的点。每条边的收益是 1，每个点的收益是 -\lambda，然后按此跑最大权闭合子图即可。

对于求割点，我们在残量网络上 dfs，即模拟网络流的过程，即可得到选择哪些点。

#include<bits/stdc++.h>
using namespace std;
const int N=2009;
const double eps=1e-7,inf=1e4;

struct edge {int to,nxt;double c;}e[N*6]; int hd[N],tot=1;
void add(int u,int v,double c) {e[++tot]=(edge){v,hd[u],c};hd[u]=tot;}
void addh(int u,int v,double c) {add(u,v,c), add(v,u,0);}

int n,m,s,t,us[N],vs[N],d[N];

bool bfs() {
    queue<int>q; q.push(s);
    memset(d,0,sizeof(d)); d[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=hd[u],v;i;i=e[i].nxt)
            if(!d[v=e[i].to]&&e[i].c>eps) {
                d[v]=d[u]+1; q.push(v);
                if(v==t) return 1;
            }
    }
    return 0;
}
double dinic(int u,double flow) {
    if(u==t) return flow;
    double rest=flow;
    for(int i=hd[u],v;i&&rest>eps;i=e[i].nxt)
        if(d[v=e[i].to]==d[u]+1&&e[i].c>eps) {
            double use=dinic(v,min(rest,e[i].c));
            if(use<eps) d[v]=0;
            rest-=use, e[i].c-=use, e[i^1].c+=use;
        }
    return flow-rest;
} 
int cnt; bool vst[N];
void dfs(int u) {
    vst[u]=1;
    for(int i=hd[u],v;i;i=e[i].nxt)
        if(e[i].c&&!vst[v=e[i].to]) dfs(v);
}

int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        if(m==0) {puts("1\n1\n"); continue;}
        s=n+m+1, t=n+m+2;
        for(int i=1;i<=m;i++) scanf("%d%d",&us[i],&vs[i]);
        double l=0, r=m, ret=0;
        while(l+eps<r) {
            double mid=(l+r)/2;
            memset(e,0,sizeof(e)), memset(hd,0,sizeof(hd)); tot=1;
            double ans=0;
            for(int i=1;i<=m;i++) addh(s,i+n,1), ans++;
            for(int i=1;i<=n;i++) addh(i,t,mid);
            for(int i=1;i<=m;i++) addh(i+n,us[i],inf), addh(i+n,vs[i],inf);
            double tmp=0; while(bfs()) while((tmp=dinic(s,inf))>eps) ans-=tmp;
            if(ans>eps) l=mid, ret=mid;
            else r=mid;
        }
        double mid=ret; 
        memset(e,0,sizeof(e)), memset(hd,0,sizeof(hd)); tot=1;
        double ans=0;
        for(int i=1;i<=m;i++) addh(s,i+n,1), ans++;
        for(int i=1;i<=n;i++) addh(i,t,mid);
        for(int i=1;i<=m;i++) addh(i+n,us[i],inf), addh(i+n,vs[i],inf);
        double tmp=0; while(bfs()) while(tmp=dinic(s,inf));
        memset(vst,0,sizeof(vst)), cnt=0;
        dfs(s);
        for(int i=1;i<=n;i++) if(vst[i]) cnt++;
        printf("%d\n",cnt);
        for(int i=1;i<=n;i++) if(vst[i]) printf("%d\n",i); putchar('\n');
    }
    return 0;
}

这道题精度问题比较重要，比如 inf 不能开太大等。

UVA 上 AC，洛谷为啥没法交啊 qwq。