【二分+差分约束】 地铁

一道个人感觉比较毒瘤的题目。

题意：

有一个环形的地铁线，有如下两种约束条件。 1 a b w：表示顺时针 a ---> b 的长度>=w 2 a b w：表示顺时针 a---->b 的长度<=w

分析：

1. 我假设这条铁路的总长度为C。
2. 并且定义d[i] 为 顺时针 1~i路线的长度

那么，我们就可以得到如下信息

1. d[i+1]-d[i]>=1
2. d[1]=0
3. d[n]-d[1]>=C-1

并且上述的两个约束条件我们就可以进行化简了。

约束条件化简:

a<b a节点在b节点的左边 ===> d[b]-d[a] ? w a>b a节点在b节点的右边，此时的顺时针需要转一圈了。如下图：

因为这条线路的总长度为C，那么剩下的长度就为C-w。如下

为了更简化题目，我们把所有的操作都记录为 k*c+w的形式。 那么，对于约束条件1，a<b时： d[b]-d[a]>=0 * C + w 同样的，其他的也可以化简....

二分：

我们把所有的已知条件已经化成了 k*C+w 的形式，但是此时有一个未知数C，我们就需要二分一下，计算C的最大值和最小值，此时C的范围就是答案。

我们就可以去每次二分查找最大值和最小值。

假设我们当前二分到mid的位置，我们就去将这个mid去替换路线上的C值。

会出现下面两种情况：

1. 不会出现负环 ==> 答案合理，更新端点。
2. 出现负环：

出现负环： 当出现负环的时候，我们就需要看情况考虑当前结果是否合理。 因为我们用的有mid,所以我们去判断，在这个负环中，我们如果将负环中的边全部加起来的话，得到( $k*C+sum$ )。 其中k为负环中，mid(总长度)的系数，sum为所有的w的和。

因为sum是常数那么就需要分类讨论了。

• k==0 那肯定无解 ==> 负环中把线的总长给约掉了，无论mid多少都会出现负环
• k>0 那就有可能是mid的值小了，当mid值大的时候，负环 (路径上的边权和增大) 就会消失
• k<0 mid的增大就会使得负环更负，我们就需要得到一个更小的mid.

由此，我们就可以去二分它的线路总长度了，得到最大长度和最小长度。输出区间大小即可。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e2+12,M=1e4+12;
const ll inf=1e12,biginf=9e18;
int cnt,head[N],vis[N],a[N],n,m;
ll d[N];
int pre[N];
struct{
  int from,to,nex,k,w;
}edge[M];
void addedge(int u,int v,int k,int w)
{
  cnt++;
  edge[cnt]={ u,v,head[u],k,w };
  head[u]=cnt;
}
int solve(ll mid)
{
  for(int i=1;i<=n;i++)
  {
    d[i]=biginf;

  }
  d  [1]=0;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=cnt;j++)
    {
      int v=edge[j].to,u=edge[j].from,k=edge[j].k,w=edge[j].w;
      if( d[ v ]>d[u]+w+k*mid )
      {
        d[v]=d[u]+w+k*mid;
        pre[v]=j;
      }
    }
  }
  for(int j=1;j<=cnt;j++)
  {
    int v=edge[j].to,u=edge[j].from,k=edge[j].k,w=edge[j].w;
    if( d[ v ]>d[u]+w+k*mid )
    {
      int sum=k;
      for(int i=1;i<=n;i++)
      {
        v=edge[ pre[v] ].from;
        sum+=edge[ pre[v] ].k;
      }
      return sum>=0 ? 1 : -1;
    }
  }
  return 0;
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<n;i++)
  {
    addedge( i+1,i,0,-1 );
  }
  addedge( 1 , n , 1 , -1 );
  while( m-- )
  {
    int op,u,v,w;
    scanf("%d%d%d%d",&op,&u,&v,&w );
    if( op==1 )
    {
      if( v>u ) addedge( v,u,0,-w );
      else addedge( v,u,1,-w );
    }
    else{
      if( v>u ) addedge( u,v,0,w );
      else addedge( u,v,-1,w );
    }
  }

  ll l=0,r=inf;
  while( l<r )
  {
    ll mid=l+r+1>>1; // 向上取整：因为是整除，所以会去掉末尾的0，然后要找左端点的值，为防止 r=l+1 这样情况下，更新出错，所以+1
    int t=solve(mid);
    if( t==0 ) l=mid; //二分最大值，合理的时候更新左端点
    else if( t==1 ) l=mid+1;  //不合理，出现负环，但是负环内k大于0，这样更新左端点就可以逃出负环
    else r=mid-1;  //反之
  }
  ll up=l;
  if( up>=inf ) {printf("-1");return 0;}
   l=0,r=inf;
  while( l<r )
  {
    ll mid=l+r>>1;  // 反之整除向下取整
    int t=solve(mid);
    if( t==0 ) r=mid;
    else if( t==1 ) l=mid+1;
    else r=mid-1;
  }
  printf("%lld",up-l+1);
}