博客

题目传送门

码农伯伯继续开始新的一季劳作：

题目大意：

有权无向图，边分黑、白两种；要求特定数量的白边（k条），构成最小生成树。

解题过程：

1、最朴素的想法：先对白边排序，然后取k条，再取剩下的黑边不就好了。（这是错的！），尝试一下自己反证。

2、然后看了各种题解，感觉似乎好像理解了：

正解思路：

1、如果对全部边进行排序，跑最小生成树，我们可以得到最优的ans，但是白边不一定是 k 条；

2、如果白边少了，说明白边整体权值比较大，所以没被选中。那我就对边都减一点权（x），这样的话，被选中的白边会增多

同理，如果被选白边数量大于k，我就给白边们都减去一个x。

3、接下来，我们二分这个x，就可以得到（我想要的白边数量的前提下）的最小生成树。

注意细节：

1、黑白边同权的时候，优先选择白边。

上代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int mx=100005;

int n,m,k,su,la[mx],f[mx];

struct nodb{int x,y,c,gg,s;}e[mx],b[mx];

bool cmp(nodb x,nodb y) { if(x.c==y.c) return x.s<y.s; return x.c<y.c; }
int chf(int x) { if(x==f[x]) return x; return f[x]=chf(f[x]); }
bool che(int x)
{
	for(int i=1;i<=n;i++) f[i]=i;//并查集
	for(int i=1;i<=m;i++)
	{
		b[i]=e[i];
		if(b[i].s==0) b[i].c+=x;//对白边+权 
	}
	sort(b+1,b+1+m,cmp);
	int kb=0,kk=0;//统计白边的数量 ：kb，统计边的数量：kk 
	su=0;
	for(int i=1;i<=m;i++)
	{
		int fx=chf(b[i].x);
		int fy=chf(b[i].y);
		if(fx!=fy)
		{
			f[fx]=fy;
			su+=b[i].c;
			if(b[i].s==0) kb++;
			kk++;if(kk==n-1) break;//选够了边 
		} 
	}
	if(kb>=k) return 1; return 0; 
}

int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d %d",&e[i].x,&e[i].y,&e[i].c,&e[i].s);
		e[i].x++;e[i].y++;//点的编号，从1开始 
	}
	int l=-150,r=150,ans;//边权最大100，做二分的那个值
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(che(mid)) //必须选够 k条
		{
			ans=su-k*mid;//答案要减掉 （+的权值） 
			l=mid+1;
		}
		else r=mid-1;
	} 
	printf("%d",ans);
	return 0;
}