poj-2485

/1356K172MSG++#include <stdio.h>#include <string.h>#define NODE_MAX 505int map[NODE_MAX][NODE_MAX];int key[NODE_MAX];int visited[NODE_MAX];int nodeNum;#define INF 999999void solve() {long distanceSum = 0;int maxDistance = -INF;for (int i = 0; i < nodeNum; i++) {key[i] = INF;visited[i] = 0;}key[0] = 0; // begin from 0for (int i = 1; i <= nodeNum; i++) {int minId = -1;int minDistance = INF;for (int j = 0; j < nodeNum; j++) {if (!visited[j]) {if (minDistance > key[j]) {minId = j;minDistance = key[j];}}}// minId Node is choosedvisited[minId] = 1;distanceSum += minDistance;maxDistance = maxDistance > minDistance ? maxDistance: minDistance;for (int j = 0; j < nodeNum; j++) { // update minId's adjaency nodeif (!visited[j] && map[minId][j] > 0) {key[j] = key[j] < map[minId][j] ? key[j] : map[minId][j];}}}// printf("%ld %d\n", distanceSum, maxDistance);printf("%d\n", maxDistance);}int main() {int caseNum;scanf("%d", &caseNum);for (int i = 0; i < caseNum; i++) {memset(map, 0, sizeof(map));memset(key, 0, sizeof(key));memset(visited, 0, sizeof(visited));scanf("%d", &nodeNum);for (int j = 0; j < nodeNum; j++) {for (int k = 0; k < nodeNum; k++) {int distance;scanf("%d", &distance);map[j][k] = distance;}}solve();}}

最小生成树基本题，没什么好说的.

只需要注意的是，问题要求的是最小生成树中最长的path的长度。刚开始看错贡献了次WA.

这个长度也很容易找到，就在Prim算法每次取新边时，可以根据大小更新。

然而，事实上，有一个问题，那就是，一张图片实际上可能有多个最小的生成树。

Prim最终得到的只有其中一个，而这棵树的最长path并不一定是所有生成树的最长path。

(但也有可能是伪问题，因为不同的树可能只是每个path的长度顺序不同， 比如树1: 1, 3 ,5, 树2: 3, 5, 1)

还要好好看看这部分的原理.

写Prim的时候总是和BellmanFord算法混淆，经常少循环一次，mark.

买一送一: 1258 基本不需要更改代码，输出总长度还可以，注意多个case，　检测scanf EOF.