差分约束

考虑建边就好了。
1.若X=1,则建立边(u,v,0),表示两者相等.
2.若X=2,则建立边(u,v,1),表示v比u大一.
3.若X=3,则建立边(v,u,0),表示u大于等于v.
4.若X=4,则建立边(v,u,1),表示u比v大一.
5.若X=5,则建立边(u,v,0),表示u小于等于v.
注意建边方向,因为要保证最优性,所以从小的往最大的转移,再跑裸的spfa.

#include<bits/stdc++.h>
#define re register
#define v first
#define w second
using namespace std;
typedef long long ll;
const double eps=1e-7;
const int INF=1e9;
const int N=1e6+5;
/*
    差分约束:
        1.若X=1,则建立边(u,v,0),表示两者相等.
        2.若X=2,则建立边(u,v,1),表示v比u大一.
        3.若X=3,则建立边(v,u,0),表示u大于等于v.
        4.若X=4,则建立边(v,u,1),表示u比v大一.
        5.若X=5,则建立边(u,v,0),表示u小于等于v.
    注意建边方向,因为要保证最优性,所以从小的往最大的转移,再跑裸的spfa.
*/
int x;
int n,k;
bool flag;
int cnt[N];
int dis[N];
bool vis[N];
vector<pair<int,int> > boy[N];
inline void spfa() {
    queue<int > girl;
    dis[0]=0;
    vis[0]=1;
    girl.push(0);
    while(girl.size()) {
        int now=girl.front();
        girl.pop();
        if(cnt[now]==n-1) {
            flag=1;
            printf("-1");
            return ;
        }
        cnt[now]++;
        vis[now]=0;
        for(int i=0; i<boy[now].size(); ++i) {
            int to=boy[now][i].v,w=boy[now][i].w;
            if(dis[to]<dis[now]+w) {
                dis[to]=dis[now]+w;
                if(!vis[to]) {
                    vis[to]=1;
                    girl.push(to);
                }
            }
        }
    }
    return ;
}
int main() {
    int a,b;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=k; ++i) {
        scanf("%d%d%d",&x,&a,&b);
        if(x==1) boy[a].push_back(make_pair(b,0)),boy[b].push_back(make_pair(a,0));
        else if(x==2) {
            if(a==b) {
                printf("-1");
                return 0;
            }
            boy[a].push_back(make_pair(b,1));
        } else if(x==3) boy[b].push_back(make_pair(a,0));
        else if(x==4) {
            if(a==b) {
                printf("-1");
                return 0;
            }
            boy[b].push_back(make_pair(a,1));
        } else if(x==5) boy[a].push_back(make_pair(b,0));
    }
    for(int i=1; i<=n; ++i) boy[0].push_back(make_pair(i,1));
    spfa();
    if(flag) return 0;
    ll ans=0;
    for(int i=1; i<=n; ++i) ans+=dis[i];
    printf("%lld",ans);
}