[题解] 51 nod 1340 地铁环线

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

但是如果想按照通常的题目那样去建边的话，就会发现这句话——相邻两站的距离至少是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 为啥没了，也不敢问

巴特西

[题解] 51 nod 1340 地铁环线

最新文章

热门文章