差分约束

这题没什么好说的.
可以很快的看出是差分约束的模板题.
当然,如果不知道什么是差分约束,建议去看一下yxc大佬的讲解.
差分约束最主要是要搞清建边的方向.
还有这道题由于问的是最小值,要求最长路.
另外,对于此题而言,十年oi一场,不开long long见祖宗.
在此不得不说句话:stack大法好啊!

时间复杂度 $SPFA玄学复杂度$

C++ 代码

#include<bits/stdc++.h>
#define N 100010
#define M 300010
#define ll long long
using namespace std;
struct node{
    int to,d,next;
}e[M];
int tot,head[N];
int n,k,dis[N],cnt[N];
bool vis[N];
inline void add(int u,int v,int d)//加边什么的都是老套路了
{
    tot++;
    e[tot].to=v;
    e[tot].d=d;
    e[tot].next=head[u];
    head[u]=tot;
}
inline bool SPFA()//SPFA模板
{
    memset(dis,-0x3f,sizeof(dis));
    stack<int> q;
    q.push(0),dis[0]=0,vis[0]=1;
    while(!q.empty()){
        int now=q.top();
        q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]<dis[now]+e[i].d){
                dis[v]=dis[now]+e[i].d;
                cnt[v]=cnt[now]+1;
                if(cnt[v]>=n+1)//注意判负环
                    return 0;
                if(!vis[v])
                    q.push(v),vis[v]=1;
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;i++){
        int x,u,v;
        scanf("%d %d %d",&x,&u,&v);
        //分五种情况建边,注意方向
        if(x==1)
            add(v,u,0),add(u,v,0);
        if(x==2)
            add(u,v,1);
        if(x==3)
            add(v,u,0);
        if(x==4)
            add(v,u,1);
        if(x==5)
            add(u,v,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+=dis[i];
        printf("%lld\n",res);
    }
    return 0;
}