排队布局

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 2791 字
差分约束最短路判负环与最值
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1512
// 题意：N 头牛按编号排成一列，ML 条「距离至多 D」与 MD 条「距离至少 D」的约束，无解输出 -1，1 与 N 距离可任意大输出 -2，否则输出最大距离。
// 思路：差分约束求最短路。「至多 D」建 A -> B 权 D，「至少 D」建 B -> A 权 -D，再加牛的先后顺序边 i + 1 -> i 权 0。
// 1. 先用虚拟源点判全图负环，再从 1 号牛跑一次 SPFA 求到 N 的最短路，即 1 与 N 的最大可能距离。
// 2. 从 1 号牛不可达 N 说明两者距离不受限，输出 -2。
// 复杂度：O(k * (n + m)) 时间 / O(n + m) 空间
// 易错点：负环判定必须覆盖全图，只从 1 号出发会漏掉由其它约束构成的矛盾。
// 易错点：牛的编号顺序意味着坐标单调不降，漏掉 i + 1 -> i 这条 0 边会得出偏大的距离。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to;
    int w;
};
vector<Edge> g[MAXN];
int dis[MAXN];
int cnt[MAXN];
bool inq[MAXN];
int main(){
    int n, ml, md;
    if(!(cin >> n >> ml >> md)) return 0;
    for(int i = 0; i < ml; i++){
        int a, b, d;
        cin >> a >> b >> d;
        Edge e;
        e.to = b;
        e.w = d;
        g[a].push_back(e);
    }
    for(int i = 0; i < md; i++){
        int a, b, d;
        cin >> a >> b >> d;
        Edge e;
        e.to = a;
        e.w = -d;
        g[b].push_back(e);
    }
    for(int i = 1; i < n; i++){
        Edge e;
        e.to = i;
        e.w = 0;
        g[i + 1].push_back(e);
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        Edge e;
        e.to = i;
        e.w = 0;
        g[0].push_back(e);
    }
    for(int i = 0; i <= n; i++){
        dis[i] = 0;
        cnt[i] = 0;
        inq[i] = true;
        q.push(i);
    }
    bool neg = false;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            int w = g[u][i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                cnt[v]++;
                if(cnt[v] > n + 1){
                    neg = true;
                    break;
                }
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
        if(neg) break;
    }
    if(neg){
        cout << -1 << "\n";
        return 0;
    }
    for(int i = 1; i <= n; i++){
        dis[i] = INF;
        cnt[i] = 0;
        inq[i] = false;
    }
    dis[1] = 0;
    inq[1] = true;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            int w = g[u][i].w;
            if(v == 0) continue;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(dis[n] >= INF / 2) cout << -2 << "\n";
    else cout << dis[n] << "\n";
    return 0;
}
排队布局

正文

一本通·提高篇的其它内容
