P4926题解

· · 题解

题目分析

题中所述，一个选手不需要女装的条件为「A 成功 k-T 倍杀 B」和「A 没有成功被 B k+T 倍杀」。

令 s[A] 为选手 A 的得分，条件为 s[A] \ge s[B] \times (k-T) 和 s[A] \ge s[B] \times \dfrac{1}{k+T}。

由于需要有选手女装，我们需要找到最大的 T 使不等式组无解。我们可以通过差分约束实现判断不等式组是否有解，二分寻找最大的 T。

不过，我们在跑差分约束之前可以先把不等式两边同时取 log，将其变为加减法。两个不等式分别转换为 \log_2(s[A]) - \log_2(s[B]) \ge \log_2(k-T) 和 \log_2(s[A]) - \log_2(s[B]) \ge - \log_2(k+T)。

实现

连边

我们需要储存边的种类、选手得分（若已知）、倍杀中的 k，在差分约束中根据边的种类计算出边权。

两种 flag 所对应的边权即为两个不等式的右项。若没有发生倍杀（即因为已知得分连边），直接将边权定为选手得分。

已知得分

我们再创造一个超级原点，将已知得分的选手与这个点连边（两条，一正一负，同上文所述不等式）。预先将其进行 \log_2 的运算。

有无解

若差分约束中出现负环说明此不等式组无解，符合题目要求。将二分中的 l=mid。否则将 r=mid。

若 T 为 0 时不等式组仍成立，则题目无解。

具体实现

（代码中注释应该很详细了，有注释版本正好一百行。）

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=w*10+ch-48;
        ch=getchar();
    }
    return w*f;
}

#define MAXN 1005

int n,s,t;
double l,r=10.0;

struct node{
    int v,nxt;
    int op;//边类型 
    double w,k;//已知得分，倍杀 
}e[MAXN*4];
int cnt=0,head[MAXN];
void build(int op,int u,int v,double w,double k){
    e[++cnt].op=op,e[cnt].v=v;
    e[cnt].w=w,e[cnt].k=k;
    e[cnt].nxt=head[u],head[u]=cnt;
}
//建图
//五个参数分别为 边的类型（倍杀还是被倍杀），边的起点，边的终点 
//选手得分（若已知，否则为0），倍杀的 k 

double dis[MAXN];
int inq[MAXN],c[MAXN];

bool spfa(double t){
    queue<int>q;
    for(int i=0;i<=n;i++)dis[i]=-1e9,c[i]=0,inq[i]=0;
    //记得清空数组
    dis[n+1]=0,inq[n+1]=1,c[n+1]++;
    q.push(n+1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            double w=e[i].w;//选手已知的得分 
            if(e[i].op==1)w=log2(e[i].k-t);//若为第一种 flag 
            if(e[i].op==2)w=-log2(e[i].k+t);//第二种 flag 
            if(dis[v]<dis[u]+w){//正常的跑差分约束 
                dis[v]=dis[u]+w;
                if(!inq[v]){
                    inq[v]=1,c[v]++;
                    q.push(v);
                    if(c[v]>=n+1)return 0;//不等式组无解 
                    //由于有两个超级原点，一个点入队大于等于 n+1 次才可判断无解 
                }
            }
        }
    }
    return 1;//不等式组有解 
}

int main(){
    n=read(),s=read(),t=read();
    for(int i=1;i<=s;i++){
        int op=read(),a=read(),b=read(),k=read();
        build(op,b,a,0,k);//倍杀
        if(op==1)r=(double)fmin(r,(double)k);//二分的上界 
    }
    for(int i=1;i<=t;i++){//已知选手得分 
        int c=read();
        double x=(double)read();
        build(0,0,c,log2(x),0);
        build(0,c,0,-log2(x),0);
        //连两条边到超级原点 
    }
    for(int i=0;i<=n;i++)build(0,n+1,i,0,0);
    //另一个超级原点保证图的连通 

    if(spfa(0)){
        printf("-1");
        return 0;
    }//T=0 时仍有解，说明题目无解 

    while(r-l>1e-5){//由于精度要求不高，无需使用相减判断 
        double mid=(r+l)/2.0;
        if(spfa(mid))r=mid;
        else l=mid;
    }//二分找到答案 

    printf("%lf",l);
    return 0;
}

后记

注意事项

后记的后记

若发现错误请私信我（毕竟我太菜了，难免出错）。

这道题我断断续续调了差不多一个多月，算是第一道紫题（也是第一篇紫题题解）。