一、题意

输入n（n<=3000）和m（m<=150 000）表示有n个小朋友进行分糖。然后是m对关系，(A B w)表示A的糖果最多比B少w个。求1号和n号最多能差多少个糖果。

二、解析

  • 这是一道差分约束问题，将原题目转化一下就是：给出n个数的m个约束关系，每个关系(A B w)表示B-A<=w，问N-1<=多少? 即N-1的最大值为多少？

  • 问最大值的差分约束问题可以转化为最短路问题解决。

  • 原理：以问最大值为例，问x-y<=多少时，肯定是通过若干B-A<=w的约束条件才可能获得，而B-A<=w这一不等式可以理解为d[B]<=d[A]+w，这正好符合与最短路问题中的松弛操作的条件（d[u]>d[v]+w）相反，也就是松弛操作会使得这一个个约束条件被满足，因此最短路问题的算法就可以得到满足所有约束条件的不等式的一组解。这样就可以得到d[x]与d[y]的差值了。

  • PS：本题的数据量比较大，所以需要用“链式向前星”和scanf输入来加快读图。

三、代码

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 30000 + 5, maxm = 150000+ 5, INF = 1 << 30;
struct node {
    int u, d;
    node(int u, int d) : u(u), d(d) {}
    bool operator < (const node& rhs) const {
        return d > rhs.d;
    }
};
struct edge {
    int to, w, next;
    edge() {}
    edge(int to, int w, int next) : to(to), w(w), next(next) {}
} E[maxm];  // 链式向前星
int n, m, vis[maxn], d[maxn], cnt, head[maxn];  // head[u]指向一条包含了u的所有邻接边的链表

void addEdge(int u, int v, int w) {
    E[cnt] = edge(v, w, head[u]);  // 从链表的头部插入
    head[u] = cnt ++;
}

void Dij(int s) {
    fill(d, d + n + 1, INF); d[s] = 0;
    fill(vis, vis + n + 1, 0);
    priority_queue<node> que;
    que.push(node(s, 0));
    while(!que.empty()) {
        int u = que.top().u; que.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; ~i; i = E[i].next) {
            int v = E[i].to, w = E[i].w;
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                que.push(node(v, d[v]));
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    fill(head, head + n + 1, -1);
    cnt = 1;
    while(m --) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
    }
    Dij(1);
    printf("%d\n", d[n]);
}

四、归纳

  • 差分约束问题 可以转化为最短路或最长路问题，具体规则如下：
    1. 首先看问题，若问题问最大值则可以转化为最短路问题；问最小值则可以转化为最长路问题；
    2. 若为最短路问题，则将所有约束转化为B-A<=w的形式；最长路问题则转化为B-A>=w的形式；
    3. B-A<=w对应于d[B]<=d[A]+w，也就是从点A到B的有向路径权值为w；
    4. 然后就可以用Dijkstra、spfa或Floyd算法来秒杀了。
    5. 若存在负环，则表示无解；若d为INF，表示有无限个解。
  • 链式向前星 就是一种用一个链表来存放每个结点的所有出边的结构，新的边从链表头插入，用于加快读图，模板如下： 
struct edge {
    int to, w, next;
    edge() {}
    edge(int to, int w, int next) : to(to), w(w), next(next) {}
} E[maxm];  // 用链式向前星来存图
int cnt, head[maxn];  // head[u]指向一条包含了u的所有邻接边的链表

void addEdge(int u, int v, int w) {
    E[cnt] = edge(v, w, head[u]);  // 从链表的头部插入
    head[u] = cnt ++;  // 更改头指针
}

int main() {
    ......
    fill(head, head + n + 1, -1);  // 初始化链表头，-1表示链表尾部
    cnt = 1;  // cnt表示当前加入的边序号
    while(m --) {
        ......
        addEdge(u, v, w);
        ......
    }
    ......
    for(int i = head[u]; ~i; i = E[i].next) {  // 遍历u的所有出边的方法
        int v = E[i].to, w = E[i].w;
        ......
    }