题目大意：给定一个无向图，求它的最大密度子图。

到目前做过的所有网络流的题，这个应该是最难的一个，并不是因为它的编码，而
是分析和建模的过程。最小割模型之所以让人觉得难，是因为它并不像简单的求最
大流那样直观，而是牵扯到边割集的性质，有些问题要最大化某个量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;
}

• Re:发两个注意事项~没做对的同学可以参考一下。 (5592) qq605007 2012-03-12 18:02:26