[Luogu P4926] 倍杀测量者

Luogu P4926

思路

为了求什么加上一个$T$值使方案可行还要$T$值最大,一看就是二分答案了

至于什么值的大小关系,很显然是差分约束

$o=1$时,$B$向$A$连权值为$k$的边

$o=2$时,$B$向$A$连权值为$\frac{1}{k}$的边

对于分数为$x$的$C$,从$0$向$C$连$x$,从$C$向$0$连$\frac{1}{x}$

这样的话,如果有解,就没有人可以女装

有解当且仅当有正环

找正环跑Bellman-Ford就可以了

代码

#include <iostream>
#include <cstdio>

struct Data{
    int A, B, o;
    double K;
}a[3010];

const double esp=1e-8;
int n, s, t;

bool check(double T){
    double dis[1010], tmp[1010]; int cnt[1010];
    tmp[0]=dis[0]=1; cnt[0]=0;
    for(int i=1; i<=n; i++) tmp[i]=0, dis[i]=0, cnt[i]=0;
    while(1){
        for(int i=1; i<=s+2*t; i++){
            int x=a[i].B, y=a[i].A; double z;
            if(a[i].o==1) z=a[i].K-T;
            if(a[i].o==2) z=1/(a[i].K+T);
            if(a[i].o==3) z=a[i].K;
            tmp[y]=std::max(tmp[y], dis[x]*z);
        }
        bool fl=true;
        for(int i=0; i<=n; i++) if(tmp[i]>dis[i]){
            cnt[i]++; dis[i]=tmp[i]; fl=false;
            if(cnt[i]>n-1) return true;
        }
        if(fl) return false;
    }
}

int main(){
    int o; double x;
    scanf("%d%d%d", &n, &s, &t);
    for(int i=1; i<=s; i++)
        scanf("%d%d%d%lf", &a[i].o, &a[i].A, &a[i].B, &a[i].K);
    for(int i=1; i<=t; i++){
        scanf("%d%lf", &o, &x);
        a[s+2*i-1].A=o, a[s+2*i-1].B=0, a[s+2*i-1].K=x;
        a[s+2*i].B=o,   a[s+2*i].A=0,   a[s+2*i].K=1/x;
        a[s+2*i-1].o=a[s+2*i].o=3;
    }
    double l=esp, r=1000, ans=-1;
    while(r-l>-esp){
        double mid=(l+r)/2;
        if(check(mid))	ans=mid, l=mid+esp;
        else			r=mid-esp;
    }
    printf("%lf", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注