其实我只是为了不让文字显示太多才写的摘要。

题目描述

原题链接

Slove

用Kruskal建立最小生成树（MST)

1.一级公路是一定要修的，而且最少为k个。所以，把所有的边先按一级公路权值从小到大排序。

2.连接前k个“安全边”，即在Kruskal算法中可以加入的边。

3.把后几条边，按二级公路的权值从小到大排序。

4.继续Kruskal。

Tips

1.为什么步骤3中排序直接忽略了一级公路的权值呢？

“一级公路上的车速快，但修路的花费要大一些（摘自题目描述的第六行）”也就是说对于同一条边，一般来说，一级公路的权值是要大于二级公路的，所以选二级一定不比选一级差（当然，此题有SJ,不影响结果的话，选一级也是可以的）。

2.在实际评测时，将只会有m-1行公路（我也不知道为啥要少一条）

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;  //标准开头
const int N=20010;
int n,m,k;  //同题
int f[N];  //f[i]——节点i的父节点
struct note{
	int u,r,c1,c2,num;
}d[N];  //同题，u，r——端点，num——序号
int s[N];  //记录每条边的情况
int ans;  //答案
int cnt;  //记录前k个安全边
bool cmp1(const note &a,const note &b){  //排序1
	return a.c1<b.c1;
}
bool cmp2(const note &a,const note &b){  //排序2
	return a.c2<b.c2;
}
int find(int h){
	if(h!=f[h]) f[h]=find(f[h]);
	return f[h];
}
int main()
{
	cin>>n>>k>>m;
	m--;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>d[i].u>>d[i].r>>d[i].c1>>d[i].c2;
		d[i].num=i;
	}
	sort(d+1,d+1+m,cmp1);
	for(int i=1;i<=m;i++){
		int x,y;
		x=find(d[i].u);
		y=find(d[i].r);
		if(x!=y){
			f[y]=x;
			ans=max(ans,d[i].c1);
			s[d[i].num]=1;
			cnt++;
		}
		if(cnt==k){
			k=i;
			break;
		}
	}
	sort(d+k+1,d+1+m,cmp2);
	for(int i=k+1;i<=m;i++){
		int x,y;
		x=find(d[i].u);
		y=find(d[i].r);
		if(x!=y){
			f[y]=x;
			ans=max(ans,d[i].c2);
			s[d[i].num]=2;
		}
	}
	cout<<ans<<endl;
	for(int i=1;i<=m;i++){  //完美输出
		if(s[i]>=1) cout<<i<<" "<<s[i]<<endl;
	}
	return 0;
}

话说为啥这么个题都是蓝的