P2619 [国家集训队]Tree I

题目

P2619 [国家集训队]Tree I

分析

经典 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;
}