python/TangDou/AcWing/ChaFenYueShu/1169_stack.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010;

stack<int> q; // 有时候换成栈判断环很快就能找到答案
LL dist[N];
bool st[N];
int cnt[N];
int n, m; // 表示点数和边数
// 邻接表
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++;
}

bool spfa() {                         // 最长路，判正环
    memset(dist, -0x3f, sizeof dist); // 最长路，需要初始化为-0x3f

    // 超级源点出发
    dist[0] = 0;
    q.push(0);
    st[0] = 1;

    while (q.size()) {
        int u = q.top();
        q.pop();
        st[u] = 0;

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] < dist[u] + w[i]) { // 求最长路
                dist[v] = dist[u] + w[i];
                cnt[v] = cnt[u] + 1;
                // 注意多加了超级源点,共n+1个节点，边数最多是n
                if (cnt[v] > n) return 1;
                if (!st[v]) {
                    q.push(v);
                    st[v] = 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--) {
        int x, a, b; // X为大小关系描述
        scanf("%d %d %d", &x, &a, &b);

        // 求最小值，需要最长路，即形如： a>=b+1这样形式的式子

        // 表示第 a 个小朋友分到的糖果必须和第 b 个小朋友分到的糖果一样多
        //  a == b  =>  (a >= b , b >= a)  相等的关系，需要传入两条对称的边，即 a>=b,b>=a,边长为0
        if (x == 1) add(a, b, 0), add(b, a, 0);
        // 表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果
        //  a<b => b > a => b >= a+1
        if (x == 2) add(a, b, 1);
        // 表示第 a 个小朋友分到的糖果必须不少于第 b 个小朋友分到的糖果
        // 不少于即大于等于 a >= b
        if (x == 3) add(b, a, 0);
        // 表示第 a 个小朋友分到的糖果必须多于第 b 个小朋友分到的糖果
        //  a>b => a >= b+1
        if (x == 4) add(b, a, 1);
        // 表示第 a 个小朋友分到的糖果必须不多于第 b 个小朋友分到的糖果。
        //  a<=b => b>=a
        if (x == 5) add(a, b, 0);
    }

    // 重点：需要自己从题意中挖掘出一个性质，即 每个小朋友都要至少一个糖果
    //  xi >= 1  => xi >= x0 + 1
    // 将所有节点与超级源点x0相连
    for (int i = 1; i <= n; i++) add(0, i, 1);

    if (spfa())
        puts("-1");
    else {
        LL res = 0;
        for (int i = 1; i <= n; i++) res += dist[i]; // 累加所有最小值的和
        printf("%lld\n", res);
    }
    return 0;
}