题目描述：

给你一个无向图，让你选一个子图，使这个子图的密度（边数/点数）最大。

输出这个子图的每个点，SPJ，如果多个最大密度，输出任意一个子图就好了。

解题报告：

胡伯涛《最小割模型在信息学竞赛中的应用》有详细的证明与解释，不在这里赘述。只写做法：

统计出每个点的度d[i]，点的下标1到n

原点s，汇点t。设边数有m。

原点s和1~n点连接，容量为m。

对于原图中的无向边a，b，连接a->b，容量1，连接b->a，容量1。

二分枚举一个double数字，左边界L = 0，右边界R = m。

跳出条件是while(R – L >= (1 / n / n))

对于每一个mid = (L + R) * 0.5。

1~n每个点和t连接，容量为m + 2 * mid – d[i]。

求最大流得到一个double数字ans。

如果 (m * n – ans) * 0.5大于0， L = mid

否则R = mid。

最后跳出的L就是最大密度。

拿这个L再重新建图，求最大流。

然后从s出发bfs或者dfs，走残留容量大于0的边，所有能到达的点就是答案。

关键部分：

double l = 0, r = m, mmin = 1.0 / n / n;

while(r - l >= mmin)

{

    double mid = (r + l) * 0.5;

    if ((m * n - build(s, t, mid)) * 0.5 > eps) l = mid;

    else r = mid;

}

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define size 2000
#define eps 1e-7
struct edge{int from, to, next;double val;}e[140000];
int v[size], que[size], dis[size], cnt, cur[size];
void insert(int from, int to, double va)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt++;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt++;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail++] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head++]]; id != -1; id = e[id].next)
            if (e[id].val > eps && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] + 1;
                que[tail++] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}

double Dinic(int n, int s, int t)
{
    int i;
    double maxflow = 0, tmp;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i++) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > eps && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])
            {que[tail++] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow += tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val += tmp;
                    if (fabs(e[que[i]].val) <= eps) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
int n ,m, ee[1002][2], num, vst[1005], re[1005], rd[1002];
void jeo(int id)
{
    vst[id] = 1;
    if (id >= 1 && id <= n) re[num++] = id;
    for(int i = v[id]; i != -1; i = e[i].next)
        if (e[i].val > 0 && !vst[e[i].to]) jeo(e[i].to);
}
double build(int s, int t, double mid)
{
    memset(v, -1, sizeof(int) * (t + 1)); cnt = 0;
    for(int i = 1; i <= n ;i++) insert(s, i, m), insert(i, t, m + 2 * mid - rd[i]);
    for(int i = 1; i <= m; i++)
        insert(ee[i][0], ee[i][1], 1), insert(ee[i][1], ee[i][0], 1);
    return Dinic(t + 1, s, t);
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        int s = 0, t = n + 1;
        memset(rd, 0, sizeof(rd));
        memset(vst, 0, sizeof(vst));
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &ee[i][0], &ee[i][1]);
            rd[ee[i][0]]++, rd[ee[i][1]]++;
        }
        double l = 0, r = m, mmin = 1.0 / n / n;
        while(r - l >= mmin)
        {
            double mid = (r + l) * 0.5;
            if ((m * n - build(s, t, mid)) * 0.5 > eps) l = mid;
            else r = mid;
        }
        build(s, t, l);num = 0;
        jeo(s);
        if (num == 0) re[num++] = 1;
        sort(re, re + num);
        printf("%d\n", num);
        for(int i = 0; i < num; i++) printf("%d\n", re[i]);
    }
    return 0;
}