题目链接

游游出游

题目描述

给定一个包含 座城市和 条双向道路的图。每条道路连接两个城市，并具有最大承重和长度两个属性。

你需要计算出一辆车从城市 1 前往城市 的最大可能重量，前提是车辆的总行驶距离不能超过一个给定的上限 。车辆的重量必须小于等于其所经过的每一条道路的最大承重。

如果无法在距离限制内从城市 1 到达城市 ，输出 -1。

解题思路

这道题要求在满足一个约束（总长度 ）的前提下，最大化另一个值（车辆重量）。这是一个典型的最大化最小值或最优化问题，非常适合使用二分答案的技巧来解决。

1. 二分答案

我们可以对车辆的重量 进行二分查找。问题的关键在于，如果一个重量为 的车可以通过，那么任何重量小于 的车也一定可以通过（因为它能走的道路集合更大，路径选择更多）。这个单调性是应用二分查找的前提。

二分查找的框架如下：

  • 设置一个查找范围 [left, right]，表示可能的车重。left 可以是 0，right 可以是道路承重的最大值。
  • 每次取中间值 mid，然后调用一个 check(mid) 函数来验证重量为 mid 的车是否可行。
  • 如果 check(mid) 为 true，说明重量 mid 是可行的，我们尝试寻找更大的可行重量，因此记录 mid 为一个可能的答案，并收缩搜索范围至 [mid + 1, right]。
  • 如果 check(mid) 为 false，说明重量 mid 太大了，不可行，必须减小重量，因此收缩搜索范围至 [left, mid - 1]。
  • 二分结束后，记录的最后一个可行重量就是答案。

2. check(W) 函数

check(W) 函数的目的是判断，当车辆重量为 时，是否存在一条从城市 1 到城市 的路径，其总长度不超过 。

这个判断过程可以转化为一个图论问题：

  1. 构建子图：我们只考虑原图中那些最大承重不小于 的道路。所有这些满足条件的道路构成了一个新的子图。
  2. 求最短路：在这个子图上，我们需要找到从城市 1 到城市 的最短路径。
  3. 验证距离：如果这条最短路径的长度小于等于 ，那么重量 就是可行的，check(W) 返回 true。否则，返回 false。

求解这个最短路径问题，我们可以使用 Dijkstra 算法（堆优化版本），因为所有道路的长度都是非负的。

算法整体流程

  1. 对车重 进行二分查找。
  2. 在 check(W) 函数中： a. 遍历所有边，只考虑承重 的边。 b. 以这些边构建的图为基础，运行 Dijkstra 算法计算从 1 到 的最短路。 c. 比较最短路长度与 ，返回 true 或 false。
  3. 根据 check 函数的结果调整二分范围，直到找到答案。
  4. 如果自始至终都找不到一条满足条件的路径（即使重量为0），则最终输出 -1。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Edge {
    int to;
    int length;
    int capacity;
};

struct Node {
    int id;
    ll dist;

    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

int n, m;
ll l;
vector<vector<Edge>> adj;

bool check(int weight) {
    if (weight == 0) return true;
    vector<ll> dist(n + 1, INF);
    dist[1] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({1, 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        int u = current.id;
        ll d = current.dist;

        if (d > dist[u]) {
            continue;
        }

        if (u == n) break; // 优化：找到终点即可

        for (const auto& edge : adj[u]) {
            if (edge.capacity >= weight) {
                int v = edge.to;
                if (dist[u] + edge.length < dist[v]) {
                    dist[v] = dist[u] + edge.length;
                    pq.push({v, dist[v]});
                }
            }
        }
    }
    return dist[n] <= l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> l;
    adj.resize(n + 1);
    int max_cap = 0;
    for (int i = 0; i < m; ++i) {
        int u, v, c, len;
        cin >> u >> v >> c >> len;
        adj[u].push_back({v, len, c});
        adj[v].push_back({u, len, c});
        if (c > max_cap) {
            max_cap = c;
        }
    }

    int left = 0, right = max_cap + 1, ans = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mid == 0) { // 重量0没有意义，直接跳过
            left = mid + 1;
            continue;
        }
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 最后检查一次1是否能到n
    if (ans == -1) {
        vector<ll> dist(n + 1, INF);
        dist[1] = 0;
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        pq.push({1, 0});
        while(!pq.empty()) {
            int u = pq.top().id;
            ll d = pq.top().dist;
            pq.pop();
            if (d > dist[u]) continue;
            if (u == n) break;
            for(const auto& edge : adj[u]) {
                if (dist[u] + edge.length < dist[edge.to]) {
                    dist[edge.to] = dist[u] + edge.length;
                    pq.push({edge.to, dist[edge.to]});
                }
            }
        }
        if(dist[n] > l) cout << -1 << endl;
        else cout << 0 << endl; // 如果能到但最大承重是0
    } else {
        cout << ans << endl;
    }


    return 0;
}

import java.util.*;

public class Main {
    static final long INF = Long.MAX_VALUE;
    static int n, m;
    static long l;
    static List<List<Edge>> adj;

    static class Edge {
        int to, length, capacity;

        Edge(int to, int length, int capacity) {
            this.to = to;
            this.length = length;
            this.capacity = capacity;
        }
    }

    static class Node implements Comparable<Node> {
        int id;
        long dist;

        Node(int id, long dist) {
            this.id = id;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node other) {
            return Long.compare(this.dist, other.dist);
        }
    }

    static boolean check(int weight) {
        if (weight == 0) return true;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.id;
            long d = current.dist;

            if (d > dist[u]) {
                continue;
            }
            if (u == n) break;

            for (Edge edge : adj.get(u)) {
                if (edge.capacity >= weight) {
                    if (dist[u] != INF && dist[u] + edge.length < dist[edge.to]) {
                        dist[edge.to] = dist[u] + edge.length;
                        pq.add(new Node(edge.to, dist[edge.to]));
                    }
                }
            }
        }
        return dist[n] <= l;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        l = sc.nextLong();

        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        
        int maxCap = 0;
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int c = sc.nextInt();
            int len = sc.nextInt();
            adj.get(u).add(new Edge(v, len, c));
            adj.get(v).add(new Edge(u, len, c));
            maxCap = Math.max(maxCap, c);
        }

        int left = 0, right = maxCap + 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
             if (mid == 0) {
                left = mid + 1;
                continue;
            }
            if (check(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        if (ans == -1) {
            // Check if path exists at all within limit L
             long[] dist = new long[n + 1];
            Arrays.fill(dist, INF);
            dist[1] = 0;
            PriorityQueue<Node> pq = new PriorityQueue<>();
            pq.add(new Node(1, 0));
            while(!pq.isEmpty()){
                Node curr = pq.poll();
                int u = curr.id;
                long d = curr.dist;
                if(d > dist[u]) continue;
                if(u == n) break;
                for(Edge edge : adj.get(u)){
                    if(dist[u] != INF && dist[u] + edge.length < dist[edge.to]){
                        dist[edge.to] = dist[u] + edge.length;
                        pq.add(new Node(edge.to, dist[edge.to]));
                    }
                }
            }
            if(dist[n] > l) System.out.println(-1);
            else System.out.println(0); // path exists, but max weight is 0
        } else {
            System.out.println(ans);
        }
    }
}

import heapq

def check(weight, n, adj, l_limit):
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[1] = 0
    pq = [(0, 1)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue
        
        if u == n:
            break

        for v, length, capacity in adj.get(u, []):
            if capacity >= weight:
                if dist[u] + length < dist[v]:
                    dist[v] = dist[u] + length
                    heapq.heappush(pq, (dist[v], v))
    
    return dist[n] <= l_limit

def main():
    n, m, l_limit = map(int, input().split())
    adj = {}
    max_cap = 0
    for _ in range(m):
        u, v, c, length = map(int, input().split())
        if u not in adj: adj[u] = []
        if v not in adj: adj[v] = []
        adj[u].append((v, length, c))
        adj[v].append((u, length, c))
        max_cap = max(max_cap, c)

    left, right = 0, max_cap + 1
    ans = -1

    while left <= right:
        mid = left + (right - left) // 2
        if mid == 0:
            left = mid + 1
            continue
        if check(mid, n, adj, l_limit):
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
            
    if ans == -1:
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[1] = 0
        pq = [(0, 1)]
        path_found = False
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]: continue
            if u == n:
                path_found = True
                break
            for v, length, _ in adj.get(u, []):
                if dist[u] + length < dist[v]:
                    dist[v] = dist[u] + length
                    heapq.heappush(pq, (dist[v], v))
        
        if not path_found or dist[n] > l_limit:
            print(-1)
        else:
            print(0) # path exists, but max capacity is 0
    else:
        print(ans)


if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：二分答案 + Dijkstra 算法
  • 时间复杂度：，其中 是城市数量， 是道路数量， 是最大承重。二分查找需要 次迭代，每次迭代内部运行一次 Dijkstra 算法，其复杂度为 或简写为 。
  • 空间复杂度：，用于存储图的邻接表以及 Dijkstra 算法所需的距离数组和优先队列。