网络战争问题

解题思路

本题要求的是 $\frac{\sum_{e \in C} w_e}{\vert C \vert}$ 的最小值。这种形式的问题基本都需要用到 01 分数规划。

现在取一个值 $x$，然后我们看一下 $\frac{\sum_{e \in C} w_e}{\vert C \vert}$ 和 $x$ 的关系。

假设现在 $\frac{\sum_{e \in C} w_e}{\vert C \vert} > x$，通过变形得到 $\sum_{e \in C} w_e - \vert C \vert \cdot x > 0$，由于 $\sum_{e \in C} w_e$ 和 $x$ 都有 $\vert C \vert$ 个，因此进一步化简为 $\sum_{e \in C} (w_e - x) > 0$。

假设现在 $\frac{\sum_{e \in C} w_e}{\vert C \vert} < x$，同样可以得到 $\sum_{e \in C} (w_e - x) < 0$。

因此我们可以根据 $\sum_{e \in C} (w_e - x)$ 和 $0$ 的关系来判断 $\frac{\sum_{e \in C} w_e}{\vert C \vert}$ 和 $x$ 的关系。而这个关系是有二段性的，是可以进行二分的。

在整个范围区间内进行二分，二分出的中间值就是 $x$，如果 $\sum_{e \in C} (w_e - x) > 0$，说明 $\frac{\sum_{e \in C} w_e}{\vert C \vert} > x$，继续二分右区间。否则说明 $\frac{\sum_{e \in C} w_e}{\vert C \vert} < x$，继续二分左区间。最终得到一个固定值，就是答案。

每次需要求出 $\sum_{e \in C} (w_e - x)$，我们可以建一个新图，将所有边都减去 $x$，在新图中求一个边割集的权值和就是 $\sum_{e \in C} (w_e - x)$。

那么新图中可能存在 $w_e - x \leq 0$，对于这样的边，我们一定要选上，因为一个边割集若加上一些无法让图重新连上的边，它仍然是一个边割集，但是权值和会变小，所以这种负权值边必选。

现在已经选上所有非正边，我们需要考虑一下剩下的边该怎么选，因为边割集和流网络的割是不一样的，边割集在有流网络的割的所有边的同时，在这两个集合里面还有一些边，这些边去掉之后也能让整张图不连通，由于剩下要考虑的边都是正边，我们要让权值和越小，因此这两个集合里面的边尽量能不选就不选，因此在权值和最小的情况下，边割集一定不包含所有集合里面的边了，这时就是只剩下两个集合之间的边了，而这些边的权值和其实就是流网络的割。

通过以上的分析，我们成功将每个边割集的权值和与流网络的割的边的容量和对应起来。而边割集的最小权值和就是割的最小容量和，即最小割。

然后本题是无向图，而流网络中是有向图，我们需要将有向图和无向图对应起来，我们只需要正常建两条有向边，来回的流量会被抵消，而且流网络的割有一个特点就是保证正向边是满流反向边是 $0$ 流，所以无向图的割等价于有向图的割，不需要额外处理。

然后这里每条无向边建两条有向边，有向边在残量网络中又有反向边，所以每条无向边都要建四条边，这里和前面的某一题一样直接合并成两条边即可。

最终得出本题算法，二分找最小值，每次求一遍最小割继续二分。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 810, INF = 0x3f3f3f3f;
const double eps = 1e-8;

int n, m, S, T;
int h[N], e[M], wt[M], ne[M], idx; //邻接表，wt[] 权值
double wf[M]; //流量
int q[N], d[N], cur[N]; //队列、层数、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, wt[idx] = c, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && wf[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

double find(int u, double flow) //统计从 u 往终点能传输的最大流量，上限为 flow
{
    if(u == T) return flow;

    double rest = flow;
    for(int i = cur[u]; i != -1 && rest > eps; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && wf[i])
        {
            double k = find(j, min(rest, wf[i]));
            if(k < eps) d[j] = 0;

            wf[i] -= k;
            wf[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

double dinic(double mid) //求最小割（最大流）
{
    double res = 0; //统计非正边的权值和
    for(int i = 0; i < idx; i += 2) //枚举所有正向边
        if(wt[i] <= mid) //如果权值 <= mid，即新图中的非正边
        {
            res += wt[i] - mid; //累加到 res
            wf[i] = wf[i ^ 1] = 0; //这条边已经选上，从新图中删去
        }
        else wf[i] = wf[i ^ 1] = wt[i] - mid; //否则需要减去 mid，变成新图中的新边

    //求最小割（最大流）
    double maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf + res; //边割集的权值和 = 非正边的权值和 + 正边的权值和（最小割）
}

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

    memset(h, -1, sizeof h); //初始化邻接表

    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); //添加边（四条边合并成两条边）
    }

    //浮点数二分
    double l = 0, r = 1e7;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        if(dinic(mid) > 0) l = mid;
        else r = mid;
    }
    printf("%.2lf\n", r);

    return 0;
}