> 题目大意：给定一个无向图，求它的最大密度子图。
> 
> 到目前做过的所有网络流的题，这个应该是最难的一个，并不是因为它的编码，而
> 是分析和建模的过程。最小割模型之所以让人觉得难，是因为它并不像简单的求最
> 大流那样直观，而是牵扯到边割集的性质，有些问题要最大化某个量x，假设最小割
> 为y，那么如果从数学上可以证明x+y==c（c是个常数）的话，只要让y最小化，即
> 求出原图的最小割，用c-y即是x可以取得的最大值。这种题目关键在于数学建模和
> 对问题的透彻分析，把握量和量之间的关系，只有做到对网络流的性质了如指掌才
> 有可能顺利解决。
> 
> 题目的具体解法大家可以参考胡伯涛的论文《最小割模型在信息学竞赛中的应用》，
> 论文中给出了详细的分析。
> 
> 这里再补充一点编程时需要注意的地方：这个题目是利用分数规划进行二分求解的，
> 但这个问题的分数规划和我之前的见过的很多分数规划是不同的，之前的分数规划表
> 达式很多都是在给定区间内只有一个零点的单调函数。但这个题目不同，因为
> MiniCut=U*n-Maxmize{f(n)}，而MiniCut& lt;=U*n是恒成立的，所以
> Maxmize{f(n)}>=0恒成立，及Maxmize{f(n)}函数会先递减，然后一直为0，我们的目
> 标是找出第一个零点。所以二分应该这么写：
> 
> 
> while(r-l >= 1.0/n/n)
>         {
>             mid = (l+r) / 2;
>             BuildGraph();
>             Cut = Max_flow(s, t);
>             tmp = (U*n-Cut) / 2;
>             if(tmp > eps)  l = mid;
>             else  r = mid;
>         }
> 
> 而不能当找出一个零点时直接break。
> 
> 第二个需要注意的地方：
> 
> 对于这种输入数据：
> 
> 3 3
> 
> 1 2
> 
> 2 3
> 
> 3 1
> 
> 最后一次网络流的运行会使所有从s出发的边满流，这时候子图的顶点数为0，结果
> 输出为0，不符合题意。但是由于误差最多不会超过1/(n*n)，所以取l再做一次网络
> 流然后查解输出就可以了（解就是所有从s通过最后的参量网络可达的顶点——因为
> 这保证了不走割边，这就和论文中的讲解一致了）。
> 
> 
>  
> 
> 附代码：
> 
> #include <iostream>
> #include <cstdio>
> #include <cstring>
> using namespace std;
> 
> const int N = 110;
> const int M = 1010;
> const double INF = 1e8;
> const double eps = 1e-7;
> 
> struct node
> {
>     int u, v;
>     double c;
> }e[M*4];
> 
> int s, t, n, m, tot, d[N], que[N], h[N], level[N], nxt[M*4];
> bool visit[N], map[N][N];
> 
> double min(double x, double y)
> {
>     return  x < y ? x : y;
> }
> 
> void add(int u, int v, double c)
> {
>     e[tot].u = u;
>     e[tot].v = v;
>     e[tot].c = c;
>     nxt[tot] = h[u];
>     h[u] = tot++;
> }
> 
> bool bfs(int s, int t)
> {
>     int u, v, head, tail, p;
>     head = tail = 0;
>     que[0] = s;
>     memset(level, 0, sizeof(level));
>     memset(visit, false, sizeof(visit));
>     level[s] = 0;
>     visit[s] = true;
>     while(head <= tail)
>     {
>         u = que[head++];
>         p = h[u];
>         while(p != -1)
>         {
>             v = e[p].v;
>             if(!visit[v] && e[p].c>0)
>             {
>                 level[v] = level[u]+1;
>                 visit[v] = true;
>                 que[++tail] = v;
>             }
>             if(visit[t])  return  true;
>             p = nxt[p];
>         }
>     }
>     return  false;
> }
> 
> double dinic_dfs(double delta, int u)
> {
>     int p, v;
>     double tmp, sum = 0.0;
>     if(u == t)  return  delta;
>     p = h[u];
>     while(p != -1)
>     {
>         v = e[p].v;
>         if(level[u]+1==level[v] && e[p].c>0)
>         {
>             tmp = dinic_dfs(min(delta, e[p].c), v);
>             sum += tmp;
>             delta -= tmp;
>             e[p].c -= tmp;
>             e[p^1].c += tmp;
>         }
>         p = nxt[p];
>     }
>     return  sum;
> }
> 
> double Max_flow(int s, int t)
> {
>     double ans = 0.0;
>     while(bfs(s, t))
>         ans += dinic_dfs(INF, s);
>     return  ans;
> }
> 
> void dfs(int u)
> {
>     int p = h[u];
>     visit[u] = true;
>     while(p != -1)
>     {
>         if(e[p].c>eps && !visit[e[p].v])  dfs(e[p].v);
>         p = nxt[p];
>     }
> }
> 
> int main()
> {
>     int i, j, a, b, ans;
>     double l, r, mid, U, Cut, tmp;
>     while(scanf("%d%d", &n, &m) != EOF)
>     {
>         memset(map, false, sizeof(map));
>         memset(d, 0, sizeof(d));
>         for(i = 0; i < m; i++)
>         {
>             scanf("%d%d", &a, &b);
>             map[a][b] = true;
>             d[a]++;
>             d[b]++;
>         }
>         if(m == 0)
>         {
>             printf("1\n1\n");
>             return  0;
>         }
>         l = 0.0;
>         r = m;
>         s = 0;
>          t = n+1;
>         U = m;
>         while(r-l >= 1.0/n/n)
>         {
>             mid = (l+r) / 2;
>             tot = 0;
>             memset(h, -1, sizeof(h));
>             for(i = 1; i <= n; i++)
>             {
>                 add(s, i, U);
>                 add(i, s, 0.0);
>                 add(i, t, U+2*mid-(double)d[i]);
>                 add(t, i, 0.0);
>             }
>             for(i = 1; i <= n; i++)
>                 for(j = 1; j <= n; j++)
>                     if(map[i][j])
>                     {
>                         add(i, j, 1.0);
>                         add(j, i, 1.0);
>                     }
>             Cut = Max_flow(s, t);
>             tmp = (U*n-Cut) / 2;
>             if(tmp > eps)  l = mid;
>             else  r = mid;
>         }
>         tot = 0;
>         memset(h, -1, sizeof(h));
>         for(i = 1; i <= n; i++)
>         {
>             add(s, i, U);
>             add(i, s, 0.0);
>             add(i, t, U+2*l-(double)d[i]);
>             add(t, i, 0.0);
>         }
>         for(i = 1; i <= n; i++)
>             for(j = 1; j <= n; j++)
>                 if(map[i][j])
>                 {
>                     add(i, j, 1.0);
>                     add(j, i, 1.0);
>                 }
>         Cut = Max_flow(s, t);
>         ans = 0;
>         memset(visit, false, sizeof(visit));
>         dfs(s);
>         for(ans=0,i=1; i <= n; i++)
>             if(visit[i])
>                 ans++;
>         printf("%d\n", ans);
>         for(i = 1; i <= n; i++)
>             if(visit[i])
>                 printf("%d\n", i);
>     }
>     return 0;
> }
多谢大神帮助，终于AC了，您发的帖子真心很用心，而且对我帮助很大。