和倍数有关的差分约束

P4926 [1007]倍杀测量者


差分约束中，只能表示大于，小于，等于三种关系，不包含倍数这种关系。
所以需要对倍数进行合理的转换，也就是进行log化处理，这样就可以把倍
数变成数值的差值

//对于相等以及不需要转化的关系，我们可以设立一个变量为边的种类
//这样会减少许多运算量
#include <bits/stdc++.h>
using namespace std;
const int M=5005;
const double eps=1e-4;

int h[M],ne[M],e[M],type[M],tot;
double w[M];
void add(int from,int to,double wi,int typ) {
    e[++tot]=to;
    ne[tot]=h[from];
    w[tot]=wi;
    type[tot]=typ;
    h[from]=tot;
}

int n,m,t;
int cnt[M];
double dis[M];
bool vis[M];

bool spfa(double x) {
    for(int i=0;i<=n+1;i++)
        dis[i]=-1e9,cnt[i]=vis[i]=0;
    queue<int>q;
    dis[0]=0;
    q.push(0);
    vis[0]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            double wi=w[i];
            if(type[i]==1)wi=log2(wi-x);
            else if(type[i]==2)wi=-log2(wi+x);
            if(dis[to]<dis[now]+wi) {//跑的是最大路
                dis[to]=dis[now]+wi;
                cnt[to]=cnt[now]+1;
                if(cnt[to]>n+1)return 1;//判断有没有环 
                if(vis[to]==0)q.push(to),vis[to]=1;
            }
        }
    }
    return 0;
}
//最短路的差分约束，会有最大值进行约束
//最长路的差分约束，会有最小值进行约束

int main() {
    double l=0,r=10;
    cin>>n>>m>>t;
    for(int i=1;i<=m;i++) {
        int op,x,y;
        double wi;
        cin>>op>>x>>y>>wi;
        add(y,x,wi,op);
        if(op&1)r=fmin(r,wi);
    }
    for(int i=1;i<=n;i++)add(0,i,0,3);//保证所有的边都是大于0的
    for(int i=1;i<=t;i++) {
        int c;double x;
        cin>>c>>x;
        add(0,c,log2(x),3);
        add(c,0,-log2(x),3);
    }
    //特殊边
    if(spfa(0)==0)return cout<<-1,0;
    //很显然k==0的时候条件是最容易达成的，首先特判一下子就可以了
    int cnt=0;
    while(r-l>eps) {//二分，找到最大值
        double mid=(l+r)/2;
        if(spfa(mid))l=mid;
        else r=mid;
    }
    printf("%.6lf\n",l);
    return 0;
}