题解：P7177 [COCI 2014/2015 #4] MRAVI

wu_yichen · 2026-08-08 11:31:57 · 题解

思路

我们能够发现题目中有明显的单调性，液体越多越容易养活蚂蚁，能想到二分答案，我们在判定时能够发现，如果这个管道有超能力，则可以直接使用。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a,b,x,y;
double ans,l,r,mid,m=0.0001,f[1005];
struct node{
    int x,y,cnt;
};
vector<node> g[1005];
bool ff(int num,double x){
    if(f[num]!=-1) return (x>=f[num]);
    bool ok=1;
    for(node i:g[num]){
        if(i.cnt==1) ok&=ff(i.x,(x*i.y)*(x*i.y)/10000);
        else ok&=ff(i.x,(x*i.y)/100);
    }
    return ok;
}
int main(){
    return 0;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b>>x>>y;
        g[a].push_back({b,x,y});
    }
    for(int i=1;i<=n;i++) cin>>f[i];
    l=1,r=2000000000;
    while(r-l>=m){
        mid=(l+r)/2;
        if(ff(1,mid)) ans=mid,r=mid-m;
        else l=mid+m;
    }
    printf("%.6lf\n",ans);
    return 0;
}

留了惊喜