题解 P4926 【[1007]倍杀测量者】

2018-10-20 16:28:40


题意

某地信息组流行女装。

一场考试后,一些骄傲的大佬和一些暴躁的蒟蒻达成约定:

如果某选手不满足以下限制条件,他将会被强迫女装

  • $s[A]>s[B]*k_i$
  • $s[A]>s[B]*\frac{1}{k_i}$

其中$s[A]$表示选手A的分数。同时你还已知一些选手的分数

请你求出最大的正实数$T$,使得限制条件变成下面的形式后,仍然有人女装

  • $s[A]>s[B]*(k_i-T)$
  • $s[A]>s[B]*\frac{1}{(k_i+T)}$

数据范围:限制数$\le1000$,$1\le k\le10$且为整数,已知选手的分数不超过$10^9$

题解

转化题意之后,就可以二分答案T了

对限制条件进行差分约束连边

  • 对于$s[A]>s[B]*k_i$,从$B$向$A$连一条权值为$k_i$的边
  • 对于$s[A]=x$,默认$s[0]=1$,从$0$向$A$连$x$,从$A$向$0$连$\frac{1}{x}$

对此图跑乘积最长路即可,如果存在环,则合法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=1100;
struct flag{int o,a,b,k;}fl[N];
struct edge{int next,to;double w;}a[N<<1];
int n,s,t,c[N],fr[N],head[N],cnt,vis[N];
double dis[N];queue<int> Q;
void link(int x,int y,double w){a[++cnt]=(edge){head[x],y,w};head[x]=cnt;}
int check(double T)
{
    memset(head,0,sizeof(head));
    memset(fr,0,sizeof(fr));cnt=0;
    while(!Q.empty()) Q.pop();
    for(int i=0;i<=n;i++) dis[i]=1,fr[i]=0,vis[i]=1,Q.push(i);  
    for(int i=1;i<=n;i++)
        if(c[i]) link(i,0,1.0/c[i]),link(0,i,c[i]);
    for(int i=1;i<=s;i++)
    {
        int A=fl[i].a,B=fl[i].b,k=fl[i].k,o=fl[i].o;
        if(o==1) link(B,A,k-T);
        else link(B,A,1.0/(k+T));
    }
    while(!Q.empty())
    {
        int x=Q.front();
        for(int i=head[x];i;i=a[i].next)
        {
            int R=a[i].to;
            if(dis[R]>=dis[x]*a[i].w) continue;
            dis[R]=dis[x]*a[i].w;fr[R]=fr[x]+1;
            if(fr[R]==n+2) return 1;
            if(!vis[R]) Q.push(R),vis[R]=1;
        }
        Q.pop();vis[x]=0;
    }
    return 0;
}
int main()
{
    cin>>n>>s>>t;
    double l=0,r=1e18,T=-1;
    for(int i=1;i<=s;i++)
    {
        int o,a,b,k;cin>>o>>a>>b>>k;
        fl[i]=(flag){o,a,b,k};
        if(o==1) r=min(r,(double)k-1e-8);
    }
    for(int i=1,C,x;i<=t;i++) cin>>C>>x,c[C]=x;
    while(r-l>1e-8)
    {
        double mid=(l+r)/2;
        check(mid)?l=T=mid:r=mid;
    }
    T==-1?puts("-1"):printf("%.10lf\n",T);
}

广告:https://www.cnblogs.com/xzyxzy

至今有些不明白的是,如果取倒数之后连边跑最短路、或者取对数后再做 会WA。如果有用该方法过了的同学,可以私信我一起讨论QAQ

感谢究极龙骑士:之前不能过的原因是上界有错,而且在连边之前没有判断是否已经合法,以及在跑SPFA时n+1个点应该是n+2长度的最短路才有正环。

现在已经用最短路+取对数AC本题:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#define float double
using namespace std;
const int N=1100;
struct flag{int o,a,b,k;}fl[N];
struct edge{int next,to,tag;float w;}a[N<<1];
int n,s,t,c[N],fr[N],head[N],cnt,vis[N],gt[N];
float dis[N];queue<int> Q;
void link(int x,int y,int tag,float w)
{a[++cnt]=(edge){head[x],y,tag,log2(w)};head[x]=cnt;}
int check(float T)
{
    memset(head,0,sizeof(head));
    memset(fr,0,sizeof(fr));cnt=0;
    while(!Q.empty()) Q.pop();
    for(int i=1;i<=n;i++)
        if(c[i]) link(i,0,1,c[i]),link(0,i,0,c[i]);
    for(int i=1;i<=s;i++)
    {
        int A=fl[i].a,B=fl[i].b,k=fl[i].k,o=fl[i].o;
        if(c[A]&&c[B]&&((o==1&&c[A]<c[B]*(k-T))||
                        (o==2&&c[A]*(k+T)<c[B]))) return 1;
        if(o==1) link(A,B,1,k-T);
        else link(A,B,0,k+T);
    }
    for(int i=0;i<=n;i++) dis[i]=0,fr[i]=0,Q.push(i),vis[i]=1;
    while(!Q.empty())
    {
        int x=Q.front();
        for(int i=head[x];i;i=a[i].next)
        {
            int R=a[i].to;
            float w=a[i].tag?dis[x]-a[i].w:dis[x]+a[i].w;
            if(dis[R]<=w&&dis[R]!=-1) continue;
            dis[R]=w;fr[R]=fr[x]+1;
            if(fr[R]==n+2) return 1;
            if(!vis[R]) Q.push(R),vis[R]=1;
        }
        Q.pop();vis[x]=0;
    }
    return 0;
}
int main()
{
    cin>>n>>s>>t;
    float l=0,r=1e18,T=-1;
    for(int i=1;i<=s;i++)
    {
        int o,a,b,k;cin>>o>>a>>b>>k;
        fl[i]=(flag){o,a,b,k};
        if(o==1) r=min(r,(float)k-1e-8);
    }
    for(int i=1,C,x;i<=t;i++) cin>>C>>x,c[C]=x;
    while(r-l>1e-6)
    {
        float mid=(l+r)/2.0;
        check(mid)?l=T=mid:r=mid;
    }
    T==-1?puts("-1"):printf("%.10f\n",(double)T);
}

(题解有更新,烦请管理员再次通过)