这题一眼题就是差分约束了。
然后有一点特别的就是这一题差分是找最长路。
注意：开LL。有个全是一条链的坑比点，没搞懂hzw那个玄学的进栈建边的顺序，然后我就想一个点虽然最多被访问n次，但数据肯定不会不会这么极端，那我就判被访问了n/10次，苟过去了。。。
upd今天看到了真正的正解，用强联通判环，环里面的边权必须是0否则无解。都是0那就缩点，跑拓扑排序就好
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; struct node { int x,y,d,next; }a[410000];int len,last[110000]; void ins(int x,int y,int d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } int top,sta[210000]; LL d[2100000];int ru[210000]; bool v[210000]; int main() { freopen("candy.in","r",stdin); freopen("candy.out","w",stdout); int n,m,op,A,B; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&op,&A,&B); if(op==1) ins(B,A,0), ins(A,B,0);//A==B 两个不等式：B>=A A>=B else if(op==2) ins(A,B,1);//A少于B B>=A+1 else if(op==3) ins(B,A,0);//A不少于B A>=B else if(op==4) ins(B,A,1);//A多于B A>=B+1 else if(op==5) ins(A,B,0);//A不多于B B>=A } //每个小朋友都要有糖 A>=1 A>=st+1 for(int i=1;i<=n;i++)ins(0,i,1); //---------composition---------------- top=0; for(int i=n;i>=0;i--)sta[++top]=i; memset(d,0,sizeof(d)); memset(ru,0,sizeof(ru)); memset(v,false,sizeof(v));v[sta[top]]=true; bool bk=false; while(top!=0) { int x=sta[top];top--; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]<d[x]+a[k].d) { d[y]=d[x]+a[k].d; if(v[y]==false) { v[y]=true; ru[y]++; if(ru[y]==m/10){bk=true;break;} sta[++top]=y; } } } v[x]=false; if(bk==true)break; } //------------spfa-------------------- if(bk==true)printf("-1 "); else { LL ans=0; for(int i=1;i<=n;i++)ans+=d[i]; printf("%lld ",ans); } return 0; }