CCF-201812-4

题目描述

样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明　　
下图是样例说明。 

题目写的很具有迷惑性，但是认真分析就会发现，就是求图的最小生成树中权值最大的边。因为数据是通过流水线形式传输的，流水线耗时只受最长的瓶颈段影响，而最小生成树上最长的边显然就是瓶颈段。

我的做法是用邻接矩阵存储，然后用Prim算法求最小生成树。代码如下

#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define INF 100000000
#define nINF -100000000

int main() {
	int n;	//点的个数
	cin >> n;
	vector< vector<int> > adjMatrix;	//邻接矩阵
	for (int i = 0; i <= n; i++) {	//邻接矩阵初始化
		vector<int> line(n + 1, INF);	//第0行第0列不用
		adjMatrix.push_back(line);
	}
	int m, root;	//m:边的个数	root:根节点编号
	cin >> m >> root;
	for (int i = 0; i < m; i++) {
		int a, b, dis;
		cin >> a >> b >> dis;
		//因为是无向图，所以邻接矩阵对称
		adjMatrix[a][b] = dis;
		adjMatrix[b][a] = dis;
	}

	map<int, bool> visited;	//访问过的点
	int maxLength = nINF;	//由于流水线只受最长边的影响，所以只存储边集中最长边的长度即可
	visited.insert(pair<int, bool>(root, true));	//从root开始Prim算法
	while (visited.size() != n) {
		int minEdgeLength = INF;	//最小的到未达点的边长
		int minEdgeArrive = root;	//未达点编号
		for (map<int, bool>::iterator iter = visited.begin(); iter != visited.end(); iter++) {
			int start = iter->first;	//起点编号
			for (int i = 1; i <= n; i++) {
				if (adjMatrix[start][i] < minEdgeLength && (visited.count(i) == 0)) {	//如果到点i的距离比之前的小而且i不在visited里
					minEdgeLength = adjMatrix[start][i];
					minEdgeArrive = i;
				}
			}
		}
		visited.insert(pair<int, bool>(minEdgeArrive, true));
		if (minEdgeLength > maxLength) {
			maxLength = minEdgeLength;
		}
	}

	cout << maxLength;
	return 0;
}

但是这个方法只能拿一半的分数，观察下面的测试点信息，可以发现只有前两个测试点是稠密图而后面两个是稀疏图，因此这题的正确做法是用邻接表存储边，然后用 Kruskal （加边法）做，这样空间和时间都比我的算法好，即使前面两个图是稠密的，但因为数据量比较小，也不会超时，代码如下 （该代码转自CSDN Enjoy_process ）

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 500100;

struct Edge {
	int u, v, w;
	//按边权从小到大排序 
	bool operator<(const Edge& a)const
	{
		return w < a.w;
	}
}edge[N];

int pre[N];

void init(int n)
{
	for (int i = 0; i <= n; i++)
		pre[i] = i;
}

int find(int x)
{
	int r = x;
	while (r != pre[r])
		r = pre[r];
	//路径压缩 
	while (x != r)
	{
		int i = pre[x];
		pre[x] = r;
		x = i;
	}
	return r;
}

bool join(int x, int y)
{
	int fx = find(x);
	int fy = find(y);
	if (fx != fy)
	{
		pre[fx] = fy;
		return true;
	}
	return false;
}

int main()
{
	int n, m, root;
	scanf("%d%d%d", &n, &m, &root);
	for (int i = 0; i < m; i++)
		scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
	sort(edge, edge + m);
	int ans = 0, num = 0;//num记录添加的边数 
	init(n);
	for (int i = 0; i < m; i++)
	{
		//不构成环 
		if (join(edge[i].u, edge[i].v))
		{
			ans = edge[i].w;
			if (++num == n - 1)//添加n-1条边后就能形成树，退出 
				break;
		}
	}
	printf("%d\n", ans);
	return 0;
}