网站建设番禺,html怎么下载安装,360建网站,网站改版会降权吗四道MST#xff0c;适合Prim解法#xff0c;也可以作为MST练习题。 题意包括在代码中。 POJ1258-Agri Net 水题 1 //Prim-没什么好说的2 //接受一个邻接矩阵#xff0c;求MST3 //Time:0Ms Memory:220K4 #includeiostream5 #includecstring6 #include… 四道MST适合Prim解法也可以作为MST练习题。 题意包括在代码中。 POJ1258-Agri Net 水题 1 //Prim-没什么好说的2 //接受一个邻接矩阵求MST3 //Time:0Ms Memory:220K4 #includeiostream5 #includecstring6 #includecstdio7 #includealgorithm8 using namespace std;9 #define MAX 105
10 #define INF 0x3f3f3f3f
11 int n, m;
12 int d[MAX][MAX];
13 int lowcost[MAX];
14 bool v[MAX];
15 void prim()
16 {
17 int minroad 0;
18 memset(v, false, sizeof(v));
19 v[0] true;
20 for (int i 1; i n; i)
21 lowcost[i] d[i][0];
22 for (int i 1; i n; i)
23 {
24 double mind INF;
25 int k;
26 for (int j 1; j n; j)
27 {
28 if (!v[j] mind lowcost[j])
29 {
30 mind lowcost[j];
31 k j;
32 }
33 }
34
35 minroad lowcost[k];
36 v[k] true;
37 for (int j 1; j n; j)
38 if (!v[j]) lowcost[j] min(d[k][j], lowcost[j]);
39 }
40 printf(%d\n, minroad);
41 }
42 int main()
43 {
44 while (scanf(%d, n) ! EOF)
45 {
46 for (int i 0; i n; i)
47 for (int j 0; j n; j)
48 scanf(%d, d[i][j]);
49 prim();
50 }
51 return 0;
52 } POJ1751(ZOJ2048)-Highways 1 //Prim-好题2 //ZOJ2048-POJ17513 //ZOJ中多组样例两个样例间有一个空格(否则会WA)4 //需要记录上一个节点-注意内存限制在10^4K内5 //有M个城市已经有通路输出让N个城市生成最短通路的各边Special Judge-输出次序不定6 //Time:94Ms Memory:4648K7 #includeiostream8 #includecstring9 #includecstdio
10 #includecmath
11 #includealgorithm
12 using namespace std;
13
14 #define MAX 755
15 #define INF 0x3f3f3f3f
16 #define POW2(x) ((x)*(x))
17 #define DIS(i,j) (sqrt(POW2(p[i][0] - p[j][0]) POW2(p[i][1] - p[j][1])))
18
19 int n, m;
20 double p[MAX][2];
21 int fa[MAX]; //记录上一个顶点
22 double d[MAX][MAX];
23 double lowcost[MAX];
24 bool v[MAX];
25
26 void prim()
27 {
28 memset(v, false, sizeof(v));
29 v[1] true;
30 for (int i 2; i n; i)
31 {
32 lowcost[i] d[i][1];
33 fa[i] 1;
34 }
35 for (int i 2; i n; i)
36 {
37 double mind INF;
38 int k;
39 for (int j 2; j n; j)
40 {
41 if (!v[j] mind lowcost[j])
42 {
43 mind lowcost[j];
44 k j;
45 }
46 }
47 if (mind 1e-5)
48 printf(%d %d\n, fa[k], k);
49
50 v[k] true;
51 for (int j 2; j n; j)
52 {
53 if (!v[j] lowcost[j] d[k][j])
54 {
55 lowcost[j] d[k][j];
56 fa[j] k;
57 }
58 }
59 }
60 }
61
62 int main()
63 {
64 scanf(%d, n);
65 for (int i 1; i n; i)
66 {
67 scanf(%lf%lf, p[i][0], p[i][1]);
68 for (int j 1; j i; j)
69 d[i][j] d[j][i] DIS(i, j);
70 }
71 scanf(%d, m);
72 for (int i 0; i m; i)
73 {
74 int v1, v2;
75 scanf(%d%d, v1, v2);
76 d[v1][v2] d[v2][v1] 0;
77 }
78 prim();
79 return 0;
80 } POJ2349(ZOJ1914)-Arctic Network 1 //Prim2 //POJ2349-ZOJ19143 //有n个前哨可以通过卫星通信(无距离限制)总共m个前哨相互通信可以通过无线电通信(有距离限制),求所需无线电信号最短距离4 //定理如果去掉所有权值大于d的边后最小生成树被分割成为k个连通支图也被分割成为k个连通支(可尝试证明)5 //Time:47Ms Memory:2164K6 #includeiostream7 #includecstring8 #includecstdio9 #includecmath
10 #includealgorithm
11 using namespace std;
12
13 #define MAX 501
14 #define INF 0x3f3f3f3f
15 #define POW2(x) ((x)*(x))
16 #define DIS(i,j) (sqrt(POW2(p[i][0] - p[j][0]) POW2(p[i][1] - p[j][1])))
17
18 int n, m;
19 double p[MAX][2]; //point
20 double d[MAX][MAX]; //distance
21 double lowcost[MAX];
22 bool v[MAX];
23
24 void prim()
25 {
26 memset(lowcost, 0, sizeof(lowcost));
27 memset(v, false, sizeof(v));
28 v[0] true;
29 for (int i 1; i m; i)
30 lowcost[i] d[i][0];
31 for (int i 1; i m; i)
32 {
33 int mind INF;
34 int k;
35 for (int j 1; j m; j)
36 {
37 if (!v[j] mind lowcost[j])
38 {
39 mind lowcost[j];
40 k j;
41 }
42 }
43 v[k] true;
44 for (int j 1; j m; j)
45 if(!v[j]) lowcost[j] min(d[k][j], lowcost[j]);
46 }
47 }
48
49 int main()
50 {
51 int T;
52 scanf(%d, T);
53 while (T--)
54 {
55 scanf(%d%d, n, m);
56 for (int i 0; i m; i)
57 {
58 scanf(%lf%lf, p[i][0], p[i][1]);
59 for (int j 0; j i; j)
60 d[i][j] d[j][i] DIS(i, j);
61 }
62
63 prim();
64 sort(lowcost, lowcost m);
65 printf(%.2lf\n, lowcost[m - n]);
66 //G需要使用printf(%.2f\n, lowcost[m-n]);
67 //原因查了半天好像是因为新版GCC标准中将%f和%lf合并为%f的意思
68 }
69 return 0;
70 } POJ3026-Borg Maze 1 //PrimBFS2 //总是心想着要创造一个新算法结果越想越麻烦...3 //保险做法:找出每个点间的距离再进行Prim4 //Time:79Ms Memory:292K5 #includeiostream6 #includecstring7 #includecstdio8 #includequeue9 #includealgorithm10 using namespace std;11 12 #define MAX 125 //MAX 50的话会RE或WA(博主在55RE在100WA)13 14 struct Point{15 int x, y;16 int step;17 }p;18 19 int r, c;20 char board[MAX][MAX];21 int d[MAX][MAX];22 int num[MAX][MAX], cnt;23 int lowcost[MAX];24 bool v[MAX][MAX];25 int mov[4][2] { {1,0}, {-1,0}, {0,1}, {0,-1} };26 27 void bfs(Point p)28 {29 memset(v, false, sizeof(v));30 v[p.x][p.y] true;31 int np num[p.x][p.y];32 queuePoint q;33 p.step 0;34 q.push(p);35 while (!q.empty())36 {37 Point cur q.front();38 q.pop();39 for (int i 0; i 4; i)40 {41 Point t cur;42 t.x mov[i][0];43 t.y mov[i][1];44 if (t.x 0 t.y 0 t.x r t.y c !v[t.x][t.y])45 {46 if (board[t.x][t.y] #) continue;47 int nt num[t.x][t.y];48 t.step;49 v[t.x][t.y] true;50 if (board[t.x][t.y] A || board[t.x][t.y] S)51 d[nt][np] t.step;52 q.push(t);53 }54 }55 }56 }57 58 void prim()59 {60 int v[MAX];61 memset(v, false, sizeof(v));62 memset(lowcost, 0x3f, sizeof(lowcost));63 v[0] true;64 for (int i 1; i cnt; i)65 lowcost[i] d[i][0];66 67 int minv 0;68 for (int i 1; i cnt; i)69 {70 int mind 0x3f3f3f3f;71 int k;72 for (int j 1; j cnt; j)73 {74 if (!v[j] mind lowcost[j])75 {76 mind lowcost[j];77 k j;78 }79 }80 minv mind;81 v[k] true;82 for (int j 1; j cnt; j)83 if (!v[j]) lowcost[j] min(lowcost[j], d[k][j]);84 }85 printf(%d\n, minv);86 }87 88 int main()89 {90 int T;91 scanf(%d, T);92 while (T--)93 {94 cnt 0;95 scanf(%d%d, c, r);96 gets_s(board[0]);97 for (int i 0; i r; i)98 {99 gets_s(board[i], MAX);
100 for (int j 0; j c; j)
101 if (board[i][j] S || board[i][j] A)
102 num[i][j] cnt;
103 }
104 for (int i 0; i r; i)
105 for (int j 0; j c;j)
106 if (board[i][j] S || board[i][j] A)
107 {
108 p.x i; p.y j;
109 bfs(p);
110 }
111 prim();
112 }
113 return 0;
114 } 转载于:https://www.cnblogs.com/Inkblots/p/5380599.html
