洛谷P2149 [SDOI2009]Elaxia的路线

19 August 2019 | duanyll | Tags: OI 题解 图论

@liao_rl今天下午神秘兮兮的宣称洛谷上有道题4个标4种做法都被hack了, 于是我就看见了这个题. 好像也没有什么难的吧, 几乎一遍就A了原题和hack数据(交的前两遍数组没开够)

做法比较显然吧, 4次最短路得到$x_1\rightarrow y_1, x_2 \rightarrow y_2$的最短路径上的所有边, 然后分别按照相同和相反方向建两个DAG跑最长路就完了, 没什么坑啊.

也可能是我太弱了, 过于自信, 欢迎hack.

代码

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 1510;

#include <cctype>
#include <cstdio>

template <typename T = int>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

/*
    把S1~T1, S2~T2的最短路网络求出来, 然后求出两个网络的公共边并建图,
   得到一个DAG, 在上面跑最长路.
*/

class lfs {
   public:
    lfs(int N) {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = N;
    }
    void adde(int from, int to, int w) {
        Edge now;
        now.to = to;
        now.w = w;
        now.next = head[from];
        now.mark1 = now.mark2 = false;
        e.push_back(now);
        head[from] = ecnt++;
    }
    void addde(int a, int b, int w) {
        adde(a, b, w);
        adde(b, a, w);
    }

   protected:
    struct Edge {
        int to, next, w;
        bool mark1, mark2;
    };
    vector<Edge> e;
    int head[MAXN];
    int ecnt;
    int n;
};

class long_path : public lfs {
   public:
    long_path(int n) : lfs(n) {}
    int solve() {
        memset(dp, -1, sizeof dp);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dp[i] == -1) {
                dfs(i, -1);
            }
        }
        for (int i = 1; i <= n; i++) {
            ans = max(ans, dp[i]);
        }
        return ans;
    }

   protected:
    int dp[MAXN];

    void dfs(int u, int fa) {
        dp[u] = 0;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (v == fa) continue;
            if (dp[v] == -1) {
                dfs(v, u);
            }
            dp[u] = max(dp[u], dp[v] + e[i].w);
        }
    }
};

class spfa : public lfs {
   public:
    spfa(int n) : lfs(n) { memset(dis, INF, sizeof dis); }
    int dis[MAXN];
    void solve(int s) {
        memset(ins, false, sizeof ins);
        memset(dis, INF, sizeof dis);
        queue<int> q;
        q.push(s);
        ins[s] = true;
        dis[s] = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            ins[now] = false;
            for (int i = head[now]; i != -1; i = e[i].next) {
                int w = e[i].w;
                int v = e[i].to;
                if (dis[now] + w < dis[v]) {
                    dis[v] = dis[now] + w;
                    if (!ins[v]) {
                        q.push(v);
                        ins[v] = true;
                    }
                }
            }
        }
    }

    void mark1(int s, int t) {
        solve(s);
        int* dis1 = new int[MAXN];
        memcpy(dis1, dis, sizeof dis);
        solve(t);
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to;
                if (dis1[u] + e[i].w + dis[v] == dis1[t]) {
                    // clog << "Mark1 " << u << ' ' << v << endl;
                    e[i].mark1 = true;
                }
            }
        }
        delete[] dis1;
    }

    void mark2(int s, int t) {
        solve(s);
        int* dis1 = new int[MAXN];
        memcpy(dis1, dis, sizeof dis);
        solve(t);
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to;
                if (dis1[u] + e[i].w + dis[v] == dis1[t]) {
                    // clog << "Mark2 " << u << ' ' << v << endl;
                    e[i].mark2 = true;
                }
            }
        }
        delete[] dis1;
    }

    void create_dag(lfs* dag1, lfs* dag2) {
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to;
                if (e[i].mark1 && e[i].mark2) {
                    dag1->adde(u, v, e[i].w);
                }
                if (e[i].mark1 && e[i^1].mark2) {
                    dag2->adde(u, v, e[i].w);
                }
            }
        }
    }

   private:
    bool ins[MAXN];
};

int main() {
    int n = read();
    int m = read();
    int s1 = read();
    int t1 = read();
    int s2 = read();
    int t2 = read();

    spfa* all = new spfa(n);
    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        int w = read();
        all->addde(u, v, w);
    }
    all->mark1(s1, t1);
    all->mark2(s2, t2);
    long_path* dag1 = new long_path(n);
    long_path* dag2 = new long_path(n);
    all->create_dag(dag1, dag2);
    cout << max(dag1->solve(), dag2->solve()) << endl;
    return 0;
}