#include <bits/stdc++.h>
#define int1 int
#define N 100000
#define M 200000
#define exp 1e-8
using namespace std;
int1 n,m,i,f[N + 5];//点数、边数、i、父亲(并查集用)
double l,r,mid,cost[M + 5],tim[M + 5];//二分左边界、右边界、中点;道路的花费和时间
int1 bs;//边数
struct Edge{
int1 x,y,id;
double w;
} e[M + 5];
bool cmp(Edge x,Edge y){//比较器
return x.w < y.w;
}
bool cmp2(Edge x,Edge y){//还原边的顺序
return x.id < y.id;
}
int1 read(){//快读
int1 x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)){
if (ch == '-'){
f = -1;
}
ch = getchar();
}
while (isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void uprint(int1 x){//快写
if (x >= 10){
uprint(x / 10);
}
putchar(x % 10 ^ 48);
return ;
}
void print(int1 x){//快写
if (x < 0){
putchar('-');
x = -x;
}
uprint(x);
return ;
}
void ps(int1 x){//快写
print(x);
putchar(' ');
return ;
}
void pe(int1 x){//快写
print(x);
putchar('\n');
return ;
}
void add_edge(int1 x,int1 y,double c,double t){
cost[++bs] = c,tim[bs] = t;
e[bs].x = x,e[bs].y = y,e[bs].id = bs;
return ;
}
int1 find(int1 x){//找爸爸
if(f[x] == x){
return x;
}
return f[x] = find(f[x]);
}
double kruskal(){//最小生成树(?)
sort(e + 1,e + bs + 1,cmp);//按边权排序
double s = 0;
int1 i;
for(i = 1; i <= n; i++){
f[i] = i;//父亲初始化
}
for(i = 1; i <= bs; i++){
int1 fx = find(e[i].x),fy = find(e[i].y);
if(fx == fy && e[i].w <= 0){//如果修这条边答案更优但在最小生成树里不修
s += e[i].w;//我照样要修
}
if(fx != fy){//如果没联通
f[fy] = fx;//修
s += e[i].w;
}
}
sort(e + 1,e + bs + 1,cmp2);//复原
return s;
}
bool check(double x){
//原理:sum(cost)/sum(time)<=x
//sum(cost)<=x*sum(time)
//sum(cost)-x*sum(time)<=0
//sum(cost-x*time)<=0
for(int1 i = 1; i <= bs; i++){
e[i].w = cost[i] - x * tim[i];//赋新边权
}
double s = kruskal();
return (s <= exp);//<=0即可
}
int main(){
n = read(),m = read();
for(i = 1; i <= m; i++){
int1 x = read() + 1,y = read() + 1;//把点从0~n-1变成1~n
double a = read() * 1.0,b = read() * 1.0;
add_edge(x,y,a,b);//建边(?)
}
l = 0.000001,r = 1000000;
while(r - l > exp){
mid = (l + r) / 2;
if(check(mid)){//如果满足条件就改右边界(因为是求最小值)
r = mid;
}else{
l = mid;
}
}
cout<< r << endl;
return 0;
}
机房电脑上不去AT,看不到具体情况