[LUOGU] P3275 [SCOI2011]糖果

显然的差分约束，除了题目给出的约束以外，边界是(A_x-Ageq1)
判环有两种方法，要不就是SPFA记录最长路经过次数，要不就是tarjan缩了SCC，看SCC内有没有正权边

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define int long long
using namespace std;

inline int rd(){
  int ret=0,f=1;char c;
  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
  while(isdigit(c))ret=ret*10+c-'0',c=getchar();
  return ret*f;
}
#define space() putchar(' ')
#define nextline() putchar('
')
void pot(int x){if(!x)return;pot(x/10);putchar('0'+x%10);}
void out(int x){if(!x)putchar('0');if(x<0)putchar('-'),x=-x;pot(x);}

const int MAXN=4000005;

int n,m;

int nex[MAXN],to[MAXN],wi[MAXN];
int ecnt,head[MAXN];
inline void add(int x,int y,int w){
//	cout<<x<<" "<<y<<" "<<w<<endl;
    nex[++ecnt] = head[x];
    to[ecnt] = y;
    wi[ecnt]=w;
    head[x] = ecnt;
}

int dis[MAXN],inq[MAXN],cnt[MAXN];
queue<int> Q;
bool spfa(int st){
//	memset(dis,0x3f,sizeof(dis));
    dis[st]=0;Q.push(st);
    while(!Q.empty()){
        int top=Q.front();Q.pop();inq[top]=0;
 		
 		cnt[top]++;if(cnt[top]>n) return 1;
        for(int i=head[top];i;i=nex[i]){
            int v=to[i];
            if(dis[top]+wi[i]>dis[v]){
                dis[v]=dis[top]+wi[i];
                if(!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
    return 0;
}

int dfn[MAXN],low[MAXN],tim;
int sta[MAXN],ins[MAXN],top; 
int bl[MAXN],scc;
vector<int> vec[MAXN];
void tarjan(int x){
    dfn[x]=low[x]=++tim;
    ins[sta[++top]=x]=1;
    for(int i=head[x];i;i=nex[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }else if(ins[v]){
            low[x]=min(low[x],dfn[v]);	
        }
    }
    if(dfn[x]!=low[x]) return;
    int elm=-1;++scc;
    do{
        elm=sta[top--];
        ins[elm]=0;
        bl[elm]=scc;
        vec[scc].push_back(elm);
    }while(elm!=x);
}


signed main(){
    n=rd();m=rd();
    int t,x,y;
    for(int i=1;i<=m;i++){
        t=rd();x=rd();y=rd();
        if(t==1) add(x,y,0),add(y,x,0);
        if(t==2) add(x,y,1);
        if(t==3) add(y,x,0);
        if(t==4) add(y,x,1);
        if(t==5) add(x,y,0);
    }
    for(int i=n;i>=1;i--) add(n+1,i,1);
    for(int i=1;i<=n+1;i++){
        if(!dfn[i]) tarjan(i);	
    }
    for(int i=1;i<=scc;i++){
        int sz=vec[i].size();
        for(int j=0;j<sz;j++){
            for(int k=head[vec[i][j]];k;k=nex[k]){
                int v=to[k];
                if(bl[v]!=i) continue;
                if(wi[k]!=0) return puts("-1"),0;	
            }
        }
    }
    if(spfa(n+1)) return puts("-1"),0;
    int ans=0;
    for(int i=1;i<=n;i++) ans+=dis[i];
    out(ans);
}