题解 P4926 【[1007]倍杀测量者】
xzyxzy
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}$
对此图跑乘积最长路即可，如果存在环，则合法
```cpp
#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本题：
```cpp
#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);
}
```
（题解有更新，烦请管理员再次通过）