差分约束：P4926 [1007] 倍杀测量者

· · 题解

差分约束算法本质是将不等式与最短路的三角不等式 dis_v\le dis_u+w（最短路）和 dis_v\ge dis_u+w（最长路）联系起来，

这种情况下不等式组无解对应的是图存在负环 / 正环，故一般用 Spfa 解决。

题目大意

给定若干形如 P_{a_i}\ge (k_i-t)P_{b_i} 或 (k_i+t)P_{a_i}> P_{b_i} 的式子，找出最大的实数 t，使得不等式组无解，若找不到，输出 -1。

注意有若干 P_i 已知，形如 P_C=x。

思路分析

看到若干不等式组首先想到差分约束，考虑建模。

题目的限制与朴素的差分约束式子略有不同，可以跑倍率最短路，也可以用常规套路，式子两边同时取对数：

\left\{\begin{aligned}\log_2P_{a_i}\ge \log_2{P_{b_i}}+\log_2{(k_i-t)} \\\log_2P_{a_i}>\log_2P_{b_i}-\log_2(k_i+t) \end{aligned}\right.

由于允许精度误差，所以上式的 > 可以默认成 \ge​。

对于已知的 P_i，考虑钦定 n+1 为零势能点，有 \log_2P_i=\log_2P_{n+1}+\log_2x，相当于同时满足 \log_2P_i\le \log_2P_{n+1}+\log_2x 和 \log_2P_i\ge \log_2P_{n+1}+\log_2x，建两条边即可。

定义 dis_i=\log_2P_i，二分 t 的大小跑最长路即可，最长路有正环说明合法。

答案无解情况：不需要考虑 t<0 的情况，若 t=0 不等式组仍成立说明答案无解。 但是你会发现题解区里没人写任何简易证明。

当 t<0 时，原式

\left\{\begin{aligned}\log_2P_{a_i}\ge \log_2{P_{b_i}}+\log_2{(k_i-t)} \\\log_2P_{a_i}>\log_2P_{b_i}-\log_2(k_i+t) \end{aligned}\right.

不等号右侧均单增，P_{a_i} 可取的范围变小，所以 t=0 无解时 t<0 必无解，反过来，若 t<0 有解，则 t=0 必有解，而我们要求 t 的最大值，所以 t<0 永远不会产生贡献。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e3+5;
const double eps=1e-6;
int n,s,t,p[N];
struct qh{
    int v,nt,ty;
    double w;
}E[N<<2];
void add(int u,int v,double w,int ty){E[++p[0]]=(qh){v,p[u],ty,w};p[u]=p[0];return ;}
bool Spfa(double t){  //Spfa check a minus loop: have a minimum path whose length > n
    queue<int> q;
    double dis[N];int bz[N],vis[N];
    rep(i,1,n) dis[i]=-1e18,bz[i]=vis[i]=0;
    q.push(n);bz[n]=1;dis[n]=0;
    while (q.size()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=p[u];i;i=E[i].nt){
            int v=E[i].v,ty=E[i].ty;double w=E[i].w;
            if(ty==1) w=log2(w-t);
            if(ty==2) w=-log2(w+t);
            if(dis[v]<dis[u]+w){
                dis[v]=dis[u]+w;
                bz[v]=bz[u]+1;
                if(bz[v]==n+2) return 1;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&s,&t);n++;
    double l=0,r=10,ans=0;
    rep(i,1,s){
        int o,a,b;double k;scanf("%d%d%d%lf",&o,&a,&b,&k);
        add(b,a,k,o);if(o==1) r=fmin(r,k);
    }
    rep(i,1,t){
        int c;double x;scanf("%d%lf",&c,&x);
        add(n,c,log2(x),0);add(c,n,-log2(x),0);
    }
    if(!Spfa(0)) return puts("-1"),0;
    while (l+eps<=r){
        double mid=(l+r)/2.0;
        if(Spfa(mid)) ans=l,l=mid+eps;
        else r=mid-eps;
    }
    printf("%.8f",ans);
    return 0;
}
/*
start coding:15:45
finish debuging:16:07
*/