当前位置:   article > 正文

模板:wqs二分_wqs二分模板题

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,也就不难得到了。

一些细节:

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


  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/436714
推荐阅读
相关标签
  

闽ICP备14008679号