BZOJ1880或洛谷2149 [SDOI2009]Elaxia的路线

BZOJ原题链接

洛谷原题链接

显然最长公共路径是最短路上的一条链。
我们可以把最短路经过的边看成有向边，那么组成的图就是一张\(DAG\)，这样题目要求的即是两张\(DAG\)重合部分中的最长链。
重合部分中的最长链可能是同向，可能是反向的，但不可能由反向边和同向边组成，否则就不是\(DAG\)了。
所以我们分别只保留重合部分的同向边、反向边，跑两次拓扑排序求最长链，在两者中取\(\max\)即可。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1510;
const int M = 2.5e6;
struct dd {
    int x, D;
    bool operator < (const dd &b) const { return D > b.D; }
};
int fi[N], di[M], ne[M], da[M], cfi[N], cdi[M], cne[M], cda[M], dis_1[N], dis_2[N], dis_3[N], dis_4[N], dis[N], ru[N], tq[N], l, x_1, y_1, x_2, y_2, lc, ma, n;
bool v[N];
priority_queue<dd>q;
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline void add(int x, int y, int z)
{
    di[++l] = y;
    da[l] = z;
    ne[l] = fi[x];
    fi[x] = l;
}
inline void add_c(int x, int y, int z)
{
    cdi[++lc] = y;
    cda[lc] = z;
    cne[lc] = cfi[x];
    cfi[x] = lc;
    ru[y]++;
}
inline int maxn(int x, int y){ return x > y ? x : y; }
void dij(int st, int dis[])
{
    memset(v, 0, sizeof(v));
    int i, x, y;
    dis[st] = 0;
    q.push((dd){st, 0});
    while (!q.empty())
    {
        x = q.top().x;
        q.pop();
        if (v[x])
            continue;
        v[x] = 1;
        for (i = fi[x]; i; i = ne[i])
            if (dis[y = di[i]] >= dis[x] + da[i])
                q.push((dd){y, dis[y] = dis[x] + da[i]});
    }
}
void topsort()
{
    int i, x, y, head = 0, tail = 0;
    for (i = 1; i <= n; i++)
        if (!ru[i])
            tq[++tail] = i;
    while (head ^ tail)
    {
        x = tq[++head];
        ma = maxn(ma, dis[x]);
        for (i = cfi[x]; i; i = cne[i])
        {
            y = cdi[i];
            dis[y] = maxn(dis[y], dis[x] + cda[i]);
            if (!(--ru[y]))
                tq[++tail] = y;
        }
    }
}
int main()
{
    int i, j, m, x, y, z;
    n = re();
    m = re();
    x_1 = re();
    y_1 = re();
    x_2 = re();
    y_2 = re();
    for (i = 1; i <= m; i++)
    {
        x = re();
        y = re();
        z = re();
        add(x, y, z);
        add(y, x, z);
    }
    memset(dis_1, 60, sizeof(dis_1));
    memset(dis_2, 60, sizeof(dis_2));
    memset(dis_3, 60, sizeof(dis_3));
    memset(dis_4, 60, sizeof(dis_4));
    dij(x_1, dis_1);
    dij(y_1, dis_2);
    dij(x_2, dis_3);
    dij(y_2, dis_4);
    for (i = 1; i <= n; i++)
        for (j = fi[i]; j; j = ne[j])
            if (!((dis_1[i] + da[j] + dis_2[di[j]]) ^ dis_1[y_1]) && !((dis_3[i] + da[j] + dis_4[di[j]]) ^ dis_3[y_2]))
                add_c(i, di[j], da[j]);
    topsort();
    memset(cfi, 0, sizeof(fi));
    memset(dis, 0, sizeof(dis));
    lc = 0;
    for (i = 1; i <= n; i++)
        for (j = fi[i]; j; j = ne[j])
            if (!((dis_1[i] + da[j] + dis_2[di[j]]) ^ dis_1[y_1]) && !((dis_4[i] + da[j] + dis_3[di[j]]) ^ dis_3[y_2]))
                add_c(i, di[j], da[j]);
    topsort();
    printf("%d", ma);
    return 0;
}

BZOJ1880或洛谷2149 [SDOI2009]Elaxia的路线

原文：https://www.cnblogs.com/Iowa-Battleship/p/9907688.html