USACO 2001 OPEN earthquake /// 最优比例生成树

题目大意：

https://www.cnblogs.com/forever97/p/3603572.html

讲解：https://www.jianshu.com/p/d40a740a527e

题解：https://www.cnblogs.com/shuaihui520/p/10278840.html

#include <bits/stdc++.h>
using namespace std;
const double eqs=1e-8;
int n,m;
double f;
struct NODE {
    int v; double w,t,val;
    bool operator <(const NODE& p)const {
        return val<p.val;
    }
};
vector <NODE> G[405];
bool vis[405];
double prim(double x) {
    memset(vis,0,sizeof(vis));
    priority_queue <NODE> q;
    while(!q.empty()) q.pop();
    for(int i=0;i<G[1].size();i++) {
        NODE e=G[1][i];
        e.val=e.w-x*e.t;
        q.push(e);
    } vis[1]=1;
    int cnt=0;
    double X=0.0, Y=0.0;
    while(!q.empty()) {
        NODE e=q.top(); q.pop();
        if(vis[e.v]) continue;
        vis[e.v]=1;
        cnt++; X+=e.w, Y+=e.t;
        if(cnt==n-1) break;
        for(int i=0;i<G[e.v].size();i++) {
            NODE p=G[e.v][i];
            p.val=p.w-x*p.t;
            q.push(p);
        }
    }
    return X/Y;
}
int main()
{
    while(~scanf("%d%d%lf",&n,&m,&f)) {
        f/=1.0*(n-1);
        while(m--) {
            int u,v; double w,t;
            scanf("%d%d%lf%lf",&u,&v,&w,&t);
            G[u].push_back({v,f-w,t,0.0});
            G[v].push_back({u,f-w,t,0.0});
        }
        double ans=0.0, tmp=0.0;
        while(1) {
            ans=prim(tmp);
            if(abs(ans-tmp)<eqs) break;
            tmp=ans;
        }
        if(ans>0) printf("%.4f
",ans);
        else printf("0.0000");
    }

    return 0;
}