学习笔记 - 凸优化

果然 Tiw 讲的课都会自闭……


Part1. 凸优化

又称 带权二分,wqs分治

“带权二分”表现了算法的实现,“凸优化”揭示了算法的本质,“wqs分治”表述了将其引入OI的人

- Tiw_Air_OAO

Part1/1. 适用范围

凸优化适用于一类限制了“恰好有 k 个……”的题目。

> 听起来是不是非常广泛?但它还有一个条件。

既然算法名字里面带 “凸” —— 凸包!定义 $f(t)$ 表示当 k=t 时,题目所求的最优答案。那么 $f(t)$ 必须满足一个凸性质,即 $(t,f(t))$ 要么形成上凸包,要么形成下凸包。

Part1/2. 核心思想

既然还有一个别称叫“带权二分”,“带权”即 附加权值

定义附加权值为 c,并且给题目中所述的 “k 个……” 每一个的权值都附加 c。然后求出此时的最优答案(不考虑题目中“恰好 k 个的限制”)$f’(x)$ 以及对应的 x。
不难发现 $f’(x)=f(x)+cx$,因为 “x 个……” 每一个都附加了权值 c,所以多了一个 $cx$。

然后移一下项:$f(x)=-cx+f’(x)$!发现这是一个直线的解析式,$-c$ 为斜率,$f’(x)$ 为截距。

由于 $f(x)$ 的凸性质,可以得到 $f(x)$ 的切线的斜率与 $x$ 成单调性。当我们找到一个斜率 $-c$,满足其最优答案 $f’(x)$ 对应的 $x=k$,那么 $f’(x)-cx=f(x)=f(k)$ 就是我们要求的最优答案。

于是我们就可以 二分 $c$ 的权值,然后求出 $f’(x)$ 对应的 $x$,根据 $x$ 与 $k$ 的大小关系,调整 $c$ 的范围。

> Hint
现在还比较抽象,不妨先把不懂的放一放,之后看例题解析就明白了~

Part1/3. 栗子

假设 $f(x)$ 长下面这样:

png1

此时算出来的 $f’(x)$ 对应的 $x$ 大于 $k$,因此要让 $x$ 向左移,观察凸包,发现就是要让切线的斜率 $-c$(注意有负号)减小,即让切线变陡。

Part1/4. 算法正确性

由之前的式子 $f’(x)=f(x)+cx$,可知:由于我们求的是 $f’(x)$ 的最优值,那么减去 $cx$,一定是 $f(x)$ 的最优值。

会不会出现当 c 减小一点 x 就比 k 大,c 增大一点 x 就比 k 小(或者反过来)……反正就是二分不到 x=k?

但是由于 $f(x)$ 的凸性质,二分斜率一定可以判断出怎样调整斜率可以让 x 向 k 的方向移。唯一比较麻烦的情况就是三点共线……像下面这样:

png2

非常尴尬 事实上很有可能出现这种情况……二分的时候计算 $f’(x)$ 对应的 $x$,可能计算到 $k-1,k+1$,但是就是算不到 $k$。看似我们求不到 $f’(k)$,实际上正因为这几个点共线,我们只要求出那 3 个点的 $f’(x)$ 之一即可。

比如我们求得了 $f’(k-1)$,那么根据凸包,不难发现 $f(k)=f’(k-1)-ck$。照样能够算出来。


Part2. 例 - tree

要对题目中的 “恰好” 二字敏感……

Part2/1. 题面

有一个无向连通图,每条边有边权和颜色。边有黑白两色。
求在包含恰好 k 条白边的情况下的最小生成树,保证有解。

点数不超过 $50000$,边数不超过 $10^5$。

Part2/2. 解析

发现恰好二字,然后来研究一下 $f(x)$ 即“恰好有 $x$ 条白边的最小生成树”的性质。打表发现(不开玩笑……反正又不要你证明),$f(x)$ 满足下凸性质。然后就愉快地带权二分了!

二分一个附加值 c(就是切线的斜率),然后给每条白边都附加一个权值 c(白边的边权增加 c),跑一遍 Kruskal,在求出最小生成树 $f’(x)$ 的同时统计一下选的白边的数量 $x$。

再根据 $x,k$ 的大小关系,二分调整 c 的大小就好了。

> Tip
其实感性理解一下,当我们增大附加值 c 时,选择白边的代价增大,要使生成树代价小,白边被选的概率就会减小;反之减小 c 时,选择白边代价减小,被选的概率增大。

Part2/3. 源代码

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
/*Lucky_Glass*/
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5e4,M=1e5;

struct DSU{
int fa[N+3];
void Init(int n){
for(int i=0;i<=n;i++)
fa[i]=i;
}
int FindFa(int u){
if(fa[u]==u) return u;
return fa[u]=FindFa(fa[u]);
}
bool Merge(int u,int v){
int fu=FindFa(u),fv=FindFa(v);
if(fu==fv) return false;
fa[fu]=fv;
return true;
}
}D_;
struct EDGE{
int u,v,cst,typ;
EDGE(){}
EDGE(int _u,int _v,int _c,int _t):u(_u),v(_v),cst(_c),typ(_t){}
}E_[M+3];

int n,m,ned,ans;

bool cmpEDGE(const EDGE &cura,const EDGE &curb){
if(cura.cst==curb.cst) return cura.typ<curb.typ;
return cura.cst<curb.cst;
}
bool Check(int add){
D_.Init(n);
for(int i=1;i<=m;i++)
if(E_[i].typ==0)
E_[i].cst+=add;
sort(E_+1,E_+1+m,cmpEDGE);
int sum=0,wht=0;
for(int i=1;i<=m;i++)
if(D_.Merge(E_[i].u,E_[i].v)){
sum+=E_[i].cst;
wht+=!E_[i].typ;
}
for(int i=1;i<=m;i++)
if(E_[i].typ==0)
E_[i].cst-=add;
ans=sum-wht*add;
return wht>=ned;
}
int main(){
scanf("%d%d%d",&n,&m,&ned);
for(int i=1;i<=m;i++)
scanf("%d%d%d%d",&E_[i].u,&E_[i].v,&E_[i].cst,&E_[i].typ);
int adl=-200,adr=200;
while(adl+1<adr){
int adm=(int)floor((adl+adr)*0.5);
if(Check(adm)) adl=adm;
else adr=adm;
}
Check(adl);
printf("%d\n",ans);
return 0;
}

The End

Thanks for reading!

OI 的半期考试要来了 :)

0%