UVA1389

· · 题解

算法

最大密度子图。

题意：

求原图 G=(V,E) 的一个子图 G' = (V',E')，使得 \dfrac{|E'|}{|V'|} 最大。

解法

考虑二分这个比值 g。

\dfrac{|E'|}{|V'|}\ge g \Leftrightarrow |E'|-g\times|V'|\ge 0

我们只关心 \max\{|E'|-g\times|V'|\} 是否大于 0。（若最大值小于 0，说明所有值都小于 0，舍去；若最大值大于 0，说明按照最大值的方案求出的子图即为解）。

要使这个式子最大，我们自然想到了最大权闭合子图。不妨将边和点都看作网络图中的节点。将边的点权设为 1，点的点权设为 -g。然后求最大权闭合子图看权是否非负即可。

建图：

得到最大的密度之后，我们根据这个密度建图、再求一遍最大权闭合子图。此时从源点能流到的节点即为最大权闭合子图，即要求的最大密度子图。

但是，由于边的容量为实数，因此我们判断一条边是否流完的时候的条件是 w>eps（eps 为一个非常小的实数）。然而，这样我们求最大密度子图的时候会出现本来不在最大密度子图中的节点被遍历到。因此要考虑排除这些点的贡献。

首先，表示边的节点是没有贡献的，其次汇点也是没有贡献的。

对于剩下的那些表示点的节点，在最大密度子图中的点的贡献自然要算上；不在其中的点，由于边的容量小于 eps，因此计算它的贡献带来的误差是极其微小的，我们算上也没关系。

将上述有贡献的节点输出即为答案。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5;
int n, m, hd[N], now[N], d[N], q[N], h, t, T, cnt, u[N], v[N], ok[N];
double l, r, eps = 1e-7, inf = 1e4, ret;
bool vis[N];
struct edge {
    int x;
    double s; 
    int nxt;
}e[N];
inline void add(int u, int v, double w) {
    e[++cnt] = edge{v, w, hd[u]};
    hd[u] = cnt;
}
inline void build(double x) {
    for (int i = 0; i <= T; ++i) {
        hd[i] = 0;
    }
    cnt = 1;
    for (int i = 1; i <= m; ++i) {
        add(0, i, 1);
        add(i, 0, 0);
        add(i, u[i] + m, inf);
        add(u[i] + m, i, 0);
        add(i, v[i] + m, inf);
        add(v[i] + m, i, 0);
    }
    for (int i = m + 1; i < T; ++i) {
        add(i, T, x);
        add(T, i, 0);
    }
}
inline bool bfs() {
    for (int i = 0; i <= T; ++i) {
        now[i] = hd[i];
        d[i] = 0;
    }
    d[q[h = t = 1] = 0] = 1;
    while (h <= t) {
        int x = q[h++];
        for (int i = hd[x]; i; i = e[i].nxt) {
            if (e[i].s > eps && !d[e[i].x]) {
                d[q[++t] = e[i].x] = d[x] + 1;
                if (e[i].x == T) {
                    return 1;
                }
            }
        }
    }
    return 0;
}
double dfs(int x, double f) {
    if (x == T) {
        return f;
    }
    double s = 0;
    for (int i = now[x]; i; i = e[i].nxt) {
        if (e[i].s > eps && d[e[i].x] == d[x] + 1) {
            double k = dfs(e[i].x, min(f - s, e[i].s));
            e[i].s -= k;
            e[i ^ 1].s += k;
            s += k;
            if (f - s <= eps) {
                now[x] = i;
                return s;
            }
        }
    }
    now[x] = 0;
    if (s < eps) {
        d[x] = 0;
    }
    return s;
}
inline bool dinic(double x) {
    build(x);
    double ans = 0, flow;
    while (bfs()) {
        while ((flow = dfs(0, 1e9)) > eps) {
            ans += flow;
        }
    }
    return m * 1.0 - ans > eps;
}
signed main() {
    while (scanf("%lld%lld", &n, &m) != EOF) {
        if (!m) {
            puts("1\n1\n");
            continue;
        } 
        l = 0;
        r = 1.0 * m;
        T = n + m + 1;
        for (int i = 1; i <= m; ++i) {
            scanf("%lld%lld", &u[i], &v[i]);
        }
        ret = 0;
        while (l + eps < r) {
            double mid = (l + r) / 2;
            if (dinic(mid)) {
                ret = l = mid;
            } else {
                r = mid;
            }
        }
        build(ret);
        double ans = 0, flow;
        while (bfs()) {
            while (flow = dfs(0, 1e9)) {
                ans += flow;
            }
        }
        for (int i = 0; i <= T; ++i) {
            vis[i] = 0;
        }
        vis[ok[0] = q[h = t = 1] = 0] = 1;
        while (h <= t) {
            int x = q[h++];
            if (x > m && x != T) {
                ok[++ok[0]] = x - m;
            }
            for (int i = hd[x]; i; i = e[i].nxt) {
                if (!vis[e[i].x] && e[i].s) {
                    vis[q[++t] = e[i].x] = 1;
                }
            }
        }
        sort(ok + 1, ok + 1 + ok[0]);
        for (int i = 0; i <= ok[0]; ++i) {
            printf("%lld\n", ok[i]);
        }
        puts("");
    }
}