【题解】51 nod 1340 地铁环线 | 差分约束 — Iris

不难看出这是一道差分约束的题目。

但是如果想按照通常的题目那样去建边的话，就会发现这句话——相邻两站的距离至少是 1 公里——建边后就直接让整个题出现了负环 (默认是按求最短路建边)，没法做了。

这时我们就需要使用断环为链的技巧。

可以设 $len$为地铁环线总长

那么就需要把 $a→b(a>b)$的限制条件转换为 $b→a$的限制条件，比如 $dis(a,b)\leq k$转换为 $dis(b,a)\geq len-k$。总算能连边建图惹

如果现在要判断是否有解，那方法肯定是 $spfa$判负环。

但问题在于 $len$是未知量，如果用 $len$表示每一条边，那么 $e_i=len\pm d_i\ or\ \pm\ d_i$。

因为有没有解的关键在于有没有负环，所以：

考虑图上每一个环, 其权值一定可以表示为 $val=k×len+b$ 的形式. 那么现在分类讨论一下每一个环.
– $k=0$ 且 $b<0$ 时, $val<0$，为负环, 一定无解；
– $k<0$ 且 $b<0$ 时, $val<0$，为负环, 一定无解；
– $k<0$ 且 $b>0$ 时, 如果出现 $val<0$，可以通过减小 $len$ 来消除负环；
– $k>0$ 时, 如果出现 $val<0$，可以通过增大 $len$ 来消除负环。

这样思考会发现 $len$的合法大小一定是一段连续区间

所以可以确定一个 $INF$，然后二分 $len$，由上述规律找到 $len$的合法区间的左右端点，如果右端点接近 $INF$则判断为无数个解。

$tips$：
– 凡是没有说明联通的图都要小心；
– 可能只有一个点；
– 因为 $e_i=len\pm d_i\ or\ \pm\ d_i$，而 $len$是变量，所以建边的时候存 $len$的系数和 $d_i$;
– 若一个点入队次数超过 n, 则有负权环, 然后要判断 $k$的值，来决定二分方向，要记录来时的边 废话，并且把环取出来 可能有小尾巴呀；

代码:

#include <set>
#include <map>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <utility>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge{
    int nx,from,to,k,v;
};

#define N 55
#define M 55
#define INF 100000000000
#define mid ((l+r)>>1)

int T,n,m1,m2;
int cnt,head[N];
int st,pre[N],ar[N],inq[N],vis[N];
long long L,R,dis[N];
queue <int> Q;
edge e[M*2+N*2];

inline void clear(){
    cnt=L=R=0;
    memset(head,0,sizeof(head));
}

inline void add(int u,int v,int k,int w){
    e[++cnt]=edge{head[u],u,v,k,w};
    head[u]=cnt;
}

inline int spfa(long long len){
    while(!Q.empty()) Q.pop();
    memset(ar,0,sizeof(ar));
    memset(inq,0,sizeof(inq));
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;++i) dis[i]=INF;
    Q.push(st); inq[st]=1; dis[st]=0;
    while(!Q.empty()){
        int x=Q.front(); Q.pop(); inq[x]=0;
        for(int i=head[x];i;i=e[i].nx){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].k*len+e[i].v){
                dis[y]=dis[x]+e[i].k*len+e[i].v;
                pre[y]=i;   ar[y]=ar[x]+1;
                if(ar[y]>n+1){
                    int tail,k=0;   
                    for(int j=y;j;j=e[pre[j]].from)                     
                        if(vis[j]){tail=j;break;}
                        else vis[j]=1;
                    k+=e[pre[tail]].k;
                    for(int j=e[pre[tail]].from;j!=tail;j=e[pre[j]].from)
                        k+=e[pre[j]].k;
                    if(k==0) return 1;
                    if(k>0)  return 2;
                    if(k<0)  return 3;
                }
                if(!inq[y]) inq[y]=1,Q.push(y);
            }
        }
    }
    return 4;
}

int main(){
    scanf("%d",&T);
    while(T--){
        clear();
        scanf("%d%d%d",&n,&m1,&m2);
        add(1,n,1,-1);
        for(int i=2;i<=n;++i) add(i,i-1,0,-1);
        for(int i=1;i<=n;++i) add(st,i,0,0);
        int a,b,d;
        for(int i=1;i<=m1;++i){
            scanf("%d%d%d",&a,&b,&d); ++a,++b;
            if(a<b) add(b,a,0,-d);
            else add(b,a,1,-d);
        }
        for(int i=1;i<=m2;++i){
            scanf("%d%d%d",&a,&b,&d); ++a,++b;
            if(a<b) add(a,b,0,d);
            else add(a,b,-1,d);
        }
        int flag;
        bool OK=0;
        long long l=1,r=INF;
        while(l<=r){
            flag=spfa(mid);
            if(flag==1) break; 
            else if(flag==2) l=mid+1;
            else if(flag==3) r=mid-1;
            else OK=1,L=mid,r=mid-1;
        }
        l=1,r=INF;
        while(l<=r){
            flag=spfa(mid);
            if(flag==1) break; 
            else if(flag==2) l=mid+1;
            else if(flag==3) r=mid-1;
            else OK=1,R=mid,l=mid+1;
        }
        if(!OK) printf("0\n");
        else if(R>=INF) printf("-1\n");
        else printf("%lld\n",R-L+1);
    }
    return 0;                           
}

参考了 Rothen 的博客

我也不知道他 blog 为啥没了，也不敢问