Codeforces 715B - Complete The Graph

#图论 #最短路 #二分答案
Published on 2016-09-18

题目地址

描述

给定一个 n(2≤n≤1000)n(2\le n\le 1000) 个点 m(1≤m≤10000)m(1\le m\le 10000) 的无向图，边权值 w(1≤w≤109)w(1\le w\le {10}^9) 均为正整数，有一些边尚未被赋值，求一种边权的分配方案（只能分配正整数），使得 s→ts\rightarrow t 的最短路恰好为 L(1≤L≤109)L(1\le L\le {10}^9)。若不存在，输出 NO。

分析

妈蛋这个题考试搞了很久都没做出来，想到了要去找 s→ts\rightarrow t 长度不超过 LL 且有最少未赋值的边的路径，可是搞了一个小时，都没办法想出一个复杂度过得去的方案，我太弱了QAQ。

先判断无解，将所有未赋值的边给 ∞\infty，如果 s→ts\rightarrow t 最短路长度还是 <L< L，无解；将所有未赋值的边给 11，如果 s→ts\rightarrow t 最短路长度 >L> L，无解。否则一定有解，只要找到 s→ts\rightarrow t 长度不超过 LL 且有最少未赋值的边的路径，然后将这条路径改造成长度为 LL，其余未赋值的边一律给 ∞\infty，这就是一个合法方案，显然不存在不经过未赋值的边且长度小于 LL 的路径，然后任何存在未赋值的边的路径（除了我们选定的路径），长度要么是 ∞\infty，要么大于等于 LL（经过且只经过选定的路径上的所有未赋值边），所以一定能构造出可行解，但是我们只用这种方法证明，不用这种方法构造。

正解居然是强行二分！设有 cntcnt 条未赋值的边，随意排列它们，找到最小的 pp，使得将 [0,p−1][0, p - 1] 的边赋值 11，其余的边赋值 ∞\infty，s→ts\rightarrow t 最短路长度 >L> L；且将 [0,p][0, p] 的边赋值 11，其余的边赋值 ∞\infty，s→ts\rightarrow t 最短路长度 ≤L\le L，如果不存在这样一个 pp，则不经过这些未赋值的边，s→ts\rightarrow t 最短路就恰好是 LL，正合题意。

现在的情况是，如果第 pp 条边的权值赋为 11，那么最短路长度 ≤L\le L，赋为 ∞\infty，那么最短路长度 ≥L\ge L，只需要调整 pp 的权值，就可以满足题意（pp 增加一，最短路至多增加 11），所以二分一下 pp 的权值就可以了。

最短路可以使用 Dijkstra 或者 SPFA。如果使用较稳定的 Dijkstra，复杂度：O(mlogn(logm+logL))O(m\log n(\log m + \log L))。

代码

//  Created by Sengxian on 09/18/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 715B 二分 + 最短路
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000 + 3, MAX_M = 10000 + 3;
const int INF = 0x3f3f3f3f;
struct edge {
    int from, to, cost, id;
    edge(int from, int to, int cost, int id): from(from), to(to), cost(cost), id(id) {}
    edge() {}
}edges[MAX_M];
vector<edge> G[MAX_N];

int n, m, L, S, T;
int cnt = 0;

ll SPFA(int p, ll w) {
    static int q[MAX_N];
    static ll dis[MAX_N];
    static bool inq[MAX_N];
    int l = 0, r = 0, cost;
    memset(inq, 0, sizeof inq);
    memset(dis, 0x3f, sizeof dis);
    dis[S] = 0, q[r++] = S;
    while (l != r) {
        int u = q[l++];
        if (l == MAX_N) l = 0;
        inq[u] = false;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            const edge &e = G[u][i];
            if (e.cost == 0) {
                if (e.id == p) cost = w;
                else if (e.id < p) cost = 1;
                else cost = INF;
            } else cost = e.cost;
            if (dis[e.to] > dis[u] + cost) {
                dis[e.to] = dis[u] + cost;
                if (!inq[e.to]) {
                    inq[e.to] = true, q[r++] = e.to;
                    if (r == MAX_N) r = 0;
                }
            }
        }
    }
    return dis[T];
}

void solve() {
    int l = -1, r = cnt;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (SPFA(mid, 1) <= L) r = mid;
        else l = mid;
    }
    int p = r;
    l = 1, r = INF;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (SPFA(p, mid) <= L) l = mid;
        else r = mid;
    }
    puts("YES");
    for (int i = 0; i < m; ++i)
        if (edges[i].cost == 0)
            printf("%d %d %d\n", edges[i].from, edges[i].to, edges[i].id < p ? 1 : (edges[i].id == p ? l : INF));
        else printf("%d %d %d\n", edges[i].from, edges[i].to, edges[i].cost);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt(), L = ReadInt(), S = ReadInt(), T = ReadInt();
    for (int i = 0; i < m; ++i) {
        static int u, v, w;
        u = ReadInt(), v = ReadInt(), w = ReadInt();
        edges[i].from = u, edges[i].to = v, edges[i].cost = w;
        if (w == 0) edges[i].id = cnt++;
        G[u].push_back(edges[i]), G[v].push_back(edges[i]);
        swap(G[v].back().from, G[v].back().to);
    }
    if (SPFA(-1, 0) < L || SPFA(cnt, 0) > L) puts("NO");
    else solve();
    return 0;
}
BZOJ 1111 - [POI2007]四进制的天平Wag