CF125E MST Company（题解）

· · 题解

P.S.

安利自己的wqs二分学习笔记
本着复习 wqs二分 的目的，我点开了这道题，结果呢。。。。。。

为了纪念来之不易的 AC，我打算写一篇题解。
不过看题解区吵地很厉害，我也不敢肯定这篇题解一定是对的，如果伪了还请原谅。

Description.

此题 输出方案。

Solution.

wqs 二分模板题。
我们把和 1 连边的点当作特殊物品。
然后按照套路二分斜率，每次判定对于和 1 相连的边跑一遍最短路。
由上文，我们每次直接对和 1 相邻边的权值加上当前二分的 mid。
判断有几条边和 1 相连，直接根据这个数量继续二分就好了。
小 tips：每次二分需要求一个 Kruskra，但是我们并不需要对于每次二分重新排序边。
我们只需要刚开始排序一遍，对于每次二分直接归并一下就好了。
于是，成功把复杂度从 O(n\log n\log V) 降至 O(n(\log n+\log V))
UpDate: 笔者偷懒，懒得写归并，直接sort，复杂度两只 \log。
然后以 904ms 的优异成绩通过了此题。

主要还需要介绍一些笔者出错的地方。

  1. 注意二分精度，建议二分到 double
  2. 开 long long
  3. 数据范围，边数量和点数量不同 不过没人和笔者这样sb吧
  4. 二分也需要二分到 +/-，值域需要大一点

然后就做完了，具体可以看代码。
有少量注释。

Coding.

//愿你和你重要的人能够再次重逢！
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
    x=0;char c=getchar(),f=0;
    for(;c<48||c>59;c=getchar()) if(!(c^45)) f=1;
    for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    f?x=-x:0;
}
struct node{int x,y;double w;int id;bool operator<(node b) {return w<b.w;}}e[100005],e1[100005],e2[100005];
int n,m,K,fa[10005],t1,t2;
inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
inline char mrg(int x,int y) {x=getf(x),y=getf(y);if(x^y) return fa[x]=y,1;else return 0;}
//↑并查集
inline char check(ll w)
{
    for(int i=1;i<=t1;i++) e[i]=e1[i],e[i].w+=w/100000.0;
    int cnt=0;for(int i=1;i<=t2;i++) e[i+t1]=e2[i];
    sort(e+1,e+m+1);for(int i=1;i<=n;i++) fa[i]=i;//暴力排序
    for(int i=1;i<=m;i++) if(mrg(e[i].x,e[i].y)) cnt+=(e[i].x==1||e[i].y==1);
    return cnt<=K;//计算有多少个点与 1 相连
}//↑二分check函数
int main()
{
    read(n),read(m),read(K),assert(0);ll le=-1e16-7,ri=1e16+7,rs=1e16+7;//值域，尽量大 （assert(0)不解释
    for(int i=1,x,y,w;i<=m;i++) {read(x),read(y),read(w);if(x==1||y==1) e1[++t1]=(node){x,y,w,i};else e2[++t2]=(node){x,y,w,i};}
    //↑把边分类   ↓wqs二分主体（一行
    while(le<=ri) {ll md=(le+ri)/2;if(check(md)) rs=md,ri=md-1;else le=md+1;}
    if(!check(rs)) return puts("-1"),0;else printf("%d\n",n-1);
    for(int i=1;i<=t1;i++) e[i]=e1[i],e[i].w+=rs/100000.0;
    for(int i=1;i<=t2;i++) e[i+t1]=e2[i];
    sort(e+1,e+m+1);for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) if(mrg(e[i].x,e[i].y)) printf("%d ",e[i].id);
    return putchar('\n'),0;//↑输出方案，check 直接赋值一遍（
}