题目
分析
经典 wqs二分。
wqs二分的本质是:首先看出答案对于个数 \(k\) 有单调性,是个凸包。
然后把“凸包”投射到“y轴”上,此时我们要求这个凸包的顶端必须是取到题目限制的 \(k\) 个时可以取到最大/小值,如果是 \(k+c\) 或者 \(k-c\) 取到最大,则继续二分。
当正好取到 \(k\) 最大,停止二分,这样就使得我们既刚好取到 \(k\) 个又可以取到我们希望的最优解。
这里也是一样,我们对于白边多加权值进行限制即可。
但是注意:我们可以把白边黑边先分别储存,每次更新完白色就归并起来,这样可以省掉一个 \(sort\) 的 \(\log\) 。
代码
#include<bits/stdc++.h>
using namespace std;
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=5e5+5;
const ll INF=1e9;
int n,m,k,s;
struct Edge{
int u,v,col;ll w;
inline bool operator < (const Edge &B)const{return w<B.w;}
Edge(int u=0,int v=0,ll w=0,int col=0):u(u),v(v),w(w),col(col){}
}E1[N],E2[N],E[N];
int fa[N],top1,top2;
int Getfa(int x){return fa[x]==x?x:fa[x]=Getfa(fa[x]);}
ll sum,tot,cnt;
bool Kruskal(ll mid){
tot=sum=m=cnt=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=top1;i++) E1[i].w+=mid;
int j=1;
for(int i=1;i<=top2;i++){
while(j<=top1&&E1[j].w<=E2[i].w) E[++m]=E1[j],j++;
E[++m]=E2[i];
}
while(j<=top1) E[++m]=E1[j++];
for(int i=1;i<=m;i++){
int u=Getfa(E[i].u),v=Getfa(E[i].v);
if(u==v) continue;
fa[u]=v;sum+=E[i].w;
if(E[i].col==0) tot++;
if(cnt==n-1) return tot>=k;
}
for(int i=1;i<=top1;i++) E1[i].w-=mid;
return tot>=k;
}
signed main(){
read(n),read(m);read(k);
for(int i=1,u,v,w,col;i<=m;i++){
read(u),read(v),read(w),read(col);
u++,v++;
if(col==0) E1[++top1]=Edge(u,v,w,col);
else E2[++top2]=Edge(u,v,w,col);
}
sort(E1+1,E1+top1+1),sort(E2+1,E2+top2+1);
ll l=-INF,r=INF,ans=-1;
while(l<r){
ll mid=l+r+1>>1;
if(Kruskal(mid)) l=mid;
else r=mid-1;
}
Kruskal(r);
write(sum-min(k,(int)tot)*r);
return 0;
}