「CF716D」Complete The Graph「最短路」

淡淡的烟草味﹌ 2023-08-17 17:31 92阅读 0赞

**题意**

给定一个\\(n\\)个点\\(m\\)条边的无向图，有一些边权暂时为\\(0\\)，你需要分配一个\\(\[1, 10^\{18\}\]\\)的数。最终使得\\(s\\)到\\(t\\)最短路为\\(L\\)，输出一个可行的分配方案，或告知无解。

\\(n \\leq 10^3\\)，\\(m \\leq 10^4\\)，\\(L \\leq 10^9\\)

**题解**

首先拿到这个图，我们把\\(0\\)边换成INF，求\\(s\\)到\\(t\\)的最短路\\(d\\)，如果此时\\(d<L\\)，则无解

再把\\(0\\)边换成\\(1\\)，求最短路\\(d\\)，如果\\(d>L\\)，也无解

上面两行是显然的，我们现在证明除了以上情况，一定有解。

考虑把\\(0\\)边换\\(1\\)。然后所有\\(s\\)到\\(t\\)的路径拿出来按权值从小到大排序，这时第一条路径\\(d\\leq L\\)。若\\(d=L\\)则结束，否则这条路径一定含有可变边。把可变边+1（这可能导致一些路径权值+1）。重复上述过程就能得到解。

那么第一种做法：我们用和证明相似的做法来求解。把\\(0\\)边换\\(1\\)后，我们找**一条**任意最短路径。我们直接把不在这路径上的可变边变成INF并固定，不需要考虑。这样一定是对的。不经过可变边的路径>L，经过非标记可变边的路径=inf，只剩下经过标记边的路径要考虑。

那么我们每次跑一下最短路，找到最短路上一个**标记边**，然后加上\\(L-d\\)并固定。这样进行若干次一定能出解。容易看出最多n次（标记边数量是\\(O(n)\\)的），这个复杂度\\(O(nm\\log n)\\)

CF上还给了一个优秀解法，具体看：[http://codeforces.com/blog/entry/47169][http_codeforces.com_blog_entry_47169]

另外在民间发现二分解法，非常易懂，应该是理解起来最简单的做法：[https://www.cnblogs.com/zhouzhendong/p/CF715B.html][https_www.cnblogs.com_zhouzhendong_p_CF715B.html]

代码：（解法1）

#include <algorithm>
    #include <vector>
    #include <cstdio>
    #include <queue>
    using namespace std;
     
    typedef long long ll;
     
    const int N = 1e3 + 10;
    const int M = 2e4 + 10;
    const ll INF = 1e16;
     
    struct Edge {
        int v, nxt; ll w;
    } e[M];
    int hd[N], p, n, m, L, s, t, pre[N];
    bool use[M], mark[M];
    vector<int> mdf, mmdf;
    void clr() { fill(hd, hd + n, -1); p = 0; }
    void add(int u, int v, ll w) {
        e[p] = (Edge) {v, hd[u], w}; hd[u] = p ++;
    }
    struct node {
        int u; ll d;
        bool operator < (const node &b) const { return d > b.d; }
    };
    ll d[N];
    ll dijkstra() {
        fill(d, d + n, INF * 10ll);
        priority_queue<node> pq; pq.push((node) {s, d[s] = 0});
        while(pq.size()) {
            node k = pq.top(); pq.pop();
            int u = k.u; ll du = k.d;
            if(d[u] < du) continue ;
            for(int i = hd[u]; ~ i; i = e[i].nxt) {
                Edge &g = e[i];
                if(d[g.v] > d[u] + g.w) {
                    pre[g.v] = i;
                    pq.push((node) {g.v, d[g.v] = d[u] + g.w});
                }
            }
        }
        return d[t];
    }
    int main() {
        scanf("%d%d%d%d%d", &n, &m, &L, &s, &t); clr();
        for(int i = 0; i < m; i ++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            if(w == 0) mdf.push_back(p), use[p] = 1;
            add(u, v, w); add(v, u, w);
        }
        for(int i = 0; i < mdf.size(); i ++) {
            int j = mdf[i]; e[j].w = e[j ^ 1].w = INF;
        }
        if(dijkstra() < L) return puts("NO"), 0;
        for(int i = 0; i < mdf.size(); i ++) {
            int j = mdf[i]; e[j].w = e[j ^ 1].w = 1;
        }
        if(dijkstra() > L) return puts("NO"), 0;
        puts("YES");
        for(int u = t; u != s; u = e[pre[u] ^ 1].v) {
            int j = pre[u], v = e[j ^ 1].v; j >>= 1; j <<= 1;
            if(use[j] && d[u] == d[v] + e[j].w || d[v] == d[u] + e[j].w) {
                mark[j] = 1; mmdf.push_back(j);
            }
        }
        for(int i = 0; i < mdf.size(); i ++) {
            int j = mdf[i];
            if(!mark[j]) e[j].w = e[j ^ 1].w = INF;
        }
        while(1) {
            ll di = dijkstra();
            if(di == L) break ;
            for(int i = 0; i < mmdf.size(); i ++) {
                int j = mmdf[i];
                if(mark[j]) {
                    mark[j] = 0; e[j].w += L - di; e[j ^ 1].w += L - di; break ;
                }
            }
        }
        for(int i = 0; i < p; i += 2)
            printf("%d %d %I64d\n", e[i ^ 1].v, e[i].v, e[i].w);
        return 0;
    }

转载于:https://www.cnblogs.com/hongzy/p/11514912.html

[http_codeforces.com_blog_entry_47169]: http://codeforces.com/blog/entry/47169
[https_www.cnblogs.com_zhouzhendong_p_CF715B.html]: https://www.cnblogs.com/zhouzhendong/p/CF715B.html