Poj 3662: Telephone Lines

poj3662.md

Poj 3662: Telephone Lines

題目

分析

K lengths of cable for free 這是指「K 條 cable 免費」，而不是「長度大於 K 的免費」…

觀察可得，當我們確定 longest remaining cable = L 時， 我們可以用最短路徑演算法得到此時從 0 走到 N-1 最少需要幾條 > L 的邊（d[N-1]）， 並且 L 與 d[N-1] 成反相關。更詳細的解釋參 這 。

於是我們對 L 二分搜

正負相關性判定

bool C(L) = 可否使路徑上長於 L 的邊少於等於 K 條

C(m) 表：

0 0 0 1 1 1 1

目標是尋找第一個 1

上下界判定

根據題意，解的範圍為 [0, longest_edge]，即 Telephone 1 與 Telephone N 相鄰時，與 K = 0 時。因為使用 (lb, ub]，所以

int lb = -1;
int ub = max_cost;

答案是 ub

※ 要輸出 -1 的情況僅發生在 Telephone 1 與 Telephone N 不連通時，可用 dfs 先預判掉

判斷函式實作

改寫 Dijkstra's algorithm。

d[x] 變成代表從 0 走到 x 最少需要幾條 > L 的邊

最後判斷 d[N-1] 是否 <= K

AC Code

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, cost;
};

int N, P, K;
vector<Edge> g[1000];

bool dfs() {
    bool added[1000]; memset(added, false, sizeof(added));
    stack<int> st;
    st.push(0);
    added[0] = true;
    while (!st.empty()) {
        int v = st.top(); st.pop();
        if (v == N-1) return true;
        for (size_t i = 0; i < g[v].size(); i++) {
            int u = g[v][i].to;
            if (!added[u]) {
                st.push(u);
                added[u] = true;
            }
        }
    }
    return false;
}

// 可否使路徑上長於 L 的邊少於等於 K 條
bool C(int L) {
    // dijkstra, d[x] = 從 0 走到 x 最少需要幾條 > L 的邊
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    int d[1000]; memset(d, INF, sizeof(d));

    pq.push(pii(0, 0));
    d[0] = 0;

    while (!pq.empty()) {
        pii top = pq.top(); pq.pop();
        int v = top.second;

        if (d[v] < top.first)
            continue;

        for (size_t i = 0; i < g[v].size(); i++) {
            const Edge& e = g[v][i];
            int new_d = d[v] + ((e.cost > L) ? 1 : 0);
            if (d[e.to] > new_d) {
                d[e.to] = new_d;
                pq.push(pii(new_d, e.to));
            }
        }
    }

    return d[N-1] <= K;
}

int solve(int max_cost) {
    if (dfs() == false)
        return -1;

    // 解的範圍：[0, max_cost]
    // (lb, ub]
    int lb = -1;
    int ub = max_cost;

    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) ub = mid;
        else lb = mid;
    }

    return ub;
}

int main() {
    scanf("%d %d %d", &N, &P, &K);

    int max_cost = -1;
    for (int i = 0; i < P; i++) {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);
        a--; b--;
        g[a].push_back(Edge{b, l});
        g[b].push_back(Edge{a, l});
        if (l > max_cost)
            max_cost = l;
    }

    printf("%d\n", solve(max_cost));

    return 0;
}