题目:
提示:
Floyd最短路径算法实现(未测试):
//
// main.cpp
// Alg_Floyd_playgame
//
// Created by wasdns on 16/11/19.
// Copyright ? 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <string.h>
using namespace std;
#define endless 1000000001;
int Floydgh[5005][5005];
void Inigh(int n)
{
for (int i = 1; i <= n; i++)
{
Floydgh[i][i] = 0;
for (int j = 1; j <= n; j++)
{
if (i != j) {
Floydgh[i][j] = endless;
}
}
}
}
void Creatgh(int n, int m)
{
Inigh(n);
int i, u, v, w;
for (i = 1; i <= m; i++)
{
cin >> u >> v >> w;
Floydgh[u][v] = w;
Floydgh[v][u] = w;
}
}
void Alg_Floyd(int n)
{
int i, j, k;
for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
int t = Floydgh[i][k] + Floydgh[k][j];
if (t < Floydgh[i][j]) {
Floydgh[i][j] = t;
Floydgh[j][i] = t;
}
}
}
}
}
int minjudge(int n)
{
int i, j;
int minlen = endless;
for (i = 1; i <= n; i++)
{
int cnt = 0;
for (j = 1; j <= n; j++)
{
cnt += Floydgh[i][j];
}
if (cnt < minlen) {
minlen = cnt;
}
}
return minlen;
}
int main()
{
int n, m;
cin >> n >> m;
Creatgh(n, m);
Alg_Floyd(n);
cout << minjudge(n) << endl;
return 0;
}
Prim生成树算法实现:
关于Prim算法,请参考我的另外一篇博客:hdoj-1233-还是畅通工程
//
// main.cpp
// Prim
//
// Created by wasdns on 16/11/24.
// Copyright © 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#define maxn 10000005;
using namespace std;
int Primgh[10000][10000];
bool refer[10005];
void Initial(int n, int m)
{
int i, j;
for (i = 1; i <= n; i++)
{
refer[i] = false;
for (j = 1; j <= n; j++)
{
if (i == j) {
Primgh[i][j] = 0;
}
else Primgh[i][j] = maxn;
}
}
int u, v, w;
for (i = 1; i <= m; i++)
{
cin >> u >> v >> w;
Primgh[u][v] = w;
Primgh[v][u] = w;
}
}
int Prim_Alg(int n, int m)
{
Initial(n, m);
int i, j, k;
int ans = 0;
refer[1] = true; //起点为1
for (i = 1; i <= n-1; i++)
{
int minlen = maxn;
int rcd = 1;
for (j = 1; j <= n; j++)
{
if (!refer[j]) continue;
int len1 = maxn;
int rcd1 = 1;
for (k = 1; k <= n; k++)
{
if (!refer[k])
{
if (Primgh[j][k] < len1) {
len1 = Primgh[j][k];
rcd1 = k;
}
}
}
if (len1 < minlen) {
minlen = len1;
rcd = rcd1;
}
}
//char check = 'A'+rcd-1;
//cout << "rcd: " << check << endl;
//cout << "minlen: " << minlen << endl;
refer[rcd] = true;
rcd = 1;
ans += minlen;
}
return ans;
}
int main()
{
int n, m;
cin >> n >> m;
cout << Prim_Alg(n, m) << endl;
return 0;
}
测试样例:
/*
eg1.
Input:
4 6
1 2 1
2 3 2
1 3 3
2 4 3
3 4 5
1 4 4
Output:
6
eg2.
Input:
7 11
1 2 7
1 4 5
2 4 9
2 3 8
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11
Output:
39
*/
2016/11/24