本文移植自个人的原博客（原文）

题目描述

$n$个城市首尾依次通过$n$条非负权边相连。存在两种约束，分别表示从$S$到$T$的顺时针路径小于等于$L$或大于等于$L$，求出$n$条边可能的总权值个数。

$n<=50$

题解

根据题目条件易知应按权值前缀和建立差分约束系统，并且二分答案。对于一个节点顺时针走到标号更小节点的情况，应该将当前二分的答案代入式子中进行化简，如果图最短路中存在负环（亦或最长路存在正环），则当前答案不合法，难点主要在此时答案应该增大还是减小上，应将当前二分答案的系数代入环中，判断系数的正负性，如果系数为$0$，则负环与二分值无关，即为无穷多解，如果系数大于$0$，则答案增大时负环权值增大，如果系数小于$0$，则答案减小时负环权值增大。两次二分出可行区间的左右端点，即为所求。（需要注意的是，由于要得到答案在环上的系数，所以当找到负环时，应只返回负环的系数，而不应返回整条路径的系数）

#include<bits/stdc++.h>
#define vi vector<int>
#define mp make_pair
#define sd second
#define fr first
using namespace std;
typedef long long ll;
const int N = 1e3+1;
const ll inf = 1e14;
int head[N],cnt;
struct nd{
    int ne,to,f,fr;ll w;
}e[N*2];
void in(int x,int y,ll w,int f){
    e[++cnt].to=y;e[cnt].fr=x;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;e[cnt].f=f;
}
class YamanoteLine{
    public:
    ll howMany(int n,vi s1,vi t1,vi l1,vi s2,vi t2,vi l2){
        ll l=n,r=inf,L=-1,R=inf;
        for(int i=0;i<s1.size();++i)s1[i]++,t1[i]++;
        for(int i=0;i<s2.size();++i)s2[i]++,t2[i]++;
        while(l!=r){
            ll mid=(l+r+1)>>1;
            pair<bool,ll>ck=can(mid,n,s1,t1,l1,s2,t2,l2);
            if(ck.fr||ck.sd>0)l=mid;
            else    r=mid-1;
        }
        R=l;
        l=n,r=inf;
        while(l!=r){
            ll mid=(l+r)>>1;
            pair<bool,ll>ck=can(mid,n,s1,t1,l1,s2,t2,l2);
            if(ck.fr||ck.sd<0)r=mid;
            else    l=mid+1;
        }
        L=l;
        if(L>=n&&R==inf)return -1;
        if(L>R)return 0;
        return R-L+1;
    }
    private:
    int q[N],cntx;
    pair<ll,ll> d[N];
    bool vis[N];
    pair<bool,ll> spfa(int n,int x){
        vis[x]=1;
        for(int i=head[x];i;i=e[i].ne){
            int y=e[i].to;
            pair<ll,ll> t=mp(d[x].fr+e[i].w,d[x].sd+e[i].f);
            if(d[y].fr>t.fr){
                q[++cntx]=i;
                d[y]=t;
                if(vis[y]){
                    int tot=0;
                    while(e[q[cntx]].fr!=y)tot+=e[q[cntx]].f,cntx--;
                    tot+=e[q[cntx]].f;
                    return mp(0,tot);
                }
                pair<bool,ll>res=spfa(n,y);
                cntx--;
                if(!res.fr)return res;
            }
        }
        vis[x]=0;
        return mp(1,0ll);
    }
    pair<bool,ll> can(ll ans,int n,vi s1,vi t1,vi l1,vi s2,vi t2,vi l2){
        memset(head,0,sizeof(head));cnt=0;
        for(int i=0;i<s1.size();++i){
            int x=s1[i],y=t1[i];ll w=l1[i];
            if(y>x)in(y,x,-w,0);
            else    in(y,x,ans-w,1);
        }
        for(int i=0;i<s2.size();++i){
            int x=s2[i],y=t2[i];ll w=l2[i];
            if(y>x)in(x,y,w,0);
            else    in(x,y,w-ans,-1);
        }
        in(0,n,ans,1);in(n,0,-ans,-1);
        for(int i=1;i<=n;++i)in(i,i-1,-1,0),in(0,i,ans,1);
        for(int i=1;i<=n;++i)d[i]=mp(inf,0);
        d[0]=mp(0,0);
        memset(vis,0,sizeof(vis));
        cntx=0;
        return spfa(n,0);
    }
}