[Medium] AT_abc397_g [ABC397G] Maximize Distance

简要题意

给出一个 $n$ 个点 $m$ 条边的有向图，初始时这些边的边权均为 $0$。

你需要选定恰好 $k$ 条边将其边权改为 $1$，使得 $1$ 到 $n$ 的最短路长度最大（保证 $1\to n$ 连通）。

$2\leq n\leq 30,1\leq k\leq m\leq 100$。

思路

看到最小值最大，先二分，改为判定性问题：能否选定恰好 $k$ 条边，将其边权改为 $1$ 后，$1$ 到 $n$ 的最短路长度不小于 $x$。

首先可以发现这个“恰好”是假的，假如能够选定 $x$ 条边达成目标，则选定 $x+1$ 条边一定也可以。于是将限制改为至多 $k$ 条边。

然后发现最短路这个信息不好维护？不妨暴力一点，直接维护点 $i$ 的最短路 $d_i$。

那么我们相当于有 $n$ 个变量 $d$，需要满足一定的限制，使得 $d_1=0$ 且 $d_n\geq x$。

根据最短路的定义，应该只有这一条限制：对于边 ${(u,v)}$，${d_v\leq d_u+1}$。

另外如果 $d_v=d_u+1$，那么我们需要连一条边 $(u,v)$ 而需要 $1$ 的代价。我们需要最小化代价。

于是我们貌似需要解决一个 LP 问题？不过我不会单纯形，不过既然想到了 LP，那么就自然可以想到网络流。

根据图论建模的经典技巧（AT_abc277_h [ABC277Ex] Constrained Sums），我们可以将一个整数变量看成 $O(V)$ 个布尔变量。具体地，对于变量 $x$，可以改为记录若干个变量 $x_i=[x\geq i]$。

对应到本题中，我们可以记录 $O(n^2)$ 个变量 $d_{ij}=[d_i\geq j]$。那么可以得到一个形如下面的问题：

有一个 $n$ 个点 $m$ 条边的有向图图，限制某两个点分别为 $0/1$，你需要给其他点附一个 $01$ 值，对于原图上的边，若起点是 $1$ 且汇点是 $0$，则需要等同于边权的代价。你需要求出最小代价。

可以发现这个问题和最小割问题相同，于是求最小割即可。时间复杂度 $O(\mathrm{maxflow}(n^2,n^2+nm))$。

代码

#include <bits/stdc++.h>
#include <atcoder/maxflow>
#define X(i, j) (((i) - 1) * (n + 1) + (j))
using namespace std;

using atcoder::mf_graph;
int n, m, k;
pair<int,int> a[105];

bool check(int x){
    mf_graph<int> g(X(n, n) + 1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) g.add_edge(X(i, j), X(i, j - 1), k + 1);
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(j + 1 <= n) g.add_edge(X(a[i].second, j + 1), X(a[i].first, j), k + 1);
            g.add_edge(X(a[i].second, j), X(a[i].first, j), 1);
        }
    }
    return g.flow(X(n, x), X(1, 1)) <= k;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(int i=1;i<=m;i++) cin >> a[i].first >> a[i].second;
    int L = 0, R = n;
    while(L < R){
        int mid = (L + R + 1) >> 1;
        if(check(mid)) L = mid;
        else R = mid - 1;
    }
    cout << L << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。