题目描述

城市 C 是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的:城市中有 \(n\)
个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

  1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
  2. 在满足要求 1 的情况下,改造的道路尽量少。
  3. 在满足要求 1、2 的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择哪些道路应当被修建。

输入格式

第一行有两个整数 \(n,m\) 表示城市有 \(n\) 个交叉路口,\(m\) 条道路。

接下来 \(m\) 行是对每条道路的描述,\(u, v, c\) 表示交叉路口 \(u\)\(v\) 之间有道路相连,分值为 \(c\)

输出格式

两个整数 \(s, \mathit{max}\),表示你选出了几条道路,分值最大的那条道路的分值是多少。

样例 #1

样例输入 #1

4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8

样例输出 #1

3 6

提示

数据范围及约定

对于全部数据,满足 \(1\le n\le 300\)\(1\le c\le 10^4\)\(1 \le m \le 10^5\)

题目很长,但是题很简单
首先读题,要求每个路口都需要连通,且连通的路径数量最小,显然,这一定是一棵树,然后继续读题,要求最大值最小,即选择的路径长度和最小。这就是一道最小生成树的模板题

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[305];
struct edge{
	int u;
	int v;
	int w;
	friend bool operator > (edge r,edge c){
		return r.w>c.w;
	}
};
int findfa(int a){
	if(fa[a]==a){
		return a;
	}
	else{
		return fa[a]=findfa(fa[a]);
	}
}
void hebing(int a,int b){
	fa[findfa(a)]=findfa(b);
}
priority_queue<edge,vector<edge>,greater<edge> > q;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	edge temp;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&temp.u,&temp.v,&temp.w);
		q.push(temp);
	}
	cout<<n-1<<" ";
	int times=0,mmax=-1;
	edge t;
	while(times<n-1){
		t=q.top();
		q.pop();
		if(findfa(t.u)!=findfa(t.v)){
			mmax=t.w;
			hebing(t.u,t.v);
			times++;
		}
	}
	cout<<mmax;
	return 0;
}
//4 5
//1 2 3
//1 4 5
//2 4 6
//2 3 7
//3 4 8

这里我用了kruskar算法来构造最小生成树,即每次在所有的边里面选取长度最小的,但同时这条边需要满足连接的两点不在同一个集合里面
这里需要运用并查集

复习一下

并查集在使用之前需要初始化,将每一个元素的父亲改为自己
并查集有两个函数,分别是findfa和hebing
第一个是找到其父亲,同时进行路径压缩
第二个是将两个并查集合并,形成一个并查集

int findfa(int a){
	if(fa[a]==a){
		return a;
	}
	else{
		return fa[a]=findfa(fa[a]);
	}
}
void hebing(int a,int b){
	fa[findfa(a)]=findfa(b);
}

我们每次从优先队列里面取出最小的边,并且判断这条边是否连接的是两个不同的并查集,如果是,我们就选中它。
我们一共要选n-1条边,这样构建出来的才是一棵树。选完后,我们只需要记录下最后的那条边的长度,这就是答案

总结

这是一道模板题,复习了最小生成树的kruskar算法,同时也复习了并查集的算法

原文地址:http://www.cnblogs.com/GXYZY/p/16869412.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性