模板：wqs二分
所谓wqs，就是windwhisper说：“qs”
（逃）
解析
很神奇的科技。
四两拨千斤的解决一些本来可能不太好解决的问题。
经典模型：有若干个物品，要求选出 m m m 个，选的时候带有限制，求最优的方案。
这个正常 dp 常常需要加一维记录个数，复杂度
O
(
n
2
)
O(n^2)
O(n2) 难以通过。
设
f
(
x
)
f(x)
f(x) 表示选
x
x
x 个元素的最优答案，那么 wqs 二分使用的前提是
f
(
x
)
f(x)
f(x) 具有凸性。
换句话说，所有的点
(
i
,
f
(
i
)
)
(i,f(i))
(i,f(i)) 共同形成一个凸包。
（以下以上凸包为例，下凸包同理）
考虑对这个凸包做一条斜率为
k
k
k 的切线，切于点
(
x
,
f
(
x
)
)
(x,f(x))
(x,f(x))。
如何找到这条切线呢？
注意到，切线在
y
y
y 轴上的截距必然是最大的。
设截距
D
=
f
(
x
)
−
k
x
D=f(x)-kx
D=f(x)−kx，我们就使要对于所有
x
x
x，求出
D
D
D 的最大值。
注意到
−
k
x
-kx
−kx 这一项，那么我们只需要把每个物品的价值减去
k
k
k，然后直接求最大值即可。
如果这个切点不在我们需要的
m
m
m 处，由于这个切点横坐标是随
k
k
k 单调的，所以我们可以二分寻找，直到可以切到
m
m
m 的
k
k
k 为止。
找到正确的
k
k
k，求出对应的
D
D
D 后，
f
(
x
)
f(x)
f(x) 就等于
D
+
k
x
D+kx
D+kx，也就不难得到了。
一些细节：
- 切点很坐标关于 k k k 的函数并不是连续的，因此可能需要最后一步强制选 m m m 个来算出答案，对应的，我们也最好把恰好取 m m m 个的情况归到大于 m m m 个的那边。
- 如果我们把相等的情况归于大于，那么在物品权值相等的时候我们就需要把特殊物品优先，这样如果我们强制抛弃才不会出现选不够 m m m 个的情况。
例题
给出一张图，求出在满足 1 1 1 的度数恰好为 m m m 的情况下的最小生成树。
显然最小生成树权值关于
1
1
1 的度数是一个凸函数。
那么我们就二分一个
k
k
k，令所有和
1
1
1 相连的边权值减去
k
k
k，跑一边最小生成树，看
1
1
1 的度数和
m
m
m 大小关系即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=1e6+100;
const int M=1e6+100;
const int mod=1e9;
int n,m,s,k;
struct edge{
int x,y,w,op,id;
}e[N];
bool cmp(edge x,edge y){
if(x.w!=y.w) return x.w<y.w;
else return x.op>y.op;
}
int fa[N];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
ll ans;
int q[N],num;
int check(int val,int op=0){
ans=0;
//printf("\nval=%d op=%d\n",val,op);
for(int i=1;i<=m;i++){
e[i].op?e[i].w+=val:0;
}
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m,cmp);
int o=n,d=0;
for(int i=1;o>1&&i<=m;i++){
int x=find(e[i].x),y=find(e[i].y);
//printf("(%d %d) val=%d\n",e[i].x,e[i].y,e[i].w);
if(x==y) continue;
if(op&&d==k&&e[i].op) continue;
//printf(" ok\n");
--o;d+=e[i].op;
fa[x]=y;
ans+=e[i].w;
if(op) q[++num]=e[i].id;
}
ans-=d*val;
if(o>1){
printf("-1\n");exit(0);
}
for(int i=1;i<=m;i++){
e[i].op?e[i].w-=val:0;
}
return d;
}
signed main(){
#ifndef ONLINE_JUDGE
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
#endif
n=read();m=read();s=1;k=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),w=read();
e[i]=(edge){x,y,w,x==s||y==s,i};
}
int st=-4e4,ed=4e4;
while(st<ed){
int mid=(st+ed+1)>>1,num=check(mid);
if(num>=k) st=mid;
else ed=mid-1;
//printf("mid=%d num=%d\n",mid,num);
}
if(st==-4e4) printf("-1\n");
else{
int nm=check(st,1);
//printf("st=%d num=%d\n",st,num);
printf("%d\n",num);
for(int i=1;i<=num;i++) printf("%d ",q[i]);
}
return 0;
}
/*
5 6 1 3
1 2 2
1 4 5
1 5 5
1 3 2
3 5 4
2 4 4
*/