@[LXH5514](/user/177604) 我跟你一样的情况!!
这个应该不是你这种处理方法的问题,主要原因在于原图上有很多长度相等的边,减掉一个值后跑MST可能会使得MST无法刚好得到need条边。
像这个测试点就是mid=-8和-9的时候都不能刚刚好362条边,事实上mid取小数也不行
我也不清楚题解里的代码为啥没这个问题,但还是有别的解决办法的:
你给每条边的边权加一个随机扰动,这样就强制让边权不一样了,然后可以跑出来结果(虽然常数有点大)
注意随机扰动要小一点,防止最终的扰动影响结果
主函数:
```cpp
int main()
{
cin>>n>>m>>k;
for (LL i=1;i<=m;i++)
{
cin>>E[i].u>>E[i].v>>E[i].w>>E[i].c;
E[i].w+=rand()*1.0/rand()/10000000.0;
E[i].u++; E[i].v++;
E[i].c^=1;
}
double l=-200,r=200;
LL Ans=-1;
while (r-l>1e-12)
{
double mid=(l+r)/2;
ans=0,cnt=0;
check(mid);
if (cnt>=k) Ans=ans,r=mid;
else l=mid;
}
cout<<Ans<<endl;
return 0;
}
```
by 平衡树森林 @ 2021-10-26 19:11:11
好像第一个题解里就是mid=-8时更新的答案
by 白厶冯弓吿氵 @ 2022-04-16 16:24:19
而这时它的白边仍然才选了365条
边权和(没加mid)是22395
by 白厶冯弓吿氵 @ 2022-04-16 16:38:52