51nod1340地铁环线

经典题。

经典差分约束模型。

但是

显然这个总长是有上下界的。

直接二分总长，判断有没有负环

如果没有负环好办，有负环就不知道怎么偏了。

因为没有单调性！

（如果所有没有单调性的函数图像，都知道往哪里走更优，

岂不是全都可以二分了

）

但是本题特殊在于，至少还是个区间！

二分左右端点。

负环记录k*mid+b的k，根据k的正负就可以知道哪个方向可能有解。

任意一个负环都可以判断的。

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

#define pb push_back

#define solid const auto &

#define enter cout<<endl

#define pii pair<int,int>

using namespace std;

// #define int long long

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);(fl==true)&&(x=-x);}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Modulo{

const int mod=;

il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}

il int sub(int x,int y){return ad(x,mod-y);}

il int mul(int x,int y){return (ll)x*y%mod;}

il void inc(int &x,int y){x=ad(x,y);}

il void inc2(int &x,int y){x=mul(x,y);}

il int qm(int x,int y=mod-){int ret=;while(y){if(y&) ret=mul(x,ret);x=mul(x,x);y>>=;}return ret;}

template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);}

template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}

}

// using namespace Modulo;

namespace Miracle{

const int N=;

const ll inf=1e9+;

int n,m1,m2;

struct node{

    int fr,nxt,to;

    int k,b;

    ll val(ll x){

        return (ll)k*x+b;

    }

}e[N*N];

int hd[N],cnt;

void add(int x,int y,int k,int b){

    // cout<<" add "<<x<<" to "<<y<<" k "<<k<<" b "<<b<<endl;

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;e[cnt].k=k;e[cnt].b=b;

    e[cnt].fr=x;

    hd[x]=cnt;

}

ll dis[N],pre[N];

int has[N];

bool vis[N];

queue<int>q;

int spfa(ll mid){

    memset(dis,0x3f,sizeof dis);

    dis[]=;

    memset(vis,,sizeof vis);

    while(!q.empty()) q.pop();

    has[]=;

    q.push();

    while(!q.empty()){

        int x=q.front();q.pop();vis[x]=;

        for(reg i=hd[x];i;i=e[i].nxt){

            int y=e[i].to;

            if(dis[y]>dis[x]+e[i].val(mid)){

                dis[y]=dis[x]+e[i].val(mid);

                pre[y]=i;

                has[y]=has[x]+;

                if(has[y]==n+){

                    int z=y;

                    memset(vis,,sizeof vis);

                    do{

                        vis[z]=;

                        z=e[pre[z]].fr;

                    }while(!vis[z]);

                    int k=;

                    int lp=z;

                    do{

                        k+=e[pre[z]].k;

                        z=e[pre[z]].fr;

                    }while(z!=lp);

                    if(k>){

                        return ;

                    }else return -;

                }

                if(!vis[y]){

                    vis[y]=;

                    q.push(y);

                }

            }

        }

    }

    return ;

}

void clear(){

    memset(hd,,sizeof hd);cnt=;

}

int main(){

    // rd(n);rd(m);

    int T;

    rd(T);

    while(T--){

        clear();

        rd(n);rd(m1);rd(m2);

        for(reg i=;i<n;++i){

            add(i,i-,,-);

        }

        add(,n-,,-);

        int a,b,c;

        for(reg i=;i<=m1;++i){

            rd(a);rd(b);rd(c);

            if(a<b){

                add(b,a,,-c);

            }else{

                add(b,a,,-c);

            }

        }

        for(reg i=;i<=m2;++i){

            rd(a);rd(b);rd(c);

            if(a<b){

                add(a,b,,c);

            }else{

                add(a,b,-,c);

            }

        }

        ll L=n,R=(ll)n*inf;

        ll al=R+;

        while(L<=R){

            ll mid=(L+R)>>;

            int lp=spfa(mid);

            if(lp==-){

                R=mid-;

            }else if(lp==){

                L=mid+;

            }else{

                al=mid;R=mid-;

            }

        }

        L=n,R=(ll)n*inf;

        ll ar=n-;

        while(L<=R){

            ll mid=(L+R)>>;

            int lp=spfa(mid);

            if(lp==-){

                R=mid-;

            }else if(lp==){

                L=mid+;

            }else{

                ar=mid;L=mid+;

            }

        }

        // cout<<" al "<<al<<" ar "<<ar<<endl;

        if(ar<al){

            puts("");

        }else if(ar==(ll)n*inf){

            puts("-1");

        }else{

            printf("%lld\n",ar-al+);

        }

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

*/

二分条件：单调性

一切可以得知最优解方向的，也都可以二分

巴特西

51nod1340地铁环线

最新文章

热门文章