【51nod 1340】地铁环线

题目

有一个地铁环线，环线中有N个站台，标号为0,1,2，...，N-1。这个环线是单行线，一共由N条有向边构成，即从0到1,1到2，..k到k+1，...,N-2到N-1，N-1到0各有一条边。定义两站之间的距离，站a与站b间的距离dis(a,b)指从a站出发沿着单行线的边走到达b时所经过的全部长度，即dis(a,b)=dis(a,a+1)+dis(a+1,a+2)+..+dis(k,k+1 mod N)..+dis(b-1,b)。提示一下，a>b时路径为a->a+1->...N-1->0->...->b,注意这是个环线。有两个人向你提供了一些关于环线的信息：

其第一个人提供了M1条信息，每条信息：站点Ai到站点Bi的距离至少是Di，即dis(Ai，Bi)>=Di；

而第二个人提供了M2条信息，每条信息：站点ai到站点 bi的距离最多是di ，即dis(ai，bi)<=di 。

另外，已知相邻两站的距离至少是1公里，且所有站点间的距离都是整数公里。

请根据以上的信息计算这条地铁环线的总长有多少种可能，并输出这个数量，如果如果有长度有无数种可能输出-1.

分析

看到一堆不等式的信息，首先想到就是差分约束，

当总长度s确定时，我们就可以做差分约束，判断有无负环来判断是否合法

连边

    对于dis(Ai,Bi)>=Di，

    	如果Ai<Bi，Bi向Ai连一条的边,边权为-Di

    	如果Ai>Bi，Bi向Ai连一条的边,边权为s-Di

    对于dis(ai,bi)<=di，

    	如果ai<bi，ai向bi连一条的边,边权为Di

    	如果ai>bi，ai向bi连一条的边,边权为-s+Di

	相邻点距离至少为1，类似第一种情况

然后用Bellman_Ford，在进行n-1次松弛操作后，

如果依然可以进行松弛操作，即存在边(a,b)，dis[a]+v(a,b)<dis[b]，就存在负环，则不合法。

反之。

考虑如何求方案数，

我们发现每条边的边权个一次函数，

进行n-1次松弛操作，于是对于每个点的每种s的系数k记录\(dis[x][k]\)，表示当走到x时，s的系数为k的最小值为\(dis[x][k]\)

然后对于每一条边(a,b)维护一个单调栈，表示每一段s的值域是由s的哪个系数控制（详细见程序）

然后对于一段某一段s的值域的，代入s，如果a点的函数值+(a,b)>b点的函数值，则这一段值域对于这一条边是合法的。用个前缀和数组，这一段值域的合法边数加1.

当一段值域的合法边数为总边数时，这段值域的s都合法，ans加上个数。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <bitset>

#include <set>

#include <vector>

const int mo=1e9+7;

const int N=55;

using namespace std;

int T,n,m1,m2,tot,num,vv;

long long dis[N][N*2],inf;

struct list

{

	long long x,v;

}lis[N*N*N*2];

struct line

{

	long long l,r,k,b;

	long long f(long long x)

	{

		return k*x+b;

	}

}s1[N*N*N*2],t1[N*N*N*2];

long long min(long long x,long long y)

{

	return x<y?x:y;

}

long long max(long long x,long long y)

{

	return x>y?x:y;

}

long long up(long long tb,long long tk)

{

	if(tk<0) tk=-tk,tb=-tb;

	long long tt=tb/tk;

	return tt+(tt*tk<tb);

}

long long down(long long tb,long long tk)

{

	if(tk<0) tk=-tk,tb=-tb;

	long long tt=tb/tk;

	return tt-(tt*tk>tb);

}

void push(line *a,int &num,line t)

{

	while(num && t.f(a[num].l)<=a[num].f(a[num].l)) num--;

	if(num) t.l=down(-(a[num].b-t.b),a[num].k-t.k)+1,a[num].r=t.l-1;

	a[++num]=t;

}

void put(long long l,long long r)

{

	lis[++num]=(list){l,1};

	lis[++num]=(list){r+1,-1};

}

void check(line s1,line t1)

{

	long long l=max(s1.l,t1.l),r=min(s1.r,t1.r);

	if(l>r) return;

	line t={0,0,s1.k-t1.k,s1.b-t1.b};

	if(t.f(l)<0 && t.f(r)<0) return;

	put(t.f(l)>=0?l:up(-t.b,t.k),t.f(r)>=0?r:down(-t.b,t.k));

}

struct edge

{

	long long x,y,v,k;

	void BF()

	{

		for(int i=0;i<=2*n;i++)

			if(i+k>=0 && i+k<=2*n) dis[y][i+k]=min(dis[y][i+k],dis[x][i]+v);

	}

	void calc()

	{

		int n1=0,n2=0;

		for(int i=2*n;i>=0;i--)

		{

			if(dis[x][i]<inf/2) push(s1,n1,(line){n,inf,i+k-n,dis[x][i]+v});

			if(dis[y][i]<inf/2) push(t1,n2,(line){n,inf,i-n,dis[y][i]});

		}

		for(int k1=1,k2=1;k1<=n1 && k2<=n2;s1[k1].r<=t1[k2].r?k1++:k2++) check(s1[k1],t1[k2]);

	}

}E[N<<2];

bool cmp(list x,list y)

{

	return x.x<y.x;

}

int main()

{

	for(scanf("%d",&T);T--;)

	{

		scanf("%d%d%d",&n,&m1,&m2);

		memset(dis,1,sizeof(dis));

		memset(lis,0,sizeof(lis));

		inf=dis[0][0],dis[0][n]=0;

		tot=0;

		for(int i=0;i<n;i++) E[++tot]=(edge){(i+1)%n,i,-1,i==n-1};

		long long x,y,v;

		for(int i=1;i<=m1;i++)

		{

			scanf("%lld%lld%lld",&x,&y,&v);

			E[++tot]=(edge){y,x,-v,(x>y)};

		}

		for(int i=1;i<=m2;i++)

		{

			scanf("%lld%lld%lld",&x,&y,&v);

			E[++tot]=(edge){x,y,v,-(x>y)};

		}

		for(int i=1;i<n;i++)

			for(int j=1;j<=tot;j++) E[j].BF();

		for(int i=1;i<=tot;i++) E[i].calc();

		sort(lis+1,lis+1+num,cmp);

		lis[num+1]=(list){inf+1,0};

		long long sum=0,ans=0;

		for(int i=1;i<=num;i++) ans+=((sum+=lis[i].v)==tot)*(lis[i+1].x-lis[i].x);

		printf("%lld\n",ans>=inf/4?-1:ans);

	}

}

巴特西

【51nod 1340】地铁环线

题目

分析

最新文章

热门文章