30 分代码玄关求条 AC on #1#2#3

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define N 2010
#define M 16010
#define eps 1e-6
namespace graph{
    int head[N],nxt[M],to[M];
    double weig[M];// 边权（小数）
    int cnt_edge;
    inline void connect_head(const int &x,const int &y,const double &w){
        ++cnt_edge;
        nxt[cnt_edge] = head[x];
        to[cnt_edge] = y;
        weig[cnt_edge] = w;
        head[x] = cnt_edge;
    }
}
using namespace graph;
int n,s,t,tmp;
struct edge{
    int op,a,b;
    double k;
}p[M];
double l,r,mid,nx;
bool inq[N];// 在队列中
int cnt[N];
double d[N];
bool ud[N];
double dst[N];// 跑最长路判断是否可行


inline void push(){
    memset(head,0,(n<<2)+40);
    cnt_edge = 0;
    // 根据条件放入边
    for(int i = 1;i <= s;++i){
        if(p[i].op == 1){
            connect_head(p[i].b,p[i].a,log2(p[i].k - mid));
        }else{
            connect_head(p[i].b,p[i].a,-log2(p[i].k + mid));
        }
    }
    // 根据一些限制放入边
    dst[0] = -INF,cnt[0] = inq[0] = 0;
    for(int i = 1;i <= n;++i){
        dst[i] = -INF;
        cnt[i] = inq[i] = 0;
        if(!ud[i])continue;
        connect_head(0,i,d[i]);
        connect_head(i,0,-d[i]);
    }
    for(int i = 0;i <= n;++i)connect_head(n+1,i,0);
    dst[n+1] = 0,cnt[n+1] = inq[n+1] = 0;
}

inline bool check(){
    // 放入
    push();
    // spfa 最长路
    queue<int> q;
    q.push(n+1);
    int x;
    while(q.size()){
        x = q.front();
        q.pop();
        inq[x] = 0;
        // printf("spfa %d\n",x);
        for(int edg = head[x];edg;edg = nxt[edg]){
            nx = dst[x] + weig[edg];
            if(abs(dst[to[edg]] - nx) <= eps || dst[to[edg]] > nx)continue;
            dst[to[edg]] = nx;
            if(inq[to[edg]])continue;
            inq[to[edg]] = 1;
            ++cnt[to[edg]];
            q.push(to[edg]);
            if(cnt[to[edg]] > n + 1)return 0;// 不可行，有人要女装
        }
    }
    return 1;
}

// 输入函数
void input(){
    scanf("%d%d%d",&n,&s,&t);
    r = 10;
    for(int i = 1;i <= s;++i){
        scanf("%d%d%d%lf",&p[i].op,&p[i].a,&p[i].b,&p[i].k);
        r = min(r,p[i].k);
    }
    // 输入 t 个已知选手
    for(int i = 1;i <= t;++i){
        scanf("%d",&tmp);
        scanf("%lf",d+tmp);
        ud[tmp] = 1;
        d[tmp] = log2(d[tmp]);
    }
}

// 处理函数
void solve(){
    mid = 0;
    if(check()){
        r = 0;
        return;
    }
    l = 0;
    // int cnt = 60;
    while(abs(r - l) > eps){
        mid = (l+r)/2;
        if(check())r = mid;
        else l = mid;
        // printf("mid = %.10lf\n",mid);
        // 输出 dst
        // for(int i = 0;i <= n;++i)printf("idx = %d dst = %.10lf\n",i,dst[i]);
    }
}

// 输出函数
void output(){
    mid = (l+r)/2;
    if(check())printf("-1");
    else printf("%.10lf",mid);
}

// 主函数
int main(){
    input();
    solve();
    output();
    return 0;
}