2021.07.19 BZOJ2654 tree（生成树）

2021.07.19 BZOJ2654 tree（生成树）

tree - 黑暗爆炸 2654 - Virtual Judge (vjudge.net)

重点：

1.生成树的本质

2.二分

题意：

有一张无相带权连通图，每一条边都是黑色或者白色，求一棵恰好有need条白色边的最小生成树。

分析：

我们可以把每一条边按照一定优先级进行排序，当然，手动优先级（手动狗头），对于同一个权值的边，我们规定白色边比黑色边优先级高。但是对于权值特别小的的黑色边，在构成一棵生成树时，搞不好所有边都是由黑色边构成的，怎么办呢？当然还是手动给白色边改变优先级啊，把白色边供到太上皇的位置，他不想优先出现都难。白色边的颜色肯定不能改变，只能改变它的权值，白色边整体大平移活动正式开始！至于白色边到底要减多少合适，交给二分，朕相信它~

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=5e5+10;

int n,m,need,cnt,fa[N],vis[N*2];

struct node{

	int col,from,to,val;

	bool operator <(const node &b)const{

		return val==b.val?col<b.col:val<b.val;

	}

}a[N*2];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int find(int x){

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

int kruskal(){

	int sum=0;

	memset(vis,0,sizeof(vis));

	for(int i=1;i<=n;i++)fa[i]=i;

	sort(a+1,a+m+1);

	for(int i=1;i<=m;i++){

		int ui=find(a[i].from),vi=find(a[i].to);

		if(ui==vi)continue;

		fa[ui]=vi;

		sum+=a[i].val;

		vis[i]=1;

	}

	return sum;

}

bool check(int len){

	for(int i=1;i<=m;i++)if(!a[i].col)a[i].val-=len;

	int tmp=kruskal(),sum=0;

	for(int i=1;i<=m;i++)if(!a[i].col)

	a[i].val+=len,sum+=vis[i];

	return sum>=need;

}

int solve(){

	int l=-200,r=200;

	while(l<r){

		int mid=(l+r)>>1;

		if(check(mid))r=mid;

		else l=mid+1;

	}

	return l;

}

int main(){

	n=read();m=read();need=read();

	for(int i=1;i<=m;i++){

		a[i].from=read()+1;a[i].to=read()+1;

		a[i].val=read();a[i].col=read();

	}

	int len=solve();

	for(int i=1;i<=m;i++)if(!a[i].col)a[i].val-=len;

	int ans=kruskal();

	for(int i=1;i<=m;i++)if(!a[i].col)a[i].val+=len;

	ans+=len*need;

	cout<<ans;

	return 0;

}

2021.07.19 BZOJ2654 tree（生成树）的相关教程结束。