题解 [51nod1340]地铁环线

题面

解析

本文参考这篇博客

一开始看到只有120行就打算写一写,

结果一刚就是三个星期摆摆摆

本来是当查分约束入门学的.

step 1

首先来考虑下如果已知总长度\(s\)如何判断是否合法.

显然差分约束

对于\(dis(x,y)>=w\)

这个式子等价于\(dis[x]+w<=dis[y]\),

即\(dis[y]+(-w)>=dis[x]\).

因此,
- 若\(x<y\),则\(y\)向\(x\)连一条边权为\(-w\)的边.
- 若\(x>y\),则\(y\)向\(x\)连一条边权为\(s-w\)的边(要绕一圈,yy一下就知道了).
对于\(dis(x,y)<=w\)

这个式子就是\(dis[x]+w>=dis[y]\).
- 若\(x<y\),则\(x\)向\(y\)连一条边权为\(w\)的边.
- 若\(x>y\),则\(x\)向\(y\)连一条边权为\(s+w\)的边.

又因为边权至少为\(1\),即\(dis[x]+1<=dis[y]\).

\(dis[y]+(-1)>=dis[x]\).

因此\(i+1\)要向\(i\)连一条边权为\(-1\)的边(n-1要特判)

最后,跑n-1边Bellman_Ford,

若还能进行松弛操作,即存在边\((x,y,w)\),使\(dis[x]+w<=dis[y]\),

则存在负环,就不合法.

step 2

差分约束还只是判断,

但我们要统计方案数啊.

注意到每个点的\(dis\)都是\(k*s+b\)的形式(\(k,b\)为常数).

因此,我们可以设\(dis[x][k]\)表示\(s\)前的系数为\(k\)时\(dis[x]\)只计算\(b\)的最小值.

那么\(dis[x]\)就等于\(\min(k*s+dis[x][k]).\)

然后,对于每一条边(x,y,w),我们都可以把\(s\)的值域化为若干段,

使每一段都是取一个\(k\)使\(s\)取这一段值时的\(dis\)值最小.

这个可以用单调栈维护.

那么我们维护两个单调栈,

一个是\(dis[x]+w\)的,一个是\(dis[y]\)的.

然后对于一段值域若\(dis[x]+w>dis[y]\)则合法.

对每条边都这么来一次,用前缀和+差分来统计这一段权值的合法边数.

若合法边数等于总边数,则这一段值域合法,统计答案.

code(代码中的inf不知道是什么情况希望dalao指点):

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define ll long long

#define int ll

using namespace std;

inline int read(){

	int sum=0,f=1;char c=getchar();

	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}

	return f*sum;

}

const int N=55;

struct list{ll x,v;}lis[N*N*N<<1];

int T,n,m1,m2,cnt,tot;

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

inline ll up(ll tb,ll tk){

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

	ll tt=tb/tk;

	return tt+(tt*tk<tb);

}/*向上取整*/

inline ll down(ll tb,ll tk){

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

	ll tt=tb/tk;

	return tt-(tt*tk>tb);

}/*向下取整*/

struct line{

	ll l,r,k,b;

	inline ll f(int x){return k*x+b;}

}s1[N*N*N<<1],s2[N*N*N<<1];

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

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

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

	a[++num]=t;

}

inline void put(ll l,ll r){

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

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

}

inline void check(line s1,line s2){

	ll l=max(s1.l,s2.l),r=min(s1.r,s2.r);

	if(l>r) return ;

	line t=(line){0,0,s1.k-s2.k,s1.b-s2.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{

	ll x,y,w,k;

	inline void bf(){

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

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

	}

	inline void clac(){

		int n1=0,n2=0;

		for(int i=(n<<1);i>=0;i--){

			if(dis[x][i]<(inf>>1)) push(s1,n1,(line){n,inf,i+k-n,dis[x][i]+w});

			if(dis[y][i]<(inf>>1)) push(s2,n2,(line){n,inf,i-n,dis[y][i]});

		}

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

			check(s1[k1],s2[k2]);

	}

}e[N<<2];

inline void add(ll x,ll y,ll w,ll k){

	e[++cnt]=(edge){x,y,w,k};

}

inline bool cmp(list a,list b){return a.x<b.x;}

signed main(){

	T=read();

	while(T--){

		n=read(),m1=read(),m2=read();

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

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

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

		cnt=tot=0;

		for(int i=0;i<n;i++) add((i+1)%n,i,-1,i==n-1);

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

			int x=read(),y=read(),w=read();

			add(y,x,-w,(x>y));

		}

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

			int x=read(),y=read(),w=read();

			add(x,y,w,-(x>y));

		}

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

			for(int j=1;j<=cnt;j++) e[j].bf();

		for(int i=1;i<=cnt;i++) e[i].clac();

		ll sum=0,ans=0;

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

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

		for(int i=1;i<tot;i++){

			ans+=((sum+=lis[i].v)==cnt)*(lis[i+1].x-lis[i].x);

		}

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

	}

	return 0;

}

巴特西

题解 [51nod1340]地铁环线