bzoj1196: [HNOI2006]公路修建问题（最小生成树+模板题）

bzoj题目链接

luogu题目连接

题目大意：

    1、n个点，m-1条边，每条边有两个权值，权1表示用高价修路，权2表示用低价修路。

    2、求：选k条高价路的情况下，最小生成树的边权最大值是多少？

解题思路：

    1、题目框架和昨天做的2654tree似乎一样，都是双色道路，其中一个颜色选特定的数量。

    2、但认真看题发现，这题要水一些。题目已经规定，高价的道路一定比低价的道路贵，就不用担心交叉权值的问题。

    3、所以，直接跑两次最小生成树就完事了！赤裸裸的模板

上代码

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

int n,m,k,ans=0;
struct nodb{int x,y,s1,s2,gg,v;}e[mx],b[mx];
int la[mx],f[mx];
bool cmp1(nodb x, nodb y) { return x.s1<y.s1; }
bool cmp2(nodb x, nodb y) { return x.s2<y.s2; }
int ch(int x) { if(x==f[x]) return x; return f[x]=ch(f[x]); }
void bk()
{	int kk=0;
	sort(e+1,e+1+m,cmp1);
	for(int i=1;i<=m;i++)
	{
		if(e[i].v==1)
		{
			int xx=ch(e[i].x);
			int yy=ch(e[i].y);
			if(xx!=yy)
			{
				f[xx]=yy;
				e[i].v=0;//选这条边
				if(ans<e[i].s1) ans=e[i].s1;//取极值
				kk++; if(kk==k) break;
			}
		}
	}
}
void bn()
{
	int kk=0;
	sort(e+1,e+1+m,cmp2);
	for(int i=1;i<=m;i++)
	{
		if(e[i].v==1)
		{
			int xx=ch(e[i].x);
			int yy=ch(e[i].y);
			if(xx!=yy)
			{
				f[xx]=yy;
				e[i].v=0;//选这条边
				if(ans<e[i].s2) ans=e[i].s2;//取极值
				kk++; if(kk==n-1-k) break;
			}
		}
	}
}

int main()
{
	scanf("%d %d %d",&n,&k,&m);
	for(int i=1;i<m;i++)
	{
		scanf("%d %d %d %d",&e[i].x,&e[i].y,&e[i].s1,&e[i].s2);
		e[i].v=1;
	}
	for(int i=1;i<=n;i++)	{ la[i]=0;f[i]=i; }
	bk();//先取高价的k条路
	bn();//再取余下的路
	printf("%d\n",ans);		
	return 0;
}