M03424: Candies

dijkstra, http://cs101.openjudge.cn/practice/03424/

During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often compared the numbers of candies they got with others. A kid A could had the idea that though it might be the case that another kid B was better than him in some aspect and therefore had a reason for deserving more candies than he did, he should never get a certain number of candies fewer than B did no matter how many candies he actually got, otherwise he would feel dissatisfied and go to the head-teacher to complain about flymouse’s biased distribution.

snoopy shared class with flymouse at that time. flymouse always compared the number of his candies with that of snoopy’s. He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied. Now he had just got another bag of candies from the head-teacher, what was the largest difference he could make out of it?

输入

The input contains a single test cases. The test cases starts with a line with two integers N and Mnot exceeding 30 000 and 150 000 respectively. N is the number of kids in the class and the kids were numbered 1 through N. snoopy and flymouse were always numbered 1 and N. Then follow Mlines each holding three integers A, B and c in order, meaning that kid A believed that kid Bshould never get over c candies more than he did.

输出

Output one line with only the largest difference desired. The difference is guaranteed to be finite.

样例输入

2 2
1 2 5
2 1 4

样例输出

提示

32-bit signed integer type is capable of doing all arithmetic.

来源

POJ Monthly--2006.12.31, Sempr

你的理解是正确的：

将每个不等式
$x_{B} - x_{A} \leq c$
看作有向边 A→B，权重为 c。
对任意一条从 1 到 N 的路径 $1 = v_{0} \to v_{1} \to \dots \to v_{k} = N$ ，都有
$x_{N} - x_{1} \leq \sum_{i = 0}^{k - 1} c_{v_{i} v_{i + 1}}$ .
要使 $x_{N} - x_{1}$ 尽可能大，就要取所有路径权重之中的最小值──也就是在这张有向图上求从 1 到 N 的最短路。

因为所有 $c \geq 0$ ，可以直接用 Dijkstra 算法。下面给出一个 $O (M l o g N)$ 的实现：

python

import sys
import threading
import heapq

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        A, B, c = map(int, input().split())
        graph[A].append((B, c))
    INF = 10**30
    dist = [INF] * (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, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    # 输出从 1 到 N 的最短路距离，即为最大可实现的 x_N - x_1
    print(dist[N])

if __name__ == "__main__":
    threading.Thread(target=main).start()

说明：

我们把每条约束 xB≤xA+c 转化为图中的一条边 A→B，权重为 c。
用 Dijkstra 从节点 1 出发，算出到节点 N 的最短距离 dist[N]。
这个最短距离恰好就是在所有满足约束的分配方案中，xN−x1 能达到的最大值。

参考：https://blog.csdn.net/Maxwei_wzj/article/details/60464314

题目大意：幼儿园一个班里有N个小朋友（标号为1~N），一个小朋友flymouse（为N号）被校长指定去发糖，有M个条件，每个条件三个参数A,B,c，表示小朋友A不希望小朋友B有比他多超过c个的糖，班里还有另一个小朋友snoopy（为1号），flymouse希望自己得到的糖果比snoopy的尽量多，求最大的差值。

做法：这里引入一个叫差分约束系统的东西，大概就是给定一系列这样形式的不等式：xi-xj<=bk，然后求某两个xa和xb的差的最大值，即max(xa-xb)。正确的方法是，如果存在一个xi-xj<=bk这样的不等式，就从j引一条指向i的边权为bk的有向边，这样就可以构成一个有向图，然后求max(xa-xb)就是求从b到a的最短路径。为什么呢？因为我们看任意一条简单路径：b,s1,s2,...,sn,a，其中相邻两点间边权依次为b0,b1,...,bn，所以xs1-xb<=b0,xs2-xs1<=b1,...,xa-xsn<=bn,所以xa-xb=(xa-xsn)+...+(xs2-xs1)+(xs1-xb)<=b0+b1+...+bn，所以我们可以得到xa-xb必定不超过任意从b到a的简单路径上边权的和，也就是说任何一条路径都是一个上界，所以要求最大值也就是求最小的上界，也就是求最短路了。

差分约束系统是一个整体系统，我们需要找到所有约束都满足的前提下，目标变量差值的最大值。

而这一题模型比较简单，构图很容易，对于每个条件直接连A->B，边权为c即可，然后求从1到N的最短路。

标准的Dijkstra就可以。

python

import heapq

def dijkstra(N, G, start):
    INF = float('inf')
    dist = [INF] * (N + 1)  # 存储源点到各个节点的最短距离
    dist[start] = 0  # 源点到自身的距离为0
    pq = [(0, start)]  # 使用优先队列，存储节点的最短距离
    while pq:
        d, node = heapq.heappop(pq)  # 弹出当前最短距离的节点
        if d > dist[node]:  # 如果该节点已经被更新过了，则跳过
            continue
        for neighbor, weight in G[node]:  # 遍历当前节点的所有邻居节点
            new_dist = dist[node] + weight  # 计算经当前节点到达邻居节点的距离
            if new_dist < dist[neighbor]:  # 如果新距离小于已知最短距离，则更新最短距离
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))  # 将邻居节点加入优先队列
    return dist



N, M = map(int, input().split())
G = [[] for _ in range(N + 1)]  # 图的邻接表表示
for _ in range(M):
    s, e, w = map(int, input().split())
    G[s].append((e, w))


start_node = 1  # 源点
shortest_distances = dijkstra(N, G, start_node)  # 计算源点到各个节点的最短距离
print(shortest_distances[-1])  # 输出结果

python

import heapq

class Edge:
    def __init__(self, k=0, w=0):
        self.k, self.w = k, w  # 有向边的终点和边权值，或当前k到源点的距离

    def __lt__(self, other):
        return self.w < other.w


def dijkstra(N, G):
    bUsed = [False] * (N + 1)  # bUsed[i]为True表示源到i的最短路已经求出
    INF = float('inf')
    pq = []
    heapq.heappush(pq, Edge(1, 0))  # 源点是1号点,1号点到自己的距离是0
    while pq:
        p = heapq.heappop(pq)
        if bUsed[p.k]:  # 已经求出了最短路
            continue
        bUsed[p.k] = True
        if p.k == N:  # 因只要求1-N的最短路，所以要break
            break
        for edge in G[p.k]:
            if not bUsed[edge.k]:
                heapq.heappush(pq, Edge(edge.k, p.w + edge.w))
    return p.w


N, M = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
    s, e, w = map(int, input().split())
    G[s].append(Edge(e, w))

shortest_distance = dijkstra(N, G)
print(shortest_distance)

M03424: Candies ​

M03424: Candies