经典算法普及——基础篇

kon3155

接上贴： 1。根据算法1计算24点的代码

2. #include <iostream>
3. #include <string>
4. #include <cmath>
6. using namespace std;
8. const double PRECISION = 1E-6;
9. const int COUNT_OF_NUMBER = 4;
10. const int NUMBER_TO_CAL = 24;
12. double number[COUNT_OF_NUMBER];
13. string expression[COUNT_OF_NUMBER];
15. bool Search(int n)
16. {
17. if (n == 1) {
18. if ( fabs(number[0] - NUMBER_TO_CAL) < PRECISION ) {
19. cout << expression[0] << endl;
20. return true;
21. } else {
22. return false;
23. }
24. }
26. for (int i = 0; i < n; i++) {
27. for (int j = i + 1; j < n; j++) {
28. double a, b;
29. string expa, expb;
31. a = number[i];
32. b = number[j];
33. number[j] = number[n - 1];
35. expa = expression[i];
36. expb = expression[j];
37. expression[j] = expression[n - 1];
39. expression[i] = '(' + expa + '+' + expb + ')';
40. number[i] = a + b;
41. if ( Search(n - 1) ) return true;
43. expression[i] = '(' + expa + '-' + expb + ')';
44. number[i] = a - b;
45. if ( Search(n - 1) ) return true;
47. expression[i] = '(' + expb + '-' + expa + ')';
48. number[i] = b - a;
49. if ( Search(n - 1) ) return true;
52. expression[i] = '(' + expa + '*' + expb + ')';
53. number[i] = a * b;
54. if ( Search(n - 1) ) return true;
56. if (b != 0) {
57. expression[i] = '(' + expa + '/' + expb + ')';
58. number[i] = a / b;
59. if ( Search(n - 1) ) return true;
60. }
61. if (a != 0) {
62. expression[i] = '(' + expb + '/' + expa + ')';
63. number[i] = b / a;
64. if ( Search(n - 1) ) return true;
65. }
67. number[i] = a;
68. number[j] = b;
69. expression[i] = expa;
70. expression[j] = expb;
71. }
72. }
73. return false;
74. }
76. void main()
77. {
78. for (int i = 0; i < COUNT_OF_NUMBER; i++) {
79. char buffer[20];
80. int x;
81. cin >> x;
82. number[i] = x;
83. itoa(x, buffer, 10);
84. expression[i] = buffer;
85. }
87. if ( Search(COUNT_OF_NUMBER) ) {
88. cout << "Success." << endl;
89. } else {
90. cout << "Fail." << endl;
91. }
92. }

复制代码

2。根据算法2计算解决题目的程序代码：

3. #include <fstream>
4. #include <algorithm>
5. #include <string>
6. #include <sstream>
7. #include <list>
8. #include <cmath>
9. #include <climits>
10. #include <bitset>
11. using namespace std;
13. const char* INPUT_FILE = "game.in";
14. const char* OUTPUT_FILE = "game.out";
15. const int NUMBER_COUNT = 6;
16. const int STATE_COUNT = (1 << NUMBER_COUNT);
17. const int MAX_NUMBER = 100;
18. const int MAX_EXPECTION = 1000;
19. const int MAX_VALUE = MAX_EXPECTION * MAX_NUMBER;
21. struct Node {
22. int value;
23. int left, right;
24. int leftvalue, rightvalue;
25. char opr;
26. };
28. typedef list<Node> NodeList;
30. struct State {
31. bitset<MAX_VALUE+10> exist;
32. NodeList nodelist;
33. };
35. int number[NUMBER_COUNT], expection;
36. State state[STATE_COUNT];
38. void ReadData()
39. {
40. ifstream fin(INPUT_FILE);
42. for (int i = 0; i < NUMBER_COUNT; i++) {
43. fin >> number[i];
44. }
45. fin >> expection;
46. }
48. void Init()
49. {
50. Node node ;
51. for (int i = 0; i < NUMBER_COUNT; i++) {
52. node.value = number[i];
53. node.left = node.right = -1;
54. state[(1 << i)].nodelist.push_back(node);
55. state[(1 << i)].exist[node.value] = true;
56. }
57. }
59. void Merge(int a, int b, int x)
60. {
61. Node node;
62. NodeList::const_iterator i, j;
64. for (i = state[a].nodelist.begin(); i != state[a].nodelist.end();
65. i++) {
66. for (j = state[b].nodelist.begin(); j != state[b].nodelist.en
68. d(); j++)
69. {
70. node.value = (*i).value + (*j).value;
71. node.left = a;
72. node.right = b;
73. node.leftvalue = (*i).value;
74. node.rightvalue = (*j).value;
75. node.opr = '+';
76. if ( (node.value <= MAX_VALUE) && (!state[x].exist[no
78. de.value]) ) {
79. state[x].nodelist.push_back(node);
80. state[x].exist[node.value] = true;
81. }
83. /////////////////////////////////////////////////////
85. double tmp = double((*i).value) * double((*j).value);
87. if (tmp < INT_MAX) {
88. node.value = (*i).value * (*j).value;
89. node.left = a;
90. node.right = b;
91. node.leftvalue = (*i).value;
92. node.rightvalue = (*j).value;
93. node.opr = '*';
94. if ( (node.value <= MAX_VALUE) && (!state[x].
96. exist[node.value]) )
97. {
98. state[x].nodelist.push_back(node);
99. state[x].exist[node.value] = true;
100. }
101. }
103. /////////////////////////////////////////////////////
105. if ((*i).value >= (*j).value) {
106. node.value = (*i).value - (*j).value;
107. node.left = a;
108. node.right = b;
109. node.leftvalue = (*i).value;
110. node.rightvalue = (*j).value;
111. node.opr = '-';
112. } else {
113. node.value = (*j).value - (*i).value;
114. node.left = b;
115. node.right = a;
116. node.leftvalue = (*j).value;
117. node.rightvalue = (*i).value;
118. node.opr = '-';
119. }
121. if ( (node.value <= MAX_VALUE) && (!state[x].exist[no
123. de.value]) ) {
124. state[x].nodelist.push_back(node);
125. state[x].exist[node.value] = true;
126. }
128. /////////////////////////////////////////////////////
131. if ( ((*j).value != 0) && ((*i).value >= (*j).value) &
132. &
133. ((*i).value % (*j).value == 0) )
134. {
135. node.value = (*i).value / (*j).value;
136. node.left = a;
137. node.right = b;
138. node.leftvalue = (*i).value;
139. node.rightvalue = (*j).value;
140. node.opr = '/';
141. } else if ( ((*i).value != 0) && ((*j).value >= (*i).
143. value) &&
144. ((*j).value % (*i).value == 0) )
145. {
146. node.value = (*j).value / (*i).value;
147. node.left = b;
148. node.right = a;
149. node.leftvalue = (*j).value;
150. node.rightvalue = (*i).value;
151. node.opr = '/';
152. }
154. if ( (node.value <= MAX_VALUE) && (!state[x].exist[no
156. de.value]) )
157. {
158. state[x].nodelist.push_back(node);
159. state[x].exist[node.value] = true;
160. }
161. /////////////////////////////////////////////////////
163. }
164. }
165. }
167. void Solve()
168. {
169. Init();
171. for (int x = 2; x < STATE_COUNT; x++) {
172. for (int i = 1; i < x; i++) {
173. if ( (x & i) == i ) {
174. int j = x - i;
175. if (i <= j) {
176. Merge(i, j, x);
177. }
178. }
179. }
180. }
181. }
183. void PrintExpression(ostream& out, Node node)
184. {
185. if (node.left == -1) {
186. out << node.value;
187. } else {
188. NodeList::const_iterator iter;
190. out << "(";
192. for (iter = state[node.left].nodelist.begin();
193. iter != state[node.left].nodelist.end();
194. iter++)
195. {
196. if ((*iter).value == node.leftvalue) {
197. PrintExpression(out, *iter);
198. break;
199. }
200. }
202. out << node.opr;
204. for (iter = state[node.right].nodelist.begin();
205. iter != state[node.right].nodelist.end();
206. iter++)
207. {
208. if ((*iter).value == node.rightvalue) {
209. PrintExpression(out, *iter);
210. break;
211. }
212. }
214. out << ")";
215. }
216. }
218. void Output()
219. {
220. ofstream fout(OUTPUT_FILE);
222. int bestValue = -INT_MAX;
223. NodeList::const_iterator iter, bestIter;
225. NodeList& nodelist = state[STATE_COUNT-1].nodelist;
227. for (iter = nodelist.begin(); iter != nodelist.end(); iter++)
228. {
229. if ( ((*iter).value <= expection) && (bestValue < (*iter).val
231. ue) ) {
232. bestValue = (*iter).value;
233. bestIter = iter;
234. }
235. }
236. fout << bestValue << endl;
237. PrintExpression(fout, *bestIter );
238. fout << endl;
239. }
241. int main()
242. {
243. ReadData();
244. Solve();
245. Output();
246. return 0;
247. }

复制代码

kon3155

无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。 【Prim算法思想】 任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。 【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】 第一行两个数v(v<=200),e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。 　【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 　 【输出样例】 1 2 10 2 3 5 2 4 6 2 6 11 4 5 18 　 原 图 最小生成树

1. program prim_example;
2. Const
3. vmax=200
4. var
5. w:array[1..vmax,1..vmax]of integer;
6. i,j,k,v,e:integer;
7. procedure prim(v0:integer); {v0是开始结点}
8. var
9. flag:array[1..vmax] of boolean;
10. min,prevk,nextk:integer;
11. begin
12. fillchar(flag,sizeof(flag),false);
13. flag[v0]:=true; {先选出v0}
14. for i:=1 to v-1 do {一共寻找v-1条边}
15. begin
16. min:=maxint;
17. for k:=1 to v do
18. if flag[k] then {找已在集合中的顶点}
19. for j:=1 to v do {求满足条件的边的最小值}
20. if (not(flag[j])) and (w[k,j]<min) and (w[k,j]<>0)
21. then begin
22. min:=w[k,j]; {记下最小值}
23. nextk:=j;
24. prevk:=k;
25. end;
26. if min<>maxint
27. then begin
28. flag[nextk]:=true; {最小值对应顶点进入集合}
29. writeln(prevk,' ',nextk,‘ ',min);
30. end;
31. end;{for}
32. end;{prim}
33. begin
34. assign(input,'prim.in');
35. reset(input);
36. assign(output,'prim.out');
37. rewrite(output);
38. fillchar(w,sizeof(w),0);
39. readln(v,e);
40. for k:=1 to e do
41. begin
42. read(i,j);
43. readln(w[i,j]);
44. w[j,i]:=w[i,j];
45. end;
46. prim(1);
47. close(input);
48. close(output);
49. end.

复制代码

kon3155

设图G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权W(U,V)，在G中指定一个结点V0，要求从V0到G的每一个结点Vj的最短路径找出来（或指出不存在）。 由于源结点V0是给定的，所谓称为单源最短路径。 【Dijkstra算法思想】 把所有结点分为两组。 第一组：包含已确定最短路径的结点。 第二组：包含尚未确定最短路径的结点。 按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到V0可达的所有结点都包含于第一组中。在这个过程中，总保持从V0到第一组各结点的最短路径长度都不大于从V0到第二组任何结点的路径长度。 【单源最短路径算法实例】 现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。 【输入】 第一行一个整数v，代表城镇数，县城编号为1。 第二行是一个整数e，表示有向边数。 以下e行，每行为两个城镇编号和它们之间的公路造价。 【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路。 　【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 　 【输出样例】 1 2 2 3 2 4 1 5 1 6 原 图 从第1点出发的最短路径 【参考程序】

1. program dijkstra_example;
2. const
3. vmax=100;
4. type
5. path=record {此记录类型用于记录每一个结点与v0的距离和其父结点}
6. length:integer;
7. pre:0..vmax;
8. end;
9. var
10. w:array[1..vmax,1..vmax] of integer;
11. dist:array[1..vmax] of path;
12. v,e,u,i,j,x,y:integer;
13. procedure init;
14. begin
15. assign(input,'dijkstra.in');
16. reset(input);
17. assign(output,'dijkstra.out');
18. rewrite(output);
19. readln(v);
20. readln(e);
21. for i:=1 to v do
22. for j:=1 to v do
23. if i<>j
24. then w[i,j]:=30000
25. {30000只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充分大的数}
26. else w[i,j]:=0;
27. for i:=1 to e do
28. begin
29. read(x,y);
30. readln(w[x,y]);
31. w[y,x]:=w[x,y];
32. end;
33. end;
34. procedure dijkstra(v0:integer);
35. var
36. min:integer;
37. begin
38. w[v0,v0]:=1; {v0首先进入第一组}
39. for i:=1 to v do
40. begin
41. dist[i].length:=w[v0,i]; {计算每个结点的距离值}
42. if dist[i].length<>30000
43. then dist[i].pre:=v0 {如和v0直接有路，则置前驱结点为v0}
44. else dist[i].pre:=0;
45. end;
46. repeat
47. min:=30000;
48. u:=0;
49. for i:=1 to v do {找最短距离}
50. if (w[i,i]=0) and (dist[i].length<min)
51. then begin
52. u:=i;
53. min:=dist[i].length;
54. end;
55. if u<>0
56. then begin
57. w[u,u]:=1;
58. for i:=1 to v do {重新计算其他结点的距离值}
59. if (w[i,i]=0) and (dist[i].length>dist[u].length+w[u,i])
60. then begin
61. dist[i].length:=dist[u].length+w[u,i];
62. dist[i].pre:=u;
63. end;
64. end;
65. until u=0;
66. end;
67. begin
68. init;
69. v0:=1;
70. dijkstra(v0);
71. for i:=1 to v do
72. begin
73. if (i<>v0) and (dist[i].length<>30000)
74. then write(dist[i].pre,' ',i);
75. end;
76. close(input);
77. close(output);
78. end.

复制代码

kon3155

设图G=(V,E)是一个有向图,对于每对结点(U,V),找出从U到V的最短路径。 【Floyd算法思想】 利用一个三重循环产生一个存储每个结点最短距离的矩阵. 【Floyd算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离 【输入】 第一行两个数v,e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权。 【输出】 所有可能连接的城市的最短距离。 　【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】 1 2 10 1 3 15 1 4 16 1 5 19 1 6 21 2 3 5 2 4 6 2 5 24 2 6 11 3 4 6 3 5 24 3 6 16 4 5 18 4 6 14 5 6 32 【参考程序】

1. program floyd_example;
2. const
3. maxn=10;
4. var
5. n,s,t,i,j:integer;
6. dist:array[1..maxn,1..maxn] of real;
7. prev:array[1..maxn,1..maxn] of 0..maxn;
8. procedure init;
9. var
10. m,i,u,v:integer;
11. begin
12. assign(input,'floyd.in');
13. reset(input);
14. assign(output,'floyd.out');
15. rewrite(output);
16. readln(n,m);
17. fillchar(prev,sizeof(prev),0);
18. for u:=1 to n do
19. for v:=1 to n do
20. dist[u,v]:=1e10;
21. for i:=1 to m do
22. begin
23. readln(u,v,dist[u,v]);
24. dist[v,u]:=dist[u,v];
25. prev[u,v]:=u;
26. prev[v,u]:=v;
27. end;
28. end;{init}
29. procedure floyd;
30. var
31. i,j,k:integer;
32. begin
33. for k:=1 to n do
34. for i:=1 to n do
35. for j:=1 to n do
36. if (dist[i,k]+dist[k,j]<dist[i,j])
37. then begin
38. dist[i,j]:=dist[i,k]+dist[k,j];
39. prev[i,j]:=prev[k,j];
40. end;
41. end;{floyd}
42. procedure print(i,j:integer);
43. begin
44. if i=j
45. then write(i)
46. else if prev[i,j]=0
47. then write('No Solution!')
48. else begin
49. print(i,prev[i,j]);
50. write('->',j);
51. end;
52. end;{print}
53. begin
54. init;
55. floyd;
56. for i:=1 to n do
57. for j:=i+1 to n do
58. begin
59. write(i,' ',j,' ');
60. write(dist[i,j]:0:0,' ');
61. print(i,j);
62. writeln;
63. end;
64. close(input);
65. close(output);
66. end.

复制代码

kon3155

求有向图的所有环,此问题包括了求最大环或者最小环。 【输入】 第一行两个数v,e，分别代表图的顶点数和边数，以下e行，每行为有连接的两个顶点和权。 【输出】 顶点编号和环的长度以及包含该顶点的环的路径。 　【输入样例】 huan.in 5 7 1 2 2 2 1 1 2 5 4 3 2 5 3 4 7 4 1 3 5 4 6 　 【输出样例】 huan.out 1 3 1->2 2 3 2->1 4 15 4->1->2->5 5 15 5->4->1->2 【参考程序】

1. program huan;
2. const
3. maxn=90;
4. var
5. n,s,t,i,j:integer;
6. dist:array[1..maxn,1..maxn] of real;
7. prev:array[1..maxn,1..maxn] of 0..maxn;
8. procedure init;
9. var
10. m,i,u,v:integer;
11. begin
12. assign(input,'huan.in');
13. reset(input);
14. assign(output,'huan.out');
15. rewrite(output);
16. readln(n,m);
17. fillchar(prev,sizeof(prev),0);
18. for u:=1 to n do
19. for v:=1 to n do
20. dist[u,v]:=1e10;
21. for i:=1 to m do
22. begin
23. readln(u,v,dist[u,v]);
24. prev[u,v]:=u;
25. end;
26. end;
27. procedure floyd;
28. var
29. i,j,k:integer;
30. begin
31. for k:=1 to n do
32. for i:=1 to n do
33. for j:=1 to n do
34. if (dist[i,k]+dist[k,j]<dist[i,j])
35. then begin
36. dist[i,j]:=dist[i,k]+dist[k,j];
37. prev[i,j]:=prev[k,j];
38. end;
39. end;{floyd}
40. procedure print(i,j:integer);
41. begin
42. if i=j
43. then write(i)
44. else if prev[i,j]=0
45. then write('No Circle!')
46. else begin
47. print(i,prev[i,j]);
48. write('->',j);
49. end;
50. end;{print}
51. begin
52. init;
53. floyd;
54. for i:=1 to n do
55. begin
56. if dist[i,i]<>1e10
57. then
58. begin
59. write(i,' ');
60. write(dist[i,i]:0:0,' ');
61. print(i,prev[i,i]);
62. writeln;
63. end;
64. end;
65. close(input);
66. close(output);
67. end.

复制代码

kon3155

Dijkstra算法中要求边的权非负，如果遇到负权，则可以采用Bellman-Ford算法。 【Bellman-Ford算法思想】 【Bellman-Ford算法实例】 　【输入样例】 6 10 1 2 -10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 -6 4 5 18 4 6 14 5 6 -33 1 4　 【输出样例】 length=-11 1->2->3->4 【参考程序】

2. program bellman_ford;
3. const
4. maxn=30;
5. var
6. n,s,t:integer;
7. dist:array[1..maxn] of real;
8. w:array[1..maxn,1..maxn] of real;
9. pre:array[1..maxn] of integer;
10. vis:array[1..maxn] of boolean;
11. procedure init;
12. var
13. m,i,u,v:integer;
14. begin
15. assign(input,'bellford.in');
16. reset(input);
17. assign(output,'bellford.out');
18. rewrite(output);
19. readln(n,m);
20. for u:=1 to n do
21. for v:=1 to n do
22. w[u,v]:=1e38;
23. for i:=1 to m do
24. readln(u,v,w[u,v]);
25. readln(s,t); {求结点s和结点t的最短距离和路径}
26. end;{init}
27. procedure bellford;
28. var
29. i,j:integer;
30. change:boolean;
31. begin
32. for i:=1 to n do
33. dist[i]:=1e38;
34. dist[s]:=0;
35. repeat
36. change:=false; {记录递推序列是否改变}
37. for i:=1 to n do
38. for j:=1 to n do
39. if dist[i]+w[i,j]<dist[j]
40. then begin
41. dist[j]:=dist[i]+w[i,j];
42. pre[j]:=i;
43. change:=true;
44. end;
45. until not change;
46. end;{bellford}
47. procedure out(s,t:integer);
48. var
49. k,length,i:integer;
50. path:array[1..maxn] of integer;
51. begin
52. if (dist[t])>1e38
53. then writeln('No solutin.')
54. else begin
55. length:=0;
56. k:=t;
57. while (k<>s) do
58. begin
59. inc(length);
60. path[length]:=k;
61. k:=pre[k];
62. end;
63. writeln('length=',dist[t]:0:0);
64. write(s);
65. for i:=length downto 1 do
66. write('->',path[i]);
67. writeln;
68. end;
69. end;{out}
70. begin
71. init;
72. bellford;
73. out(s,t);
74. end.

复制代码

kon3155

输入一张无向图，指出该图中哪些结点对之间有路。该问题通常采用传递闭包的计算方法。 【输入】 n(顶点数，1≤n≤20) e(边数，1≤e≤210) 以下e行，每行为有边连接的一对顶点 【输出】 k行，每行两个数，为存在通路的顶点对序号i,j(i 【输出样例】 1 4 1 5 1 6 2 3 4 5 4 6 5 6

1. program bibao_example;
2. const
3. maxv=20;
4. var
5. link,longlink:array[1..maxv,1..maxv] of boolean;
6. v,e,k,i,j:integer;
7. procedure init;
8. begin
9. assign(input,'bibao.in');
10. reset(input);
11. assign(output,'bibao.out');
12. rewrite(output);
13. fillchar(longlink,sizeof(longlink),0);
14. fillchar(link,sizeof(link),0);
15. readln(v);
16. readln(e);
17. for k:=1 to e do
18. begin
19. readln(i,j);
20. link[i,j]:=true; {因为没有权，所以有布尔型表示连通关系，能提高运算速度}
21. link[j,i]:=true;
22. end;
23. end;{init}
24. procedure bibao;
25. begin
26. longlink:=link;
27. for k:=1 to v do {枚举中间顶点}
28. for i:=1 to v do {枚举所有顶点对}
29. for j:=1 to v do {计算顶点i和顶点j的连通情况}
30. longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]);
31. end;{bibao}
32. procedure out;
33. begin
34. for i:=1 to v-1 do
35. for j:=i+1 to v do
36. if longlink[i,j]
37. then writeln(i,' ',j);
38. end;{out}
39. begin{main}
40. init;
41. bibao;
42. out;
43. close(input);
44. close(output);
45. end.

复制代码

kon3155

在一张顶点带权的无向图中，计算含顶点数最多的一个连通分支和顶点权和最大的连通分支。 【输入】 n(顶点数，1≤n≤20) 以下n行，其中第i行是顶点i的权 e(边数，1≤e≤210) 以下e行，每行为有边连接的一对顶点 【输出】 含顶点数最多的一个连通分支 顶点权和最大的一个连通分支 　【输入样例】 6 2 10 20 8 5 7 5 1 5 1 6 2 3 4 6 5 6 　 【输出样例】 1->5->6->4-> 2->3->

1. program liantong_example;
2. const
3. maxv=20;
4. var
5. link,longlink:array[1..maxv,1..maxv] of boolean;
6. f:array[1..maxv] of boolean;
7. w:array[1..maxv] of integer;
8. v,e,k,i,j,s,best,besti,max,maxk:integer;
9. procedure init;
10. begin
11. assign(input,'liantong.in');
12. reset(input);
13. assign(output,'liantong.out');
14. rewrite(output);
15. fillchar(longlink,sizeof(longlink),0);
16. fillchar(link,sizeof(link),0);
17. readln(v);
18. for i:=1 to v do
19. readln(w[i]);
20. readln(e);
21. for k:=1 to e do
22. begin
23. readln(i,j);
24. link[i,j]:=true;
25. link[j,i]:=true;
26. end;
27. end;{init}
28. procedure bibao;
29. begin
30. longlink:=link;
31. for k:=1 to v do
32. for i:=1 to v do
33. for j:=1 to v do
34. longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]);
35. end;{bibao}
36. procedure dfs(i:integer); {深度优先搜索，用于输出路径}
37. begin
38. write(i,'->');
39. f[i]:=true;
40. for j:=1 to v do
41. if (not f[j]) and longlink[i,j]
42. then dfs(j);
43. end;{dfs}
44. begin{main}
45. init;
46. bibao;
47. for i:=1 to v do
48. begin
49. k:=0;s:=0;
50. for j:=1 to v do {计算顶点i所在连通分支中的顶点总数和顶点的权和}
51. if longlink[i,j]
52. then begin
53. k:=k+1;
54. s:=s+w[j];
55. end;
56. if k>best {求出顶点数的最大值}
57. then begin
58. best:=k;
59. besti:=i;
60. end;
61. if s>max {求出顶点权和的最大值}
62. then begin
63. max:=s;
64. maxk:=i;
65. end;
66. if k=v then break;
67. end;
68. fillchar(f,sizeof(f),false); {结点是否访问数组初始化}
69. dfs(besti);
70. writeln;
71. fillchar(f,sizeof(f),false);
72. dfs(maxk);
73. close(input);
74. close(output);
75. end.

复制代码

kon3155

所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下： 给出有向图G=（V，E），若结点的线形序列V1,V2,...Vn满足条件：对于i,j(1≤jp2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD 【输入】 k行，每行a b，表示a>b 【输出】 一个可行的排队方案 【输入样例】 A B B D F D　 【输出样例】 ABFD 　

1. program soldier_sort;
2. var
3. w:array['A'..'Z','A'..'Z'] of 0..1;
4. d:array['A'..'Z'] of integer; {记录顶点入度的数组}
5. s:set of 'A'..'Z';
6. a,b,ch:char;
7. m,n:string;
8. i,j,k:integer;
9. begin
10. assign(input,'tuopu.in');
11. reset(input);
12. assign(output,'tuopu.out');
13. rewrite(output);
14. s:=[];
15. while not eof(input) do
16. begin
17. readln(a,ch,b);
18. s:=s+[a,b]; {计算士兵名集合}
19. w[a,b]:=1;
20. d[b]:=d[b]+1; {累计顶点b的入度}
21. end;
22. m:='';
23. for a:='A' to 'Z' do
24. if a in s
25. then m:=m+a; {产生士兵名字符集}
26. k:=length(m); {求得士兵人数}
27. n:=''; {拓扑序列初始为空}
28. for i:=1 to k do
29. begin
30. j:=1;
31. while (d[m[j]]>0) and (j<=k) do {搜索第i个入度为0的士兵的顶点序号j}
32. j:=j+1;
33. if j>k {若不存在入度为0的顶点，则无法拓扑排序失败}
34. then begin
35. writeln('Fault!');
36. break;
37. end;
38. n:=n+m[j]; {入度为0的顶点进入拓扑序列n}
39. a:=m[j]; {删去顶点j}
40. d[a]:=maxint;
41. for j:=1 to k do {与a相连的顶点入度减1}
42. if w[a,m[j]]>0
43. then d[m[j]]:=d[m[j]]-1;
44. end;{for}
45. writeln(n);
46. close(input);
47. close(output);
48. end.

复制代码

kon3155

某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N<1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。 【输入】network.in 输入文件的第一行为一个正整数N(1≤N≤100)。 接下来N行，每行2个数U,V ，表示坐标。 【输出】network.out 输出最短路径距离（保留两位小数） 【样例数据】 【输入】 5 0 0 0 1 0 -1 1 0 -1 0 【输出】 4.00 【参考程序查看】