原题传送门
01分数规划
f
−
∑
c
x
∑
t
x
=
a
n
s
\frac{f-\sum c_x}{\sum t_x}=ans
∑txf−∑cx=ans
f
−
∑
c
x
−
∑
t
x
∗
a
n
s
=
0
f-\sum c_x-\sum t_x*ans=0
f−∑cx−∑tx∗ans=0
f
>
=
∑
c
x
+
∑
t
x
∗
a
n
s
f>=\sum c_x+\sum t_x*ans
f>=∑cx+∑tx∗ans
二分答案
m
i
d
mid
mid,将边权赋为
c
x
+
t
x
∗
m
i
d
c_x+t_x*mid
cx+tx∗mid
求最小生成树,总边权和
f
f
f比较
Code:
#include <bits/stdc++.h>
#define maxn 40010
using namespace std;
const double eps = 1e-6;
double F;
int f[maxn], n, m;
struct Line{
int x, y;
double c, t, l;
}line[maxn];
inline int read(){
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
return s * w;
}
bool cmp(Line x, Line y){ return x.l < y.l; }
int getfa(int k){ return f[k] == k ? k : f[k] = getfa(f[k]); }
bool check(double mid){
for (int i = 1; i <= n; ++i) f[i] = i;
for (int i = 1; i <= m; ++i) line[i].l = line[i].c + line[i].t * mid;
sort(line + 1, line + 1 + m, cmp);
double s = 0;
for (int i = 1; i <= m; ++i){
int s1 = getfa(line[i].x), s2 = getfa(line[i].y);
if (s1 != s2) f[s1] = s2, s += line[i].l;
}
return F - s >= eps;
}
int main(){
n = read(), m = read(), F = read();
for (int i = 1; i <= m; ++i) line[i].x = read(), line[i].y = read(), line[i].c = read(), line[i].t = read();
double l = 0, r = F, ans = 0;
while (fabs(r - l) > eps){
double mid = (l + r) / 2.0;
if (check(mid)) ans = mid, l = mid; else r = mid;
}
printf("%.4lf\n", ans);
return 0;
}