二分,最小生成树。
二分一下$k$,然后每次算最小生成树验证即可,事实证明,$cmp$函数,参数用引用还是能提高效率的,不引用一直$TLE$,时限有点卡常。
然后错误的代码好像$AC$了啊,$L$和$R$直接赋值成$mid$,有几个点一直$WA$,加一减一反而能过。
#include <cstdio>
#include <algorithm>
using namespace std; int n,m;
double M;
struct X
{
int u,v,f;
double t;
}e[100010],tmp[100010]; int b[100010]; bool cmp(X &a, X &b)
{
return a.t<b.t;
} int Find(int x)
{
if(x!=b[x]) b[x] = Find(b[x]);
return b[x];
} bool work(double x)
{
for(int i=1;i<=n;i++) b[i] = i; for(int i=1;i<=m;i++)
{
if(e[i].f==0) tmp[i] = e[i];
else
{
tmp[i] = e[i];
tmp[i].t = x*tmp[i].t;
}
} sort(tmp+1,tmp+1+m,cmp); double sum = 0;
for(int i=1;i<=m;i++)
{
int fa = Find(tmp[i].u);
int fb = Find(tmp[i].v);
if(fa==fb) continue; b[fa] = fb;
sum = sum + tmp[i].t;
if(sum>M+10) return 0;
} if(sum<=M) return 1;
return 0;
} int main()
{
while(~scanf("%d%d%lf",&n,&m,&M))
{
for(int i=1;i<=m;i++) scanf("%d%d%lf%d",&e[i].u,&e[i].v,&e[i].t,&e[i].f);
double L=1, R = 1e10, ans; for(int i=1;i<=55;i++)
{
double mid = (L+R)/2;
if(work(mid)) ans=mid, L=mid+1;
else R = mid-1;
}
printf("%.10f\n",ans);
}
return 0;
}