[INFOR] 考幹題PC 蓋捷運

題目連結：https://oj.infor.org/contests/13/problems/71
　　考幹題真的讓我學到了很多新的東西（目前PF還沒寫出來），原本以為這題是一般的MST，不過試過範測後才察覺不對，因為分子分母的大小會影響最後值的大小，所以並不是單純以y/x當作權重。
　　看了演算法筆記才發現這有專有名詞叫做：mininum ratio spanning tree，這題的情況必須使用二分搜比例，若以r構出的圖的最小生成樹權重和為負的，代表比例可以更小，等於的話就是找到了最小比例。
　　不過因為二分搜範圍問題我TLE了無數次，一開始還假解過被學長rejudge，最後是用了greedy弄出了一個值之後再使用牛頓法迭帶才終於AC了，牛頓法很快，不過要注意初始就不能差太遠。（不過最終還是不知道OTOTOT學長的正解是甚麼==）

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define pii pair<int,pair<int,int>>
#define double long double
#define pi pair<double,pair<int,int> >
#define eps 0.000001
#define getchar getchar_unlocked
using namespace std;
inline int input()
{
    int x = 0;
    char cha;
    while(cha = getchar())
        if(cha >= '0' && cha <= '9') break;
    x = cha-48;
    while(cha = getchar())
    {
        if(cha < '0' || cha > '9') break;
        x = x*10 + cha-48;
    }
    return x;
}
class DSU{
    private:
        vector<int> fa,sz;
    public:
        inline void init(int n)
        {
            fa.resize(n+1), sz.resize(n+1,1);
            for(int i = 0; i <= n; i++) fa[i] = i;
        }
        inline int find(int x)
        {
            return (x==fa[x])?x:fa[x]=find(fa[x]);
        }
        inline bool same(int x,int y)
        {
            return find(x)==find(y);
        }
        inline void unite(int x,int y)
        {
            if(same(x,y)) return;
            if(sz[find(x)] < sz[find(y)]) swap(x,y);
            fa[find(y)] = find(x);
            sz[find(x)] += sz[find(y)];
        }
}dsu;
struct Q{
    int u,v;
    double x,y;
};
vector<Q> mrt;
vector<pi> kr;
int n,m;
double xx,yy,ans,c,d,pre = -1,mid;
int a,b;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    n = input(); m = input();
    while(m--)
    {
        int a,b;
        double c,d;
        a = input(); b = input(); c = input(); d = input();
        mrt.push_back({a-1,b-1,c,d});
        xx += c;
    }
    for(auto i:mrt) kr.push_back({i.y/i.x,{i.u,i.v}});
    sort(kr.begin(),kr.end());
    dsu.init(n);
    ans = 0;
    double kk = 0;
    for(auto p:kr)
    {
        if(dsu.same(p.second.first,p.second.second)) continue;
        dsu.unite(p.second.first,p.second.second);
        ans += p.first;
        kk+=1;
    }
    mid = ans/kk;
    while(abs(mid-pre) > eps)
    {
        kr.clear();
        for(auto i:mrt) kr.push_back({i.y-mid*i.x,{i.u,i.v}});
        sort(kr.begin(),kr.end());
        dsu.init(n);
        ans = 0;
        for(auto p:kr)
        {
            if(dsu.same(p.second.first,p.second.second)) continue;
            dsu.unite(p.second.first,p.second.second);
            ans += p.first;
        }
        pre = mid;
        mid += ans/xx;
    }
    cout << fixed << setprecision(8) << mid << '\n';
}