http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1340
设x为环线的长度，要判断某个特定的x是否可行，不难将题目转为差分约束模型，用最短路求解，每个限制条件对应图中一条边，可行当且仅当图中没有负环。
如果x是整数，用最短路可以构造出整数解，因此现在需要对所有x同时判断，求出x的可行域，再求整数解个数。
由于边权是关于x的一次函数，且一次项系数绝对值<=1，可以用Bellman-Ford算法处理，此时一个点w到源点的距离dist(w)被表示为关于x的函数dist(w,x)，且这个函数可以表示为一系列一次函数取min。最后判负环的时候相当于求 对每条长度为e(w,u)的边w->u都满足dist(w,x)+e(w,u)-dist(u,x)>=0 的 x的取值范围。
时间复杂度O(Tn^2m)。
#include<bits/stdc++.h>
typedef long long i64;
const i64 inf=1ll<<;
int T,n,m1,m2,ep;
i64 l[][];
void mins(i64&a,i64 b){if(a>b)a=b;}
i64 up(i64 A,i64 B){
if(B<)B=-B,A=-A;
i64 C=A/B;
return C+(C*B<A);
}
i64 dn(i64 A,i64 B){
if(B<)B=-B,A=-A;
i64 C=A/B;
return C-(C*B>A);
}
struct pos{
i64 x;
int y;
bool operator<(const pos&w)const{return x<w.x;}
}ps[];
int pp;
void ins(i64 L,i64 R){
ps[pp++]=(pos){L,};
ps[pp++]=(pos){R+,-};
}
struct ln{
i64 k,b,l,r;
i64 at(i64 x){
return k*x+b;
}
void chk(ln w){
i64 L=std::max(l,w.l),R=std::min(r,w.r);
if(L>R)return;
w.k=k-w.k;
w.b=b-w.b;
if(w.at(L)>=){
if(w.at(R)>=)ins(L,R);
else ins(L,dn(-w.b,w.k));
}else if(w.at(R)>=)ins(up(-w.b,w.k),R);
}
bool cmp(ln&w){
return at(l)>=w.at(l);
}
void cut(ln&w){
i64 K=k-w.k,B=b-w.b;
r=dn(-B,K);
w.l=r+;
}
}v1[],v2[];
void push(ln*a,int&ap,ln w){
for(;ap&&a[ap].cmp(w);--ap);
if(ap)a[ap].cut(w);
a[++ap]=w;
}
struct edge{
int x,y,a,b;
void upd(){
for(int i=;i<=n*;++i)if(i+b>=&&i+b<=n*)mins(l[y][i+b],l[x][i]+a);
}
void chk(){
int p1=,p2=;
for(int i=n*;i>=;--i){
if(l[x][i]<inf/)push(v1,p1,(ln){i-n+b,l[x][i]+a,n,inf});
if(l[y][i]<inf/)push(v2,p2,(ln){i-n,l[y][i],n,inf});
}
int i1=,i2=;
while(i1<=p1&&i2<=p2){
v1[i1].chk(v2[i2]);
if(v1[i1].r<=v2[i2].r)++i1;else ++i2;
}
}
}e[];
void ae(int a,int b,int d,int k){
e[ep++]=(edge){a,b,d,k};
}
int main(){
for(scanf("%d",&T);T;--T){
scanf("%d%d%d",&n,&m1,&m2);
ep=;
for(int i=;i<n;++i){
for(int j=;j<=n*;++j)l[i][j]=inf;
}
l[][n]=;
for(int i=;i<n;++i){
int a=i,b=(i+)%n,d=;
ae(b,a,-d,(a>b));
}
for(int i=,a,b,d;i<=m1;++i){
scanf("%d%d%d",&a,&b,&d);
ae(b,a,-d,(a>b));
}
for(int i=,a,b,d;i<=m2;++i){
scanf("%d%d%d",&a,&b,&d);
ae(a,b,d,-(a>b));
}
for(int t=;t<n;++t){
for(int i=;i<ep;++i)e[i].upd();
}
pp=;
for(int i=;i<ep;++i)e[i].chk();
std::sort(ps,ps+pp);
i64 ans=;
for(int i=,s=;i<pp;++i){
s+=ps[i].y;
if(s==ep)ans+=ps[i+].x-ps[i].x;
}
if(ans>inf/)ans=-;
printf("%lld\n",ans);
}
return ;
}