$$\huge{最大密度子图}$$

$\large{前言}$

前置知识： 最大流，最小割

宣传：算法主页

$\large{定义}$

给定一个无向图 $G=(V,E)$ 。

求 $G$ 的一个子图 $G’=(V’,E’)$ ，使得 $\frac{|E’|}{|V’|}$ 最大化。

$\large{初步分析}$

容易联想到 $01$ 分数规划。

在这里用二分配合网络流即可求出答案。

$\large{建图}$

建立新图为 $G’$$’$ ， 源点为 $S$ ，汇点为 $T$。

原图中所有边在新图中权值为 $1$ 。

从 源点 $S$ 向点 $u$ 连权值为 $m$ 的边。

从 点 $u$ 向汇点 $T$ 连权值为 $2g + m - dg_u$ 的边。

其中， $g$ 表示二分的值， $dg_u$ 表示点 $u$ 在原图中连边的数量。

$\large{实现}$

以 生活的艰辛 为例。

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 2410, inf = 0x3f3f3f3f;

int n, m, S, T, ans;
int h[N], e[M], ne[M], idx;
int q[N], dep[N], cur[N], dg[N];
double c[M];
bool st[N];

struct Node{
    int a, b;
}edge[M];

void add(int u, int v, double w1, double w2)
{
    e[idx] = v, c[idx] = w1, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = w2, ne[idx] = h[v], h[v] = idx ++ ;
}

bool bfs()
{
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dep[j] == -1 && c[i] > 0)
            {
                dep[j] = dep[t] + 1;
                cur[j] = h[j];
                if (j == T)return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}

double find(int u, double limit)
{
    if (u == T)return limit;
    double flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if (dep[j] == dep[u] + 1 && c[i] > 0)
        {
            double t = find(j, min(c[i], limit - flow));
            if (!t)dep[j] = -1;
            c[i] -= t, c[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

void build(double g)
{
    idx = 0;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )add(edge[i].a, edge[i].b, 1, 1);
    for (int i = 1; i <= n; i ++ )add(S, i, m, 0), add(i, T, m + 2 * g - dg[i], 0);
}

double dinic(double g)
{
    build(g);
    double res = 0, flow;
    while (bfs())while (flow = find(S, inf))res += flow;
    return res;
}

void dfs(int u)
{
    st[u] = true;
    if (u != S)ans ++ ;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j] && c[i] > 0)
            dfs(j);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n + 1;

    for (int i = 0; i < m; i ++ )
    {
        scanf("%d%d", &edge[i].a, &edge[i].b);
        dg[edge[i].a] ++ , dg[edge[i].b] ++ ;
    }

    double l = 0, r = m;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        double t = dinic(mid);
        if (n * m - t > 0)l = mid;
        else r = mid;
    }

    dinic(l);
    dfs(S);

    if (!ans)puts("1\n1");
    else
    {
        printf("%d\n", ans);
        for (int i = 1; i <= n; i ++ )
            if (st[i])printf("%d\n", i);
    }

    return 0;
}