题解 P2149 【[SDOI2009]Elaxia的路线】

· · 题解

似乎有朋友跑两遍拓扑，实际上本题背景是无向图，定序一下跑一边topo即可
本题就是求无向图两点对最短路的最长公共路径。
分析可知，我们必须有一种手段得知一条边是否在最短路径上。
设一条边为(u, v), 长度为w(u, v),ds(p)为起点到p的最短路,dt(p)为终点到p的最短路,p∈V.
则所有s到t最短路上的边应当满足ds(u)+ w(u, v) + dt(v) == ds(t).
以上说明均在有向图的范畴，无向图则将一条连接u, v的边看做(u, v)和(v, u).
因而可以确定该无向图上的所有s到t的最短路的成分。 然后，若一条边满足均在两个人的最短路径上就可以被考虑成公共路径的一部分。
因为两对点之间的最短路可能有多条，所以不能简单地把找到的边统计。但是最长公共边应当是一条链，因而考虑topo+dp。
因为所求边必然是无向图上的链，而且是由满足同时在一组两个最短路上的边组成的链。所以对符合条件的边在拓扑之前确定一下顺序，将无向边转为有向边才能topo。应该选择哪一个方向呢？我们只要确保链上的边均指向一个方向。不妨想像一下走路的过程，我们可以将离某个起点较近的边的端点标为边的发出点，较远的点标为边的指向点。
下面附代码

#include <cstdio>
#include <cstring>
#include <queue>
#define pii pair<int, int>
#define max(i, j) (i) > (j) ? (i) : (j)

using namespace std;

int head[1510], ver[3000010], wei[3000010], nex[3000010], tot;
int hd[1510], vr[3000010], wi[3000010], nx[3000010], tt;
int ind[1510], ans[1510];
int n, m, x1, y1, x2, y2;
int d[4][1510];

inline void add(int u, int v, int w) {
    ver[tot] = v; wei[tot] = w; nex[tot] = head[u]; head[u] = tot++;
}

inline void ad(int u, int v, int w) {
    vr[tt] = v; wi[tt] = w; nx[tt] = hd[u]; hd[u] = tt++;
}

void dijkstra(int id, int s) {
    priority_queue<pii> q;
    memset(d[id], 0x3f, sizeof(d[id]));
    d[id][s] = 0; q.push(make_pair(0, s));
    while(!q.empty()) {
        int cur = q.top().second, dmen = -q.top().first; q.pop();
        if(dmen > d[id][cur]) continue;
        for(int i = head[cur]; i != -1; i = nex[i]) if(d[id][ver[i]] > d[id][cur] + wei[i]){
            d[id][ver[i]] = d[id][cur] + wei[i]; q.push(make_pair(-d[id][ver[i]], ver[i]));
        }
    }
}

void topo() {
    queue<int> q; memset(ans, 0, sizeof(ans));
    for(int i = 1; i <= n; i++) if(!ind[i]) q.push(i);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int i = hd[cur]; i != -1; i = nx[i]) {
            if(!--ind[vr[i]]) {
                q.push(vr[i]); ans[vr[i]] = max(ans[vr[i]], ans[cur] + wi[i]);
            }
        }       
    }
}

int main() {
    int u, v, w;
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    memset(head, -1, sizeof(head));
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    dijkstra(0, x1); dijkstra(1, y1); dijkstra(2, x2); dijkstra(3, y2);
    memset(hd, -1, sizeof(hd));
    for(int i = 1; i <= n; i++)
        for(int j = head[i]; j != -1; j = nex[j])
            if((d[0][i]+wei[j]+d[1][ver[j]] == d[0][y1]) && (d[2][i]+wei[j]+d[3][ver[j]] == d[2][y2] || d[3][i]+wei[j]+d[2][ver[j]] == d[2][y2])){
                if(d[0][i] < d[0][ver[j]])
                    ad(i, ver[j], wei[j]), ind[ver[j]]++;
                else ad(ver[j], i, wei[j]), ind[i]++;
        }
    topo();
    int a = 0;
    for(int i = 1; i <= n; i++) a = max(a, ans[i]);
    printf("%d\n", a);
    return 0;
}

写这篇题解的时候状态不太好,可能语言略有晦涩还请见谅。不懂的可以私信我。
欢迎互相关注(然而在oi界蒟蒻的圈很小)。
最后安利一下蒟蒻的洛谷博客