自动搬运

查看原文

来自洛谷，原作者为

	Gary818 **

搬运于2025-08-24 21:39:43，当前版本为作者最后更新于2019-07-12 15:43:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题吧，说难也不难，说简单也不简单

其实题目给的很明确
让你求一棵最小权的恰好有need条白色边的生成树。
这不是明摆着要求最小生成树吗？
刚要开始写，问题接踵而至，这个白边的数量怎么控制呢，如果多了或者少了，如何增减？

进入正题： 总所周知，在跑kruskal的时候，我们有这样一句代码：

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

这是对边进行排序，由此可知，边权越小越靠前
我们可以通过改变白边的权值来改变它出现的位置

例如need=3，但是此时我的最小生成树上有4条白边，那么我可以全部加上一个数，然后某条白边突然比最小的黑边大了，我再跑kruskal，更新之后的最小生成树就会把一条大的白边扔到后边去，替换成一条黑边，那么此时白边条数就少了1，满足答案，统计答案时把加的这个数减掉就行了

现在我们来说说怎么确定要加的这个数
我们采取二分答案的办法，因为题目中说道边权在[1,100]所以定义l=-111,r=111,然后二分往白边上加权值，最后一定能卡出来一个合适的解

那么问题又来了，如果说当前白边加上mid后，白边条数temp>need了，然鹅，如果加上mid+1后，temp<need了，这可咋整，难搞哟~~

题目中说到了：保证有解，所以出现上述情况时一定有黑边==白边的边权
so，我们只需要把一条黑边换成白边就好啦
在白边条数temp>need时更新答案
最终答案$ans=sum-mid×need$

代码时间：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int fa[1000010];
int n,m,need;
struct node{
	int s,t,v,c;//起点、终点、权值、颜色
}e[1000010];

inline bool cmp(node a,node b){//排序
	if(a.v==b.v) return a.c<b.c;
	else return a.v<b.v;
}

inline int find(int x){//并查集不会赶紧学去
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

int sum,ans,temp;
int cnt=0;
inline void kruskal(){//板子
	sort(e+1,e+1+m,cmp);
	for(int i=1;cnt!=n-1;i++){
		int xx=find(e[i].s),yy=find(e[i].t);
		if(xx==yy) continue;
		if(xx!=yy){
			cnt++;
			fa[xx]=yy;
			if(e[i].c==0) temp++;//统计白边数量
			sum+=e[i].v;
		} 
	}
}

int main(){
	cin>>n>>m>>need;
	for(int i=1;i<=m;i++){
		cin>>e[i].s>>e[i].t>>e[i].v>>e[i].c;
		e[i].s++,e[i].t++;//注意！因为题面说0开始标号
	}
	int l=-111,r=111;//二分，初始值比100大就行
	while(l<=r){
		int mid=(l+r)>>1;
		for(int i=1;i<=m;i++)
			if(e[i].c==0)
				e[i].v+=mid;//白边加权
		for(int i=1;i<=n+1;i++)
			fa[i]=i;//初始化
		sum=0,cnt=0,temp=0;//每次要清空
		kruskal();
		if(temp>=need){
			l=mid+1;
			ans=sum-need*mid;//更新答案
		}
		else r=mid-1;
		for(int i=1;i<=m;i++)
			if(e[i].c==0)
				e[i].v-=mid;//最终要把加上的减掉
	}
	cout<<ans<<'\n';//over
	return 0;
}

感觉讲的挺明白了叭，不懂评论区见，溜~~~