列队 （HG 2018.10.25 T1）

  这一题是典型的差分约束模板题，当然也可以用并查集做。 差分约束是解决形如 $\begin{cases} \text{x1-x2<=k1} \\ \text{x2-x3<=k2} \\ \text{x1-x3<=k1} \\ ......\end{cases}$ 这样的方程组解的范围。 然后我们可以发现x1-x2<=k1即x1<=k1+x2，这是不是像spfa的转移只不过倒过来了？ 我们就想到了建边，建一条x2->x1权值为k1的边。然后我们发现，跑最短路，其实就是最小的解，最长路就是最大的解！ 然后对于这一题，我们发现只要出现两条路到达同一个点的路长是不一样的，那么就不成立。针对这一道题，我们还需要建反边 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; const int Top=6666666666666666; int n,m,cnt=0; int head[410000],nxt[410000],to[410000],val[410000]; int ma=0,mi=0; int q[1000000],dis[100100],f[100100],vis[100100]; void addedge(int x,int y,int z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } bool spfa(int x) { int l=0,r=1; q[1]=x;vis[x]=1;dis[x]=0; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(dis[v]==Top) { dis[v]=dis[u]+val[i]; ma=max(ma,dis[v]); mi=min(mi,dis[v]); if(ma-mi>1e9) return 0; vis[v]=1; if(!f[v]) q[++r]=v,f[v]=1; } else if(dis[v]!=dis[u]+val[i]) return 0; } f[u]=0; } return 1; } signed main() { memset(head,-1,sizeof(head)); for(int i=1;i<=100000;i++) dis[i]=Top; scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%lld%lld%lld",&x,&y,&z); addedge(x,y,z); addedge(y,x,-z); } for(int i=1;i<=n;i++) if(!vis[i]) {if(!spfa(i)) {printf("impossible");return 0;}} printf("%lld",ma-mi); return 0; } ```