题解：P7624 [AHOI2021初中组] 地铁

· · 题解

分享一个完全不用考虑负环的做法。

首先不难发现，设 f_{i} 为从 1 到 i 的距离，那么在已知 f_n=C 的情况下所有的限制都是一些与 f 有关的不等式。

具体来说，对于一次 op_i,s_i,t_i,L_i，假设 x=s_i,y=t_i,d=L_i

若 x>y：

  1. 当 op_i=1 时，f_y\le f_x+C-d。

  2. 当 op_i=2 时，f_x\le f_y+d-C。

若 x<y：

  1. 当 op_i=1 时，f_x\le f_y-d。

  2. 当 op_i=2 时，f_y\le f_x+d。

且 \forall 1\le i<n,f_i\le f_{i+1}-1。

根据这些式子，我们可以利用差分约束算法判断一个 f_n=C 时是否存在合法解。

发现挪动 C 的值，会等量挪动若干不等式的某一个端点，所以使得有解的 C 的取值范围是一段区间。

我们只要得到合法区间的两个端点，就可以得到答案。

但是值域超级大，得考虑快速找到端点，首先想到的是二分，但是由于合法点是区间，直接二分显然错误，如何解决呢？

我们试图实现一个功能为给出 x，快速判断是否存在 i\ge x，满足 i 是一个合法点，如果可以做到这一点，那么我们就可以找到合法区间的左端点，从而使用朴素的二分找到右端点解决原问题。

值域解决是否存在 i\ge x，使得 i 为合法点，发扬人类智慧，考虑当 C=i 足够大时，限制 1 必然满足，而其它限制都是 C 较小才容易满足，所以直接去掉限制 1 后，按照 C=x 跑一遍差分约束即可！

至于判断是否有无穷解，我们在代码实现中总是会设置一个极大值 inf，如果最终答案大于 0.9inf，直接认为无穷解即可。

时间复杂度 O(n(n+m)\log V)。

代码如下，不过具体实现和上述思路有略微区别：

#include<bits/stdc++.h> 
#define int long long
using namespace std;
struct edge{
    int from,to,val;
}e[505<<2];int head[505],siz;
void addedge(int x,int y,int z){
    swap(x,y);
    e[++siz].to=y,e[siz].val=z;
    e[siz].from=head[x],head[x]=siz;
}
int n,m;
int dis[505],vis[505],cnt[505];
bool spfa(){
    for(int i=0;i<=n;i++){
        dis[i]=1e14;
        vis[i]=cnt[i]=0;
    }
    dis[0]=0;
    queue<int> q;q.push(0);
    while(!q.empty()){
        int now=q.front();q.pop();
        vis[now]=0;
        cnt[now]++;
        if(cnt[now]>=n) return 0;
        for(int i=head[now];i;i=e[i].from){
            int u=e[i].to;
            if(dis[u]>dis[now]+e[i].val){
                dis[u]=dis[now]+e[i].val;
                if(!vis[u]){
                    vis[u]=1;
                    q.push(u);
                }
            }
        }
    }return 1;
}
void clear(){
    for(int i=0;i<=n;i++) head[i]=0;
    for(int i=1;i<=siz;i++) e[i].from=e[i].to=e[i].val=0;
    siz=0;
}
int op[505],s[505],t[505],d[505];
int check(int L,bool C){
    clear();
    for(int i=1;i<n;i++){
        addedge(i,i+1,-1);
    }
    for(int i=1;i<=m;i++){
        if(s[i]<=t[i]){
            if(op[i]==1){
                addedge(s[i],t[i],-d[i]);
            }
            else{
                addedge(t[i],s[i],d[i]);
            }
        }
        else{
            if(op[i]==1){
                addedge(s[i],t[i],L-d[i]);
            }
            if(op[i]==2){
                if(!C) continue; 
                addedge(t[i],s[i],d[i]-L);
            }
        }
    }
    addedge(n,0,L);
    bool ret=spfa();
    for(int i=1;i<=n;i++) if(dis[i]<=0) return 0;
    return ret;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>op[i]>>s[i]>>t[i]>>d[i];
    }
    int l=n,r=1e14,pos=1e14;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid,0)==1){
            pos=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    l=pos,r=1e14;
    int L=pos;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid,1)){
            pos=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    int R=pos;
    l=n,r=pos;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid,1)){
            pos=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    l=n,r=pos;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid,1)){
            L=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    l=pos,r=1e14;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid,1)){
            R=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    if(check(pos,1)==0||check(L,1)==0||check(R,1)==0){
        return 1;
    }
    int ans=R-L+1;
    if(ans>9e13){
        cout<<-1;
        return 0;
    }
    cout<<R-L+1<<'\n';
}