【差分约束系统+单调栈】51Nod1340 地铁环线

【题目】
51Nod
有一幅$n$个点的环图，其中第$i$个点和第$(i+1)\text{ mod }n$之间有一条有向带权边（至少为$1$）。
有$m_1+m_2$条信息限制两点之间的距离大于或小于某个值。
求有多少种不同的可能环长，若有无数种输出$-1$

【解题思路】
差分约束系统，不会做。

不妨先考虑当总长度$s$固定时如何判断有解，这是一个经典问题：
对于限制$dis(u,v)\ge d$，若$u<v$，连边$(v,u,-d)$，否则连边$(u,v,s-d)$
对于限制$dis(u,v)\le d$，若$u<v$，连边$(u,v,d)$，否则连边$(u,v,-s+d)$
然后判断是否有负环即可。

现在要求方案数，然而我并不会。

发现每条边的边权是一个一次函数，进行$n-1$次松弛操作，于是对于每个点的每种$s$的系数k记录$di{s}_{x,k}$，表示当走到$x$时，$s$的系数为$k$的最小值为$di{s}_{x,k}$

对于每一条边$(u,v)$维护一个单调栈，表示每一段$s$的值域是由$s$的哪个系数控制

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

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

每组数据复杂度$O(n^{2}m)$

【参考代码】（抄的）

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=55,M=N*N*N*2,mod=1e9+7;
int T,n,m1,m2,tot,num;
ll inf,dis[N][N<<1];

ll read()
{
	ll ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
	return ret;
}

struct lis
{
	ll x,v;
	lis(ll _x=0,ll _v=0):x(_x),v(_v){}
	bool operator <(const lis&rhs){return x<rhs.x;}
}vec[M];

struct line
{
	ll l,r,k,b;
	line(ll _l=0,ll _r=0,ll _k=0,ll _b=0):l(_l),r(_r),k(_k),b(_b){}
	ll f(ll x){return k*x+b;}
}s1[M],t1[M];

ll up(ll b,ll k)
{
	if(k<0) k=-k,b=-b;
	ll t=b/k; return t+(t*k<b);
}
ll down(ll b,ll k)
{
	if(k<0) k=-k,b=-b;
	ll t=b/k; return t-(t*k>b);
}
void push(line *a,int &cnt,line t)
{
	while(cnt && t.f(a[cnt].l)<=a[cnt].f(a[cnt].l)) --cnt;
	if(cnt) t.l=down(-(a[cnt].b-t.b),a[cnt].k-t.k)+1,a[cnt].r=t.l-1;
	a[++cnt]=t;
}
void insert(ll l,ll r)
{
	vec[++num]=lis(l,1);
	vec[++num]=lis(r+1,-1);
}
void check(line s1,line t1)
{
	ll l=max(s1.l,t1.l),r=min(s1.r,t1.r);
	if(l>r) return;
	line t=line(0,0,s1.k-t1.k,s1.b-t1.b);
	if(t.f(l)<0 && t.f(r)<0) return;
	insert(t.f(l)>=0?l:up(-t.b,t.k),t.f(r)>=0?r:down(-t.b,t.k));
}

struct edge
{
	ll x,y,v,k;
	edge(ll _x=0,ll _y=0,ll _v=0,ll _k=0):x(_x),y(_y),v(_v),k(_k){}
	void brute()
	{
		for(int i=1;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 a=0,b=0;
		for(int i=2*n;i;--i)
		{
			if(dis[x][i]<inf/2) push(s1,a,line(n,inf,i+k-n,dis[x][i]+v));
			if(dis[y][i]<inf/2) push(t1,b,line(n,inf,i-n,dis[y][i]));
		}
		for(int k1=1,k2=1;k1<=a && k2<=b;s1[k1].r<=t1[k2].r?k1++:k2++) check(s1[k1],t1[k2]);
	}
}e[N<<2];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("51Nod1340.in","r",stdin);
	freopen("51Nod1340.out","w",stdout);
#endif
	for(int T=read();T--;)
	{
		n=read();m1=read();m2=read();memset(dis,1,sizeof(dis));memset(vec,0,sizeof(vec));
		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);
		for(int i=1;i<=m1;++i)
		{
			ll x=read(),y=read(),w=read();
			e[++tot]=edge(y,x,-w,(x>y));
		}
		for(int i=1;i<=m2;++i)
		{
			ll x=read(),y=read(),w=read();
			e[++tot]=edge(x,y,w,-(x>y));
		}
		//for(int i=1;i<=tot;++i) printf("%lld %lld %lld %lldn",e[i].x,e[i].y,e[i].v,e[i].k);
		for(int i=1;i<n;++i) for(int j=1;j<=tot;++j) e[j].brute();
		for(int i=1;i<=tot;++i) e[i].calc();
		sort(vec+1,vec+num+1);vec[num+1]=lis(inf+1,0);
		ll sum=0,ans=0;
		//for(int i=1;i<=num;++i) printf("%lld %lldn",vec[i].x,vec[i].v);
		for(int i=1;i<=num;++i) ans+=((sum+=vec[i].v)==tot)*(vec[i+1].x-vec[i].x);
		printf("%lldn",ans>=inf/4?-1:ans);
	}
	return 0;
}

最后

以上就是顺利钢铁侠为你收集整理的【差分约束系统+单调栈】51Nod1340 地铁环线的全部内容，希望文章能够帮你解决【差分约束系统+单调栈】51Nod1340 地铁环线所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。