题意描述

北大ACM队的远足

在有向无环图中，求用两段给定长度的线段覆盖后，从 $s\to t$ 经过桥的长度的最小值。

其中覆盖是指忽略覆盖段的桥。$n\leq 10^5,m\leq 2\times 10^5$。

算法分析

算法思路和代码实现参考 lyd 老师的《算法竞赛进阶指南》

本题算法主要流程：

1. 处理出有向图的必经边。
2. 任意求出一条最短路路径。
3. 在最短路上进行线段覆盖。

【有向图的必经边】

求有向无环图中的必经边，比求有向图的必经边（圆方树）简单很多。

只需要正反建图，分别拓扑排序统计某个点 $i$ 到起点的路径总数 $ds(i)$ 和到终点的路径总数 $dt(i)$。

假设某条边 $(u,v)$，其中 $ds(u) + dt(v)=ds(t)$，那么这条边是必经边。

值得注意的是路径条数可能很大，即使 long long 也无法承受，高精度又太过繁琐且费时。

根据加法满足取模运算（即 $\rm (a+b)\ mod\ p=(a\ mod\ p+b\ mod \ p)\ mod\ p$），我们可以利用 Hash 的思想。

将所有路径条数都对一个大质数取模，进行判断。

当然，如果对单模数不太放心，可以使用双模数进行判断。（例如孪生素数 1e9+7 和 1e9+9 冲突概率极低）

【最短路路径】

因为是 DAG（有向无环图），处理十分简单，在正向拓扑排序的同时记录路径即可。

但是我们需要证明的是，任选一条最短路都是对的。

因为值得思考的是，不同的最短路，是否会因为必经边的分布疏密不同而导致覆盖结果不同。

其实可以证明，任意一条最短路，必经边的分布疏密（即相邻两条必经边之间的线段长度）是一样的。

引理一：必经边的排布顺序相同。（即不同最短路径，经过必经边的顺序相同）

证明：如果排布顺序不同，显然图上出现了环，与 DAG 的定义不符。

当然还有：

引理二：相邻必经边之间的线段长度相同。

证明：如果出现两条最短路 $S_1$ 和 $S_2$，假设其中必经边 $E_1$ 和 $E_2$ 之间的距离分别为 $D_1$ 和 $D_2$。

不妨设 $D_1>D_2$，那么显然将 $S_1$ 中的路径换为 $D_2$ 这一段时，$S_1$ 更短，这与最短路的定义不符。

综上，任选一条最短路，化为链之后的情况都是一模一样的。

同时根据以上的证明，也可以发现选取最短路一定是最优的。（贪心证明）

【线段上的覆盖问题】

处理出最短路之后，问题转化为利用两条长度为 $q$ 的线段覆盖最短路。

我们需要利用 DP 进行线段覆盖。

显然覆盖有两种情况：

1. 两段线段不相连，且 左边线段的右端点 与 右边线段的左端点 不在同一线段中。
2. 两段线段相连。

至于左边线段的右端点 与 右边线段的左端点 在同一线段中的情况，显然可以通过平移变为情况 $2$。

对于情况 $1$，我们可以分别对于每一条线段 $i$，统计：

1. 用一个 $q$ 覆盖线段 $1\sim i$ 的剩余最小值 $ds(i)$。
2. 用一个 $q$ 覆盖线段 $i+1\sim tot$ 的剩余最小值 $dt(i)$。

然后枚举划分点，值得注意的是，我们需要枚举的是点，而这里的 $i$ 为线段，所以：

$$ans=\min_{1\leq i\leq tot+1}\{ds(i-1)+dt(i)\}$$

当然这里 $i=1$ 和 $i=tot+1$ 的情况可以忽略，因为用一段 $q$ 覆盖肯定比不上情况 $2$。

对于情况 $2$ 的统计更加简单，只需要用长度为 $2\times q$ 的线段覆盖即可。

【小技巧】

情况这么多，还要建反图，代码看上去会十分不可写。

实际上如果利用一些小 trick，代码会变得简洁很多。

1. 存图利用成对变换的性质，奇数边存正图，偶数边存反图。（这样也不用写两遍 topo 排序了）
2. 利用 pre 不断递归来记录最短路的路径。

代码实现

个人感觉还挺有可读性的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
const int M = 200010;
typedef long long LL;
const LL MOD = 1e9 + 7;
const LL INF = 0x7fffffff;

int n, m, s, t, q, cnt, tot;
int head[N], pre[N];
struct Edge{int nxt, to, val; } ed[M*2];
LL f[2][N], deg[2][N], dis[N], a[M], sum[M], sumb[M], ds[M], dt[M];
bool bridge[M*2], b[M];

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
//多数要清空。
void Init(){
    memset(head, 0, sizeof(head));
    memset(deg, 0, sizeof(deg));
    memset(f, 0, sizeof(f));
    memset(bridge, false, sizeof(bridge));
    memset(a, 0, sizeof(a));
    memset(b, false, sizeof(b));
    cnt = 1; tot = 0;
}

void add(int u, int v, int w){
    ed[++cnt] = (Edge){head[u], v, w};
    head[u] = cnt;
}

void topo(int s, int opt){
    queue<int> q;
    if(!opt){//对于正向 topo 时记录最短路路径。
        memset(dis, 0x3f, sizeof(dis));
        dis[s] = 0;
    }
    f[opt][s] = 1;
    for(int i = 1; i <= n; i ++)
        if(!deg[opt][i]) q.push(i);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = ed[i].nxt)
            if((i & 1) == opt){//小 trick。
                int v = ed[i].to, w = ed[i].val;
                f[opt][v] = (f[opt][v] + f[opt][u]) % MOD;
                if(opt == 0 && dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    pre[v] = i;
                }
                if(!--deg[opt][v]) q.push(v);
            }
    }
}

int main(){
    int T = read();
    while(T --){
        Init();
        n = read(), m = read(), s = read() + 1, t = read() + 1, q = read();
        for(int i = 1; i <= m; i ++){
            int u = read() + 1, v = read() + 1, w = read();
            add(u, v, w), add(v, u, w);
            deg[0][v] ++; deg[1][u] ++;
        }
        topo(s, 0);
        if(!f[0][t]) {puts("-1"); continue;} //判无解。
        topo(t, 1);
        for(int i = 2; i <= cnt; i += 2){
            int u = ed[i ^ 1].to, v = ed[i].to;
            if(f[0][u] * f[1][v] % MOD == f[0][t])
                bridge[i] = bridge[i ^ 1] = true;
        }
        int now = t;
        while(now != s){
            tot ++;
            a[tot] = ed[pre[now]].val;
            b[tot] = bridge[pre[now]];
            now = ed[pre[now] ^ 1].to;
        }
        //其实根据对称性，不反过来也是可以的。
        reverse(a + 1, a + tot + 1);
        reverse(b + 1, b + tot + 1);
        for(int i = 1; i <= tot; i ++){
            sum[i] = sum[i - 1] + a[i];
            sumb[i] = sumb[i - 1] + (b[i] ? a[i] : 0); 
        }
        for(int i = 1, j = 0; i <= tot; i ++){
            while(sum[i] - sum[j] > q) j ++;
            ds[i] = ds[i - 1] + (b[i] ? a[i] : 0);
            LL tmp = sumb[j];
            if(b[j]) tmp -= q - (sum[i] - sum[j]);
            ds[i] = min(ds[i], tmp);
        }
        for(int i = tot, j = tot + 1; i; i --){
            while(sum[j - 1] - sum[i - 1] > q) j --;
            dt[i] = dt[i + 1] + (b[i] ? a[i] : 0);
            LL tmp = sumb[tot] - sumb[j - 1];
            if(b[j]) tmp -= q - (sum[j - 1] - sum[i - 1]);
            dt[i] = min(dt[i], tmp);
        }
        LL ans = INF;
        for(int i = 1; i <= tot + 1; i ++)
            ans = min(ans, ds[i - 1] + dt[i]);
        //以上是两段分别覆盖，一下是两段一起覆盖。
        for(int i = 1, j = 0; i <= tot; i ++){
            while(sum[i] - sum[j] > 2 * q) j ++;
            LL tmp = sumb[j] + sumb[tot] - sumb[i];
            if(b[j]) tmp -= 2 * q - (sum[i] - sum[j]);
            ans = min(ans, tmp); 
        }
        printf("%lld\n", ans);
    }
    return 0;
}

总结

利用 DAG 的性质可以解决很多问题。

最后再次鸣谢 lyd 老师的优美代码和书籍。

完结撒花。