AcWing 1170 排队布局

一、理论知识

见本节的整体部分。

二、超级源点法(常规办法)

#include 
using namespace std;
const int N = 1010, M = 21010;
const int INF = 0x3f3f3f3f;
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int n;      // n头奶牛
int cnt[N]; //入队次数，用于判负环
int d[N];   // spfa用到的最短距离
bool st[N]; // spfa用到的是否在队列中
bool spfa(int s) {
    memset(cnt, 0, sizeof cnt); //多次调用，需要初始化
    memset(st, false, sizeof st);
    memset(d, 0x3f, sizeof d);

    queue q;
    d[s] = 0; //出发点的距离是0
    st[s] = true;
    q.push(s);

    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[u] + w[i]) { //最短路
                d[j] = d[u] + w[i];
                //虚拟源点到j号点的最短路径的边数量
                cnt[j] = cnt[u] + 1;
                // n条边，走过了n+1个节点，所以有环
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}
int main() {
    // n头奶牛
    // ml条关于两头奶牛间有好感的描述,md条关于两头奶牛间存有反感的描述
    int ml, md, a, b, c;
    cin >> n >> ml >> md;
    //初始化邻接表
    memset(h, -1, sizeof h);

    //求最大值，最短路建图，即 <= 形式
    // 奶牛间的坐标满足  a(i) <= a(i+1) 即后面的奶牛坐标需要大于等于前面的奶牛
    // 转化为标准形式就是 a(i) <= a(i+1) + 0
    for (int i = 1; i < n; i++) add(i + 1, i, 0);

    //读入其它不等式
    while (ml--) {
        //两者之间的距离不超过一个给定的数l
        cin >> a >> b >> c;    // a(i) - a(j) <= l 变形: a(i) <= a(j)+l
        if (a > b) swap(a, b); //本题没有说a一定小于b,所以需要swap一下，
        //但实际上数据没有反着给的测试用例
        add(a, b, c);
    }
    while (md--) {
        //两者间的距离不小于一个给定的数l
        cin >> a >> b >> c; // a(i) -a(j)>=l 变形: a(j) <= a(i)-l
        if (a > b) swap(a, b);
        add(b, a, -c);
    }
    //建图完毕

    //因为不能保证所有点都是连通的，所以添加超级源点
    // a(0) - a(i) <=0  变形：a(0) <= a(i) + 0
    for (int i = 0; i < n; i++) add(0, i, 0);
    if (spfa(0))
        puts("-1");
    else {
        spfa(1); // 1号奶牛和N号奶牛间
        if (d[n] == INF)
            puts("-2"); //从1出发不能到达n，输出-2
        else
            printf("%d\n", d[n]); //最短路就是最大距离
    }
    return 0;
}

三、从n出发法(本题特性)

#include 
using namespace std;
const int N = 1010, M = 21010;
const int INF = 0x3f3f3f3f;
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int n;      // n头奶牛
int cnt[N]; //入队次数，用于判负环
int d[N];   // spfa用到的最短距离
bool st[N]; // spfa用到的是否在队列中
bool spfa(int s) {
    memset(cnt, 0, sizeof cnt); //多次调用，需要初始化
    memset(st, false, sizeof st);
    memset(d, 0x3f, sizeof d);

    queue q;
    d[s] = 0; //出发点的距离是0
    st[s] = true;
    q.push(s);

    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[u] + w[i]) { //最短路
                d[j] = d[u] + w[i];
                //虚拟源点到j号点的最短路径的边数量
                cnt[j] = cnt[u] + 1;
                // n条边，走过了n+1个节点，所以有环
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}
int main() {
    // n头奶牛
    // ml条关于两头奶牛间有好感的描述,md条关于两头奶牛间存有反感的描述
    int ml, md, a, b, c;
    cin >> n >> ml >> md;
    //初始化邻接表
    memset(h, -1, sizeof h);

    //奶牛编号从1到n, a(i) <= a(i+1) + 0
    for (int i = 1; i < n; i++) add(i + 1, i, 0); //最短路建图
    while (ml--) {
        //两者之间的距离不超过一个给定的数l
        cin >> a >> b >> c; // a(i) <= a(j) + l
        //本题没有说a一定小于b,所以需要swap一下，
        //但实际上数据没有反着给的测试用例
        if (a > b) swap(a, b);
        add(a, b, c);
    }
    while (md--) {
        cin >> a >> b >> c;
        if (a > b) swap(a, b);
        //两者间的距离不小于一个给定的数l
        add(b, a, -c); // a(i) -a(j)>=l 变形 a(j) <= a(i)-l
    }
    //至此图建好了~

    //本题是因为存在 a(i)<=a(i+1)+0这个关系的，所以就意味着
    // i+1向i有边，即终点n存在向n-1的边,n-1存在向n-2的边，...
    // 所以n可以到达所有的点(1~n),就是说不必建立超级源点了
    if (spfa(n)) //从n出发，存在负环，不等式无解
        puts("-1");
    else {
        spfa(1); // 1号奶牛和N号奶牛间
        if (d[n] == INF)
            puts("-2"); //从1出发不能到达n，输出-2
        else
            printf("%d\n", d[n]); //最短路就是最大距离
    }
    return 0;
}