推荐FlashHu的博客,用导数来理解(wqs)二分真的太妙啦,也解释为啥必须是凸函数才能用(wqs)二分
还有Creeper_LKF的数形结合的博客
Solution Tree I
题目大意:每条有黑白颜色,求恰好选择(need)条白色边条件下的最小生成树
(wqs)二分
分析:设(g(x))为恰好选(x)条白边的最小生成树权值和,那么经过打表我们可以猜想证明出(g)是一个下凸函数(其实可以(dp)的……)
然后我们就可以用(wqs)二分了
这玩意儿通常用来解决有某种限制,每个物品有个权值,钦定必须选(x)个时候的最大/小权值和
要求函数(g)必须是凸函数,这样我们才可以对导函数进行二分
以上凸函数为例,我们要求的是(g)在给定的(m)处的取值,显然我们没法直接算出来(废话,不然干嘛不直接算,雾)
但是我们可以通过贪心 / (dp)等等来求出不考虑限制的时候的最大函数值,顺带求出自变量的值。然后我们看这个函数(g)的导函数(g'),当(g)取到最大值的时候(g')交(x)轴
如果我们把(g(x))加上(kx)的话,不就等价于把导函数向上平移(k)个单位了吗
我们二分(k),使得导函数交(x)轴于我们期望的(m),然后这个时候我们就可以求出(g(m))啦
完了?naive
我们加上了(kx),也就是对(g(m))加上了(km),记得减掉
此题同理,我们二分一个(k),对所有白边的权值加上(k),跑(Kruskal)即可
黑白边同权选白边,然后没必要每次都做快排,可以黑白边分开然后每次跑归并排序,这样可以省下一个(log)的复杂度
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
struct Edge{
int from,to,dist,col;
}Edges[maxn],black[maxn],white[maxn];
int f[maxn],n,m,need,sz,black_siz,white_siz;
inline void init(){
for(int i = 1;i <= n;i++)f[i] = i;
sz = n;
}
inline int find(int x){
return (x == f[x]) ? x : f[x] = find(f[x]);
}
inline void merge(int a,int b){
int x = find(a),y = find(b);
if(x != y){
sz--;
f[x] = y;
}
}
inline int kruskal(int delta){
int res = 0,posa = 1,posb = 1,tot = 0;
while(posa <= white_siz && posb <= black_siz)
if(white[posa].dist + delta <= black[posb].dist)Edges[++tot] = white[posa++],Edges[tot].dist += delta;
else Edges[++tot] = black[posb++];
while(posa <= white_siz)Edges[++tot] = white[posa++],Edges[tot].dist += delta;;
while(posb <= black_siz)Edges[++tot] = black[posb++];
init();
for(int i = 1;i <= m && sz != 1;i++){
const Edge &e = Edges[i];
if(find(e.from) != find(e.to))res += !e.col;
merge(e.from,e.to);
}
return res;
}
int main(){
n = read(),m = read(),need = read();
for(int u,v,w,c,i = 1;i <= m;i++){
u = read() + 1,v = read() + 1,w = read(),c = read();
if(c == 0)white[++white_siz] = Edge{u,v,w,c};
else black[++black_siz] = Edge{u,v,w,c};
}
sort(white + 1,white + 1 + white_siz,[](const Edge &a,const Edge &b){return a.dist < b.dist;});
sort(black + 1,black + 1 + black_siz,[](const Edge &a,const Edge &b){return a.dist < b.dist;});
int l = -111,r = 111,ans = 233;
while(l <= r){
int mid = (l + r) >> 1,tmp = kruskal(mid);
if(tmp < need)r = mid - 1;
else ans = mid,l = mid + 1;
}
if(ans == 233)abort();
int posa = 1,posb = 1,tot = 0;
while(posa <= white_siz && posb <= black_siz)
if(white[posa].dist + ans <= black[posb].dist)Edges[++tot] = white[posa++],Edges[tot].dist += ans;
else Edges[++tot] = black[posb++];
while(posa <= white_siz)Edges[++tot] = white[posa++],Edges[tot].dist += ans;
while(posb <= black_siz)Edges[++tot] = black[posb++];
init();
ans *= -need;
for(int i = 1;i <= m && sz != 1;i++){
const Edge &e = Edges[i];
if(find(e.from) != find(e.to))ans += e.dist;
merge(e.from,e.to);
}
printf("%d
",ans);
return 0;
}