题解 [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;
}