洛谷4926 [1007]倍杀测量者

题意

有 $n(\le 1000)$ 个人，每个人有分数 $s[i]$ 。有 $S$ 组限制 $(A,B)$ ，要求 $s[A] > s[B]\times k$ 或 $s[A] > s[B]\times \frac{1}{k}$ ，如果不满足则 $A$ 需要女装。已知 $t$ 个人的初始分数。

求最大的 $T$ ，使得限制变为 $s[A] > s[B]\times (k-T)$ 或 $s[A] > s[B]\times \frac{1}{k+T}$ 后，仍然有人女装。

题解

如果 $T$ 有人女装，那么 $\le T$ 时都有人女装，所以满足单调性，可以二分答案。

考虑把加法变为乘法的差分约束，令 $k'$ 为改变后的 $k$ ，如果 $s[A] > s[B]\times k'$ 就连一条 $(B,A,k')$ 的边。如果 $s[i]$ 有初值就连 $(0,i,s[i])$ 和 $(i,0,\frac{1}{s[i]})$ 。

这样的话所有点的初值为 $1$ ，然后跑最长路，判断是否有正环即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

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

const int N=1005;
struct Edge {
    int next,to;
    double w;
} edge[N<<3];
struct node {
    int o,x,y,k;
} s[N];
bool vis[N];
double dis[N];
int cnt,head[N],n,m,k,a,b,c,d,scr[N];

inline void init()
{
    cnt=0;
    memset(head,0,sizeof(head));
    for (int i=0;i<=n;i++) dis[i]=1; //初值为1
}

inline void add(int u,int v,double w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

bool spfa(int x)
{
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to; double w=edge[i].w;
        if (dis[x]*w>dis[y])
        {
            dis[y]=dis[x]*w;
            if (vis[y] || !spfa(y)) return vis[x]=0,0;
        }
    }
    return vis[x]=0,1;
}

inline bool check(double t)
{
    init();
    for (int i=1;i<=n;i++)
    {
        if (!scr[i]) continue;
        add(0,i,scr[i]);
        add(i,0,1.0/scr[i]);
    }
    for (int i=1;i<=m;i++)
    {
        if (s[i].o==1) add(s[i].y,s[i].x,s[i].k-t);
        else add(s[i].y,s[i].x,1.0/(s[i].k+t));
    }
    for (int i=0;i<=n;i++) if (!spfa(i)) return 1;
    return 0;
}

signed main()
{
    n=read(); m=read(); k=read();
    double l=0,r=1e9;
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read(); d=read();
        s[i]=(node){a,b,c,d};
        if (a==1) r=min(r,1.0*d);
    }
    for (int i=1;i<=k;i++) a=read(),scr[a]=read();
    for (int i=1;i<=100;i++)
    {
        double mid=(l+r)/2;
        if (check(mid)) l=mid;
        else r=mid;
    }
    if (!check(l)) return 0&puts("-1"); //无解
    return !printf("%.10f",l);
}