题目描述

幼儿园里有 N个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式

输入的第一行是两个整数 N,K。

接下来 K行，表示分配糖果时需要满足的关系，每行3个数字 X,A,B。

如果 X=1．表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多。如果 X=2，表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果。
如果 X=3，表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果。
如果 X=4，表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果。
如果 X=5，表示第A个小朋友分到的糖果必须不多于第 B个小朋友分到的糖果。
小朋友编号从1到 N。

输出格式

输出一行，表示老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1。

数据范围

1≤N<105,
1≤K≤105,
1≤X≤5,
1≤A,B≤N

样例

Input

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

Output

11

算法

差分约束

模版题，求每个小朋友分到的糖果的最小值。对于每个小朋友而言，他分到的糖果数量$a$应该满足一系列不等式$a \ge x_{1}, a \ge x_{2}, … , a \ge x_{n}$等等，则他至少应该分到$max ( x_{1}, x_{2}, …, x_{n} )$个糖果，故应该求最长路。以如下方式建图：对于不等式$a \ge b + w$，建立一条由$b$至$a$边权为$w$的边。当某些不等式建立的边构成一个正环（本题中的环要么是正环要么是长度为0的环）时，无解。

不加优化的spfa会被卡，附两个玄学优化：
- 当spfa中while循环的次数超过2-3倍的结点数量时，终止循环，返回存在负环。
- 将队列换成栈

经过无数次的提交，发现最开始入队或入栈的n个结点的顺序可能会影响是否tle，感觉很玄学。。

时间复杂度

spfa $O(n \times m)$ ??

C++ 代码两份

队列

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;
const int N = 100010, M = 200010;

int h[N], va[M], ne[M], we[M], idx;
int d[N], cnt[N];
bool st[N];
int n, m;

void insert(int u, int v, int w) {
    va[++idx] = v, we[idx] = w, ne[idx] = h[u], h[u] = idx;
}

bool spfa() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        d[i] = 1;
        q.push(i);
        st[i] = true;
    }
    int cnt_while = 0;
    while (!q.empty()) {
        int ver = q.front();
        q.pop();
        st[ver] = false;
        for (int i = h[ver]; i; i = ne[i]) {
            int j = va[i], w = we[i];
            if (d[j] < d[ver] + w) {
                d[j] = d[ver] + w;
                cnt[j] = cnt[ver] + 1;
                if (++cnt_while > 2 * n) return true;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, u, v;
        scanf("%d%d%d", &x, &u, &v);
        if (x == 1) insert(u, v, 0), insert(v, u, 0);
        else if (x == 2) insert(u, v, 1);
        else if (x == 3) insert(v, u, 0);
        else if (x == 4) insert(v, u, 1);
        else insert(u, v, 0);
    }
    bool loop = spfa();
    if (loop) puts("-1");
    else {
        LL res = 0;
        for (int i = 1; i <= n; i++) res += d[i];
        printf("%lld\n", res);
    }
    return 0;
}

栈

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>

using namespace std;

typedef long long LL;

const int N = 100010, M = 200010;

int h[N], va[M], ne[M], we[M], idx;
int d[N], cnt[N];
bool st[N];
int n, m;

void insert(int u, int v, int w) {
    va[++idx] = v, we[idx] = w, ne[idx] = h[u], h[u] = idx;
}

bool spfa() {
    stack<int> stk;
    for (int i = n; i >= 1; i--) { //从1-n循环会tle
        d[i] = 1;
        stk.push(i);
        st[i] = true;
    }
    while (!stk.empty()) {
        int ver = stk.top();
        stk.pop();
        st[ver] = false;
        for (int i = h[ver]; i; i = ne[i]) {
            int j = va[i], w = we[i];
            if (d[j] < d[ver] + w) {
                d[j] = d[ver] + w;
                cnt[j] = cnt[ver] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    stk.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) insert(a, b, 0), insert(b, a, 0);
        else if (x == 2) insert(a, b, 1);
        else if (x == 3) insert(b, a, 0);
        else if (x == 4) insert(b, a, 1);
        else insert(a, b, 0);
    }

    bool loop = spfa();
    if (loop) puts("-1");
    else {
        LL res = 0;
        for (int i = 1; i <= n; i++)
            res += d[i];
        printf("%lld\n", res);
    }
    return 0;
}