分析

• 本题求最小值，因此应该使用最长路，对应不等式应该是$\ge$，如果存在正环，则说明无解。

• 依次分析题目中给的5个条件：

（1）$A==B \iff A \ge B, B \ge A$；

（2）$A<B \iff B \ge A + 1$；

（3）$A \ge B \iff A \ge B$；

（4）$A > B \iff A \ge B + 1$；

（5）$A \le B \iff B \ge A$；

• 另外这个题目还有一个隐含条件：每个小朋友都要分到糖果，因此$x \ge 1$。因此我们可以建立一个虚拟源点$x_0=0$，则有：$x_i \ge x_0+1，i=1,…,n$。

• 根据不等式$x_i \ge x_0+1$可以建立从0号点到任意点的边，边权为1，因为可以到达任意点，所以可以到达任意边。

• 因为我们能求出每个$x_i$的最小值，所以总体最小值就是所有的$x_i$之和。

• 需要建立的边数：如果K取$10^5$，所有的条件都是（1），需要$2 \times 10^5$条边，同时还要从虚拟源点建立边，需要$10^5$条，因此一共需要$3 \times 10^5$条边。

• 另外如果每个小朋友的糖果数是单调递增的，则结果可能爆int，因此需要使用long long存储结果。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int stk[N];
int cnt[N];  // 判断是否存在负环
bool st[N];  // 某个点是否在栈中

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 返回是否有解
bool spfa() {

    memset(dist, -0x3f, sizeof dist);

    int tt = 0;  // 指向栈顶
    stk[++tt] = 0;
    st[0] = true;
    dist[0] = 0;

    while (tt > 0) {

        int t = stk[tt--];
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return false;
                if (!st[j]) {
                    stk[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }

    return true;
}

int main() {

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

    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;
}