P4926 倍杀测量者

比例约束取对数后判矛盾

问题

P4926 [1007] 倍杀测量者
给出 $n$ 名选手之间若干条“倍杀关系”和部分选手的确定分数。每条关系都可以通过参数 $T$ 进行一定程度的放宽，要求最大的 $T$，使得无论怎样设置其余选手的分数，都至少会有一个 Flag 被兑现。

数据规模：$n,s\le1000$，$t\le n$，倍率 $k\le10$，已知分数不超过 $10^9$。

题意有点绕，翻译一下就是：对于 $A$ k 倍杀 $B$，若 $P_{A} \ge kP_{B}$，则记为符合，若 $P_{A} \ge (k - T) P_{B}$，则记为不符合。

现要求在原图上调整参数 $T$，使得至少存在一个人符合的最大参数 $T$。

所以我们可以直接按不符合的限制条件来建图，然后二分答案 $T$，跑一遍差分约束来 check，如果存在负环，就说明不符合的条件中有矛盾，也就说存在一个人是符合的，那当前的参数 $T$ 就是满足题目要求的。

接着处理这两个不等式子 $o = 1,\ P_{A} \ge (k - T)P_{B}$，$o = 2,\ P_{B} < (k + T)P_{A}$。

由于式子里面带了乘法，而标准的差分约束通常用于处理加法运算，所以这里可以将不等式两边同时取一个对数，记 $x_{i} = \log(P_{i})$，即 $x_{A} \ge \log(k - T) + X_{B}$，$x_{B} < \log(k + T) + x_{A}$。

前者连接 $A \to B$ 权值为 $-\log(k - T)$，后者连接 $A \to B$ 权值为 $\log(k + T)$。

对于给定 $P_{c} = x$，使用虚拟源点 $0$ 连接 $0 \to C$，权值为 $\log(x)$，以及 $C \to 0$，权值为 $-\log(x)$。

最后验证一下二分的单调性，随着 $T$ 的增大，约束只会放松，所以出现负环的概率会减小，因此 ”仍然存在负环“ 具有单调性。

▶

P4926

struct Edge { int v; double w; };
vector<Edge> base[maxn];
vector<Edge> adj[maxn];

double dis[maxn];
int cnt[maxn];
bool inq[maxn];

bool spfa( int V ) {
    queue<int> q;
    for( int i = 0; i < V; ++ i ) {
        dis[i] = 0, cnt[i] = 0, inq[i] = 1;
        q.push( i );
    }
    while( !q.empty( ) ) {
        int u = q.front( ); q.pop( );
        inq[u] = false;
        for( auto [v, w] : adj[u] ) {
            if( dis[u] == inf ) continue;
            if( dis[u] + w < dis[v] ) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if( cnt[v] >= V ) return true;
                if( !inq[v] ) inq[v] = true, q.push( v );
            }
        }
    }
    return false;
}

struct AllEdge { int o, a, b, k; };
vector<AllEdge> edges;

bool check( int N, double T ) {
    for( int i = 0; i <= N; ++ i ) adj[i] = base[i];
    for( auto [o, a, b, k] : edges ) {
        if( o == 1 ) {
            if( k - T <= 0 ) continue;
            adj[a].push_back({ b, -log10( k - T ) });
        }
        else {
            adj[a].push_back({ b, log10( k + T ) });
        }
    }
    return spfa( N + 1 );
}

void solve( ) {
    int n = read( ), s = read( ), t = read( );

    for( int i = 1; i <= s; ++ i ) {
        int o = read( ), a = read( ), b = read( ), k = read( );
        edges.push_back({ o, a, b, k });
    }

    for( int i = 1; i <= t; ++ i ) {
        int c = read( ), xi = read( );
        base[0].push_back({ c, log10( xi ) });
        base[c].push_back({ 0, -log10( xi ) });
    }

    if( !check( n, 0 ) ) {
        cout << -1 << '\n';
        return;
    }

    double l = 0, r = 1e9, ans = -1;
    for( int t = 1; t <= 100; ++ t ) {
        double mid = ( l + r ) / 2.0;
        if( check( n, mid ) ) ans = mid, l = mid;
        else r = mid;
    }
    cout << fixed << setprecision( 10 ) << ans << '\n';
}