[学习笔记]WQS二分/凸优化

这个东西可真是耗了我好长时间啊QAQ

WQS二分是解决这样一类问题:

元素之间有一定的限制
每个元素有权值
强制选k个元素
要使权值和取到最值
没有选k个元素的限制会使问题容易求解
选 $x$ 个元素时的最优解 $g(x)$ 函数为凸函数

比较抽象,我们上题。

[国家集训队2]Tree I

给出一张无向联通图,边有黑白之分,求出包含恰好need条白边的最小生成树权值。

这个问题显然满足前五个条件,凸函数什么的...~~打表或者猜结论啊~~

先说做法吧...我们先求出一个不加限制的最小生成树,看看它有几条白边,如果少了,那么给白边整体减一些权值,多了就加一些,再求最小生成树,直到正好k条白边,此时的最优解减去白边附加权值即为答案。这个过程看起来可以二分,于是我们二分白边附加权值执行上述过程。

现在来解释算法正确性和一些细节。首先,如果我们我们现在给白边加了 $k$ 的权值使得最小生成树中有 $x$ 条白边,权值和为 $y$ ,那么 $g(x)=y-kx$ 。这个其实是显然的。
在求出的最优点我们有 $y-kx=g(x)$ ,于是可以看作 $y-kx$ 这条斜率为 $k$ 的直线与 $g(x)$ 有公共点,而y又是最优的,于是可以得出这条直线与 $g(x)$ 相切(直线平移,截距取最值)。
我们现在得出了几何意义,问题变得直观了。因为直线与 $g(x)$ 相切, $g(x)$ 又是凸函数,所以 $k$ 随 $x$ 单调变化,二分 $k$ 即可得到正确的 $x$ ,然后通过 $y-kx=g(x)$ 计算即可。

还有一个小细节,当价值都为整数时凸包上任一点的斜率都为整数,只需要在整数内二分 $k$ 即可(因为凸包上的点都是整点,计算斜率时分母为1...)。不过当价值为小数时就要小数二分 $k$ 了。

现在还有最后一个问题...如果我们怎么取 $k$ 都无法找到正确的 $x$ 怎么办？上面已经说明凸包上斜率为整数,那么这种情况出现只会是要求的 $x$ 在凸包上一段直线上(斜率不严格单调)。解决办法是:
对于一个 $k$ 在使价值取最值的同时让 $x$ 尽可能大(也就是与凸包有公共边时取到最右边的 $x$ ),二分出的 $x>=need$ 且 $k$ 取最值(最大或最小,具体分析...)时的 $k$ 即为所求,这时所求的 $need$ 这点一定在直线上,只需要通过 $y-k*need=g(need)$ 计算即可。
上代码...

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,m,need,n0,n1,sum,f[N],s[N],anss,ans2;
struct node{int x,y,d;bool friend operator <(node a,node b){return a.d<b.d;}}E,c0[N],c1[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool merge(int x,int y,int d){
    x=find(x),y=find(y);
    if(x==y)return 0;
    if(s[x]>s[y])swap(x,y);
    f[x]=y;s[y]+=s[x];
    ans2+=d;return 1;
}
int main(){
    scanf("%d%d%d",&n,&m,&need);
    for(int i=1,c;i<=m;i++)
        scanf("%d%d%d%d",&E.x,&E.y,&E.d,&c),
        (c?c1[n1++]:c0[n0++])=E,sum+=E.d;
    sort(c0,c0+n0);sort(c1,c1+n1);
    int l=-sum,r=sum,ans;
    while(l<=r){
        int mid=(l+r)>>1,i=0,j=0,now=0;ans2=0;
        for(int k=0;k<n;k++)f[k]=k,s[k]=1;
        while(i<n0&&j<n1)
            if(c0[i].d+mid>c1[j].d)merge(c1[j].x,c1[j].y,c1[j].d),j++;
            else now+=merge(c0[i].x,c0[i].y,c0[i].d+mid),i++;
        while(i<n0)now+=merge(c0[i].x,c0[i].y,c0[i].d+mid),i++;
        if(now>=need){
            while(j<n1)merge(c1[j].x,c1[j].y,c1[j].d),j++;
            anss=ans2;l=mid+1;ans=mid;
        }
        else r=mid-1;
    }
    printf("%d\n",anss-ans*need);
}

还有最后一个问题...虽然上面说明了如何应对取不到正确的 $x$ ,但是仅限于计算最优解的值,如果让构造方案同样GG。如果真要构造方案就得具体问题具体分析了...如 CF125E MST Company

常见的凸函数:

拟阵:

对于拟阵 $M=(U,T)$ ，将 $U$ 中的元素染为黑白二色并赋权，设 $F(x)$ 表示具有 $x$ 个白色元素的最大权独立集之权值，则 $F$ 为凸函数。证明

序列分k段,每段价值是和的平方。证明见wqs的论文。

现在我们来讲讲怎么构造方案

以上面提到的那道CF题为例。

我们现在二分出了一个斜率,已知need这个点也在这条直线上。我们可以用这个斜率把用最多白边和最少白边策略分别跑一遍克鲁斯卡尔。

首先通过拟阵的一些性质可以得出在斜率固定的情况下白边数量的可能情况是连续的。有了最大值和最小值之后我们就可以判是否无解了。那么接下来就是如何构造方案。

我们知道最小生成树边权相同的边之间才会互相替换,且同一边权的边用的数量是固定的。于是我们可以按照边权从小到大分批次地考虑这些边。不同批次之间的边相当于是独立的。

在上面求最少白边时我们可以顺带求出在每一批次中一定需要选的白边有哪些,那么我们构造时就先把这些边连上(不然构不成最小生成树)。当前批次中剩下的边可以全都选黑边,也可以选一些白边再选黑边。如何抉择剩下的边怎么选呢?我们之前求最多白边时可以对于每个边权 x,求出在满足最小生成树条件下边权大于 x 的边最多选多少白边,设为R[x]。那么在构造时对于x边权的不必要的白边只要加到 $now+R[x]==need$ 即可,然后这批次就可以只加黑边。

可以看出这个做法只和黑白边有关,于是国家集训队那题也可以构造方案啦!而且对于一般的wqs二分构造方案都可以套用这个思路。

Prutekoi's blog