MST

POJ-3026 Borg Maze

题目传送门: POJ 3026

题目大概意思是#是墙,不能走,S是起点,A是目标点,要求从S出发走到所有点,路径不可交叉,然后求最小的路径和。

就是一个BFS+MST的题,自己BFS写的有问题,真是够糟糕的。。。

POJ-最小生成树和拓扑排序基础问题

POJ 1258 Agri-Net

prim 裸题

POJ 1258
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//by Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
long long map[110][110], dist[110], n, ans;
bool vis[110];
void prim(long long u)
{
long long i, j, min, tmp;
ans = 0;
for(i = 1; i <= n; i++)
{
dist[i] = map[u][i];
vis[i] = false;
}
vis[u] = true;
tmp = u;
for(i = 1; i <= n; i++)
{
min =0x7FFFFFFF;
for(j = 1; j <= n; j++)
if(!vis[j] && min > dist[j])
{
tmp = j;
min = dist[j];
}
if(min != 0x7FFFFFFF)
ans += min;
vis[tmp] = true;
for(j = 1; j <= n; j++)
if(!vis[j] && dist[j] > map[tmp][j])
dist[j] = map[tmp][j];
}
}
int main()
{
long long i, j;
while(~scanf("%lld", &n))
{
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%lld", &map[i][j]);
prim(1);
printf("%lld\n",ans);
}
return 0;
}