2018-10-20 16:28:40

# 题意

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

• $s[A]>s[B]*(k_i-T)$
• $s[A]>s[B]*\frac{1}{(k_i+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];
double dis[N];queue<int> Q;
int check(double T)
{
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++)
for(int i=1;i<=s;i++)
{
int A=fl[i].a,B=fl[i].b,k=fl[i].k,o=fl[i].o;
}
while(!Q.empty())
{
int x=Q.front();
{
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);
}

#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];
float dis[N];queue<int> Q;
void link(int x,int y,int tag,float w)
int check(float T)
{
memset(fr,0,sizeof(fr));cnt=0;
while(!Q.empty()) Q.pop();
for(int i=1;i<=n;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;
}
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();
{
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);
}

（题解有更新，烦请管理员再次通过）

• star
首页