莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 求最小值就是求最长路（正环），求最大值就是求最短路（负环）
2. 建立虚拟源点保证它可以到达所有点
3. 如果存在环则说明一定无解
4. 求最小值：以 x[i] 为例，x[i] >= x[j] + c[1] >= x[k] + c[1] + c[2] >= ...  
5. 则我们求的是所有下界的最大值，即 dist[i]，也就是求最长路

#include<bits/stdc++.h>

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;
int dist[N],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()
{
    stack<int> q;
    q.push(0);
    st[0]=true;

    while(q.size())
    {
        auto t=q.top();
        q.pop();
        st[t]=false;

        for(int i=h[t];~i;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 true;

                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return false;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    while(m--)
    {
        int x,a,b;
        cin>>x>>a>>b;
        if(x==1) add(b,a,0),add(a,b,0); // A >= B, B >= A
        else if(x==2) add(a,b,1); // B >= A + 1
        else if(x==3) add(b,a,0); // A >= B
        else if(x==4) add(b,a,1); // A >= B + 1
        else add(a,b,0); // A >= B
    }

    //建立虚拟源点，保证它可以到达所有点
    for(int i=1;i<=n;i++) add(0,i,1);

    //存在正环，则一定无解
    if(spfa()) cout<<-1<<endl;
    else 
    {
        LL res=0;

        for(int i=1;i<=n;i++) res+=dist[i];

        cout<<res<<endl;
    }

    return 0;
}