伊基的故事 I - 道路重建问题

解题思路

本题要我们将某一条边的容量变大，使得整个图的最大流变大。其实就是让我们找该流网络的关键边。

我们可以先求一个最大可行流 $f$，然后可以发现，如果某条边本身就满足 $f(u, v) < c(u, v)$，即没有流满，那么这条边再增加容量也不会使整张图的最大流变大，因此没有流满的边不可能是关键边。所以只有满流的边才有可能是关键边。

而某一条满流的边 $(u, v)$ 是关键边所需要的条件是什么呢，可以发现，如果在给该边 $( u, v)$ 增加容量之前，从 $S$ 到 $u$ 存在增广路径，从 $v$ 到 $T$ 存在增广路径，那么该边增加容量之后，就会存在一条从 $S$ 到 $T$ 的增广路径，那么该边就是一条关键边。

得出以上结论之后，求关键边就很简单了，我们先求一遍最大流，然后在残量网络中求一下从源点经过容量 $> 0$ 的边能到的点，再求一下所有经过容量 $> 0$ 的边能到汇点的点。然后枚举所有的边，判断一下这条边是不是满流，同时判断一下这条边的两个点 $u, v$，$u$ 能不能从源点走到，能不能从 $v$ 走到汇点。如果都满足则说明这条边就是一条关键边。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
//st_s[i] 记录残量网络中 s 经过容量 > 0 的边是否能到 i
//st_t[i] 记录残量网络中 i 经过容量 > 0 的边是否能到 t
bool st_s[N], st_t[N];

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, 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] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

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

int find(int u, int flow) //从 u 往汇点传输尽可能多的流量，上限是 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        int j = e[i];

        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

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

int dinic() //dinic算法求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

//寻找在残量网络中从 u 开始只经过容量 > 0 的边能到达的所有点，并进行标记
//t = 0 表示当前走的就是正向边，t = 1 表示当前走的是反向边，判断是否满流需要观察正向边
void dfs(int u, bool st[], int t)
{
    st[u] = true; //标记能走到 u

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i], k = w[i ^ t]; //j 表示往下走到的节点，k 表示当前边的容量（观察的是正向边）
        if(k && !st[j]) //如果容量 > 0 且当前点还没走过
            dfs(j, st, t); //递归搜索
    }
}

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

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

    //建立残量网络
    S = 0, T = n - 1; //源点、汇点
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); //添加边
    }

    dinic(); //求最大流

    dfs(S, st_s, 0); //在残量网络中找出所有从 S 只经过容量 > 0 的边能到达的点
    dfs(T, st_t, 1); //在残量网络中找出所有只经过容量 > 0 的边能到达 T 的点

    int res = 0; //记录关键边的数量
    for(int i = 0; i < m * 2; i += 2) //枚举正向边
        if(!w[i] && st_s[e[i ^ 1]] && st_t[e[i]]) //如果当前边满流，且能从 S 到达，且能到达 T
            res++; //说明找到一条关键边，关键边数量 + 1

    printf("%d\n", res);

    return 0;
}