本文共 1873 字，大约阅读时间需要 6 分钟。
显然的差分约束，除了题目给出的约束以外，边界是\(A_x-A\geq1\)
判环有两种方法，要不就是SPFA记录最长路经过次数，要不就是tarjan缩了SCC，看SCC内有没有正权边
#include #include #include #include #include #define int long longusing 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('\n')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< <<" "< <<" "< <
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
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