【2018/11/05测试T1】列队

【题目】

传送门

【分析】

这道题好像有很多种解法，我用的是差分约束

将题目条件转换一下，$x_r-x_l=d\Rightarrow \begin{cases}x_r-x_l\ge d\\x_r-x_l\le d\end{cases}\Rightarrow\begin{cases}x_r-x_l\ge d\\x_l-x_r\ge -d\end{cases}$xr​−xl​=d⇒{xr​−xl​≥dxr​−xl​≤d​⇒{xr​−xl​≥dxl​−xr​≥−d​

由于是求最小值，我们建完边后跑最长路就行了

代码中从 $0$0 向每个点连权值为 $0$0 的边的作用是把整张图联通

【代码】

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define M 500005
#define inf 1ll<<30ll
using namespace std;
int n,m,t,flag;
int d[N],cnt[N];
int first[N],v[M],w[M],nxt[M];
bool vis[N];
void add(int x,int y,int z)
{
	t++;
	nxt[t]=first[x];
	first[x]=t;
	v[t]=y;
	w[t]=z;
}
void spfa(int s)
{
	int x,y,i;
	memset(d,128,sizeof(d));
	queue<int>q;q.push(s);d[s]=0;
	while(!q.empty())
	{
		x=q.front();q.pop();
		vis[x]=false;
		for(i=first[x];i;i=nxt[i])
		{
			y=v[i];
			if(d[y]<d[x]+w[i])
			{
				d[y]=d[x]+w[i];
				cnt[y]=cnt[x]+1;
				if(cnt[y]>n)  {flag=1;return;}
				if(!vis[y])  {q.push(y);vis[y]=true;}
			}
		}
	}
}
int main()
{
//	freopen("line.in","r",stdin);
//	freopen("line.out","w",stdout);
	int l,r,i,x;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&l,&r,&x);
		add(l,r,x),add(r,l,-x);
	}
	for(i=1;i<=n;++i)
	  add(0,i,0);
	spfa(0);
	int Min=inf,Max=-inf;
	for(i=1;i<=n;++i)
	{
		Min=min(Min,d[i]);
		Max=max(Max,d[i]);
	}
	if(flag)  printf("impossible");
	else  printf("%d",Max-Min);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}