题解 P5960 【【模板】差分约束算法】

一只书虫仔 · 2020-07-14 10:10:40 · 题解

Description

给定 n 个数 t_i，然后给定 m 个用 i,j,b 描述的不等式关系

Solution

差分约束模板，左边的这个 t_i-t_j 就是差分。

我们首先把这个不等式化简一下，成 t_i\le t_j+b。

假设 t_j 已知，我们可以推出 t_i 的最大值只可能是 t_j+b，最小不限。

那我们再次假设如果 t_i 跟 t_{j'}，t_{j''}，t_{j'''} 都有关，我们就可以得到三个不等式，即一个不等式组

那么 t_i 满足所有不等式下的最大值应该是 \min\{t_{j'}+b,t_{j''}+b,t_{j'''}+b\}。

因为要满足所有不等式，所以必须要取最小值来满足所有的不等式。

注意，我们上面提到的 j 都可以模拟成 i 的 前继。

那么我们可以再次简化模型。

假设有多个 t_j 是 t_i 的前继，那么我们就可以得到一个递推式。

那么我们看一下 SPFA 的递推式。

好了，破案了。

那么我们只需要找一个超级原点 \rm super，然后使得他连到 i 的长度是 t_i 即可。

最后我们求一个最短路即可，输出每个 dist_i-\min\{dist_i\}。

最后无解的情况只需要判断一下负环即可。

Code

#include <bits/stdc++.h>

using namespace std;

struct node {
    int val, next, len;
} e[100086];

int n, m;
int cnt;
int head[100086];
int dist[100086];
int sum[100086];
int vis[100086];
const int inf = 0x3f3f3f3f;

void AddEdge (int u, int v, int w) {
    e[++cnt].val = v;
    e[cnt].next = head[u];
    e[cnt].len = w;
    head[u] = cnt;
}

bool SPFA () {
    queue <int> q;
    int s = n + 1;
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[s] = 0;
    sum[s] = 1;
    vis[s]++;
    q.push(s);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        sum[cur] = 0;
        for (int p = head[cur]; p > 0; p = e[p].next)
            if (dist[e[p].val] > dist[cur] + e[p].len) {
                dist[e[p].val] = dist[cur] + e[p].len;
                vis[e[p].val]++;
                if (vis[e[p].val] >= n + 1)
                    return true;
                if (!sum[e[p].val]) {
                    q.push(e[p].val);
                    sum[e[p].val] = 1;
                }
            }
    }
    return false;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(v, u, w);
    }
    for (int i = 1; i <= n; i++) 
        AddEdge(n + 1, i, 0);
    if (SPFA()) {
        printf("NO");
        return 0;
    }
    int Min = 1e9;
    for (int i = 1; i <= n; i++)
        Min = min(dist[i], Min);
    for (int i = 1; i <= n; i++)
        printf("%d ", dist[i] - Min);
    return 0;
}

2020.7.14
By Shuchong