模板：wqs二分_wqs二分模板题

所谓wqs，就是windwhisper说：“qs”

（逃）

解析

很神奇的科技。
四两拨千斤的解决一些本来可能不太好解决的问题。

经典模型：有若干个物品，要求选出 $m$ 个，选的时候带有限制，求最优的方案。

这个正常 dp 常常需要加一维记录个数，复杂度 $O(n^2)$ 难以通过。
设 $f(x)$ 表示选 $x$ 个元素的最优答案，那么 wqs 二分使用的前提是 $f(x)$ 具有凸性。
换句话说，所有的点 $(i,f(i))$ 共同形成一个凸包。

（以下以上凸包为例，下凸包同理）
考虑对这个凸包做一条斜率为 $k$ 的切线，切于点 $(x,f(x))$。
如何找到这条切线呢？
注意到，切线在 $y$ 轴上的截距必然是最大的。
设截距 $D=f(x)-kx$，我们就使要对于所有 $x$，求出 $D$ 的最大值。
注意到 $-kx$ 这一项，那么我们只需要把每个物品的价值减去 $k$，然后直接求最大值即可。
如果这个切点不在我们需要的 $m$ 处，由于这个切点横坐标是随 $k$ 单调的，所以我们可以二分寻找，直到可以切到 $m$ 的 $k$ 为止。
找到正确的 $k$，求出对应的 $D$ 后，$f(x)$ 就等于 $D+kx$，也就不难得到了。

一些细节：

1. 切点很坐标关于 $k$ 的函数并不是连续的，因此可能需要最后一步强制选 $m$ 个来算出答案，对应的，我们也最好把恰好取 $m$ 个的情况归到大于 $m$ 个的那边。
2. 如果我们把相等的情况归于大于，那么在物品权值相等的时候我们就需要把特殊物品优先，这样如果我们强制抛弃才不会出现选不够 $m$ 个的情况。

例题

给出一张图，求出在满足 $1$ 的度数恰好为 $m$ 的情况下的最小生成树。

显然最小生成树权值关于 $1$ 的度数是一个凸函数。
那么我们就二分一个 $k$，令所有和 $1$ 相连的边权值减去 $k$，跑一边最小生成树，看 $1$ 的度数和 $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
*/


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98