P1547 [USACO05MAR]Out of Hay S
模板
/*
B1682 [Usaco2005 Mar]Out of Hay 干草危机
洛谷P1547 [USACO05MAR]Out of Hay S
====关键词===================================================
prim算法（最小生成树）
1.WA，没有加重复边的判断
2.加了重复边的判断，还是WA，但分数高了一点
3.照着别人AC的代码重写了逻辑，过了
====关键词===================================================
====题目===================================================
题目描述
Bessie 计划调查N（2≤N≤2000）个农场的干草情况，它从1 号农场出发。农场之间总共有
M（1≤M≤10^4）条双向道路，所有道路的总长度不超过10^9。有些农场之间存在着多条道路，所有的农场之间都是连通的。
Bessie 希望计算出该图中最小生成树中的最长边的长度。
输入格式
第 1 行输入两个整数N 和M; 接下来M 行，每行输入三个整数，表示一条道路的起点终点和长度。
输出格式
一个整数，表示最小生成树中的最长边的长度。
样例输入
Copy to Clipboard
3 3
1 2 23
2 3 1000
1 3 43
样例输出
Copy to Clipboard
43
由 1 到达 2，需要经过长度 23 的道路；回到 1 再到 3，通过长度 43 的道路．最长道路为 43
提示
没有写明提示
题目来源
Silver
====题目===================================================
*/
#include <iostream>
using namespace std;
const int INF = 0x7fffffff;
const int N = 2001; //农场数量上限
int a[N][N]; //地图矩阵
int n; //农场数量
int m; //边数量
int ans; //答案
// prim算法需要的变量
bool visited[N];
struct
{
int pre; //距离结点最近的，前面的结点
int dist; //最小生成树中该节点到pre结点距离
} closedge[N];
void showClosedgeVisited(); //显示伴随参数和visited[]
/*
prim算法
*/
void prim()
{
//初始化变量
for (int i = 1; i <= n; i++)
{
visited[i] = false;
closedge[i].pre = -1;
closedge[i].dist = INF;
}
//第一个结点直接写
closedge[1] = {-1, 0};
visited[1] = true;
for (int i = 1; i <= n; ++i) //更新1的临近结点
closedge[i].dist = a[i][1];
//之后执行n-1次操作
for (int kk = 1; kk <= n - 1; kk++)
{
//找到closedge[]中dist最小的结点，更新visited
int min_dist = INF;
int min_index = -1;
for (int j = 1; j <= n; j++)
{
if (!visited[j] && closedge[j].dist < min_dist)
{
min_dist = closedge[j].dist;
min_index = j;
}
}
visited[min_index] = true;
//更新答案
if (closedge[min_index].dist > ans) //更新答案
ans = closedge[min_index].dist;
//找相邻结点,更新closedge[]
for (int j = 1; j <= n; j++)
if (!visited[j] && a[min_index][j] < closedge[j].dist)
{ // j结点未确定最小距离&&j结点到已确定最小值的结点集合的距离应最小
closedge[j] = {min_index, a[min_index][j]};
}
}
}
int main()
{
//读数据
scanf("%d%d", &n, &m);
//图初始化
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
if (i != j)
a[i][j] = INF;
else
a[i][j] = 0;
}
while (m--)
{
int s, e, dis; //起点，终点，距离
scanf("%d%d%d", &s, &e, &dis);
if (s == e) //去掉环(本题好像没有环)
continue;
if (a[s][e] != 0 && dis > a[s][e]) //去掉重复边
continue;
a[s][e] = a[e][s] = dis;
}
//题解
prim();
// for (int i = 2; i <= n; i++)
// { //找到最小生成树中最长的边
// if (closedge[i].dist > ans)
// {
// ans = closedge[i].dist;
// }
// }
//输出结果
// showClosedgeVisited();
printf("%d\n", ans);
return 0;
}
void showClosedgeVisited()
{//便于调试
cout << "下标 ";
for (int i = 1; i <= n; i++)
{
cout << i << " ";
}
cout << endl;
cout << "visited ";
for (int i = 1; i <= n; i++)
{
cout << visited[i] << " ";
}
cout << endl;
cout << "index ";
for (int i = 1; i <= n; i++)
{
cout << closedge[i].pre << " ";
}
cout << endl;
cout << "dist ";
for (int i = 1; i <= n; i++)
{
cout << closedge[i].dist << " ";
}
cout << endl;
}