题目描述

原题来自：2012 年国家集训队互测

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有条白色边的生成树。题目保证有解。

输入格式

第一行V，E,need 分别表示点数，边数和需要的白色边数。

接下来E行，每行s,t,c,col表示这边的端点（点从0开始标号），边权，颜色（0白色，1黑色）。

输出格式

一行表示所求生成树的边权和。

样例

样例输入

2 2 1
0 1 1 1
0 1 2 0

样例输出

题解:

这个题要求在选取特定数量的基础上，构造一棵最小生成树。我们想一下，因为最小生成树所选择的是当前排序后最小的边(采用克鲁斯卡尔算法)，如果我们把白色的边增大，那么这棵最小生成树里面的白色边就会少一些(因为边越大，排序的次序就越靠后)，反之亦然。那么我们跑一个二分，把所有白边减一个mid，如果在此时最小生成树的白边数量比题目要求大，就说明目前mid的值大了，将其减少，否则将其增大。当此时最小生成树的白边数量等于题目所给的need时，说明此时的最小生成树即使满足题目要求的最佳情况，且因为此时最小生成树的值是在所有白边都减了一个mid的基础之上，所以答案还需增加一个need*mid;
有一位大佬问了我一个问题：

个人认为你并没有说明可以一定可以取到一个值使得恰好为k个

那么下面附上我的回答(感谢这位大佬！！！)

因为mid的值是没有范围的，所以我们可以通过mid的大小让所有的白边比最小的黑边还小，或者让他们比最大的黑边还大，那么在确保黑边有n-1条后，我们可以让白边的数量通过mid确定范围为0~n-1,所以一定有一个值使得恰好为k个(只要黑边数量大于n-1)

代码

#include<bits/stdc++.h>

using namespace std;

struct zz{

	int u,v,w,col;

}a[100005];

int pre[50005];

int n,m,k;

int Find(int x){

	if(pre[x]!=x){

		pre[x]=Find(pre[x]);

	}

	return pre[x];

}

bool cmp(zz x,zz y){

	if(x.w!=y.w)

		return x.w<y.w;

	return x.col<y.col;        //如果两个值相同，白色放前面(或者说是优先考虑白色)，如果不相同，那么根据克鲁斯卡尔，权值小的放前面；

}

int CHEAK(int pd,int mid){       //克鲁斯卡尔，如果pd为一，那么说明 我们在统计最小生成树的权值和，如果等于0，那么说明我们在判断白边的个数；

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

		if(a[i].col==0){

			a[i].w-=mid;      //全部减去mid;

		}

	}

	for(int i=0;i<n;i++)

		pre[i]=i;

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

	int cnt=0,toto=0,sum=0;

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

		int fx=Find(a[i].u),fy=Find(a[i].v);

		if(fx==fy)

			continue;

		pre[fx]=fy;

		sum+=a[i].w;

		if(a[i].col==0)

			cnt++; 			//如果是白边，则统计；

		toto++;

		if(toto==n-1)	break;

	}

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

		if(a[i].col==0)

			a[i].w+=mid;    //减了之后别忘加回来！！！

	}

	if(pd==0)

		return cnt;

	return sum;

}

int main(){

	cin>>n>>m>>k;

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

		scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].w,&a[i].col);

	}

	int l=-105,r=105;  //二分边界

	int ans=105;      //统计最后减去的mid；

	while(l<=r){

		int mid=(l+r)/2;

		int pd=CHEAK(0,mid);

		if(pd>=k)

			r=mid-1,ans=mid;

		else

			l=mid+1;

	}

	cout<<CHEAK(1,ans)+k*ans;      //答案记得加上减去的mid;

}

巴特西

「一本通 3.1 练习 4」Tree 题解

题目描述

输入格式

输出格式

样例

样例输入

样例输出

题解:

代码

最新文章

热门文章