1 问题：返回一个二维整数数组中最大联通子数组的和
2 思路：从文件中读取数组，通过将数组转化为无相连通图，再经过遍历找出子联通数组，求和
1 #include<iostream>
2 #include<fstream>
3 #include<ctime>
4 using namespace std;
5 #define N 100
6
7 typedef
struct
8 {
9 int dian[N];
10 int xian[N][N];
11 int dianx, xianx;
12 }A;
13
14 void set(A &shu,
int x,
int y, ifstream &
infile)
15 {
16 shu.dianx = x*
y;
17 srand((unsigned)time(NULL));
18 for (
int i =
1; i <= shu.dianx; i++
)
19 {
20 infile >>
shu.dian[i];
21 }
22 infile.close();
23 for (
int i =
1; i <= shu.dianx; i +=
y)
24 {
25 for (
int j = i; j <= i + y -
2; j++
)
26 {
27 shu.xian[j][j +
1] =
1;
28 shu.xian[j +
1][j] =
1;
29 }
30 }
31 for (
int i =
1 + y; i<shu.dianx; i +=
y)
32 {
33 for (
int j = i; j <= i + x -
1; j++
)
34 {
35 shu.xian[j][j - y] =
1;
36 shu.xian[j - y][j] =
1;
37 }
38 }
39 }
40 void numdian(A &Shu,
int &hangshu,
int &
lieshu)
41 {
42 ifstream infile(
"input.txt", ios::
in);
43 if (infile.is_open() ==
false)
44 {
45 cerr <<
"open error!" <<
endl;
46 exit(
1);
47 }
48 infile >> hangshu >>
lieshu;
49 set(Shu, hangshu, lieshu, infile);
50 }
51 void output(A shu)
52 {
53 for (
int i =
1; i <= shu.dianx; i++
)
54 {
55 cout <<
shu.dian[i];
56 if (shu.xian[i][i +
1] ==
1)
57 cout <<
" ";
58 else
59 cout <<
endl;
60 }
61 }
62 void bianli(A &shu,
int v,
int visit[],
int &b,
int &max,
int x)
63 {
64 visit[v] =
1;
65
66 max +=
shu.dian[v];
67 if (max >=
b)
68 b =
max;
69
70 int a =
0, bo =
0;
71 for (
int w =
1; w <= shu.dianx; w++
)
72 {
73 for (
int c =
1; c <= shu.dianx; c++
)
74 {
75 if ((visit[w] ==
0) && (shu.xian[c][w] ==
1) && (visit[c] ==
1))
76 {
77 a = w; bo =
1;
break;
78 }
79 }
80 if (bo ==
1)
81 break;
82 }
83 for (
int w =
1; w <= shu.dianx; w++
)
84 {
85 for (
int c =
1; c <= shu.dianx; c++
)
86 {
87 if ((visit[w] ==
0) && (shu.xian[c][w] ==
1) && (visit[c] ==
1))
88 {
89 if (shu.dian[a]<
shu.dian[w])
90 a =
w;
91 }
92 }
93 }
94 if (b + shu.dian[a]<
0)
95 {
96 shu.xian[v][a] =
0;
97 }
98 else
99 bianli(shu, a, visit, b, max, x);
100 }
101
102 int NoVisit(
int visit[], A shu)
103 {
104 int k =
0, i;
105 for (i =
1; i <= shu.dianx; i++
)
106 {
107 if (visit[i] ==
0)
108 {
109 k =
i;
110 break;
111 }
112 }
113 return k;
114 }
115
116 int main()
117 {
118 int hangshu, lieshu;
119 A shu;
120 numdian(shu, hangshu, lieshu);
121 output(shu);
122
123 int v =
1, b[N] = {
0 }, h =
0;
124 for (
int i =
1; i <= shu.dianx; i++
)
125 {
126 if (shu.dian[i]<
0)
127 {
128 b[i] =
shu.dian[i];
129 }
130 else
131 {
132 int visit[N] = {
0 };
133 int max =
0;
134 bianli(shu, i, visit, b[i], max, hangshu);
135 }
136 }
137
138 int max = b[
1];
139 for (
int i =
2; i <= shu.dianx; i++
)
140 {
141 if (b[i]>
max)
142 max =
b[i];
143 }
144 cout <<
"最大联通子数组的和为：" << max <<
endl;
145 }
View Code
此次结对编程队友为 李娜。
http://www.cnblogs.com/linanil/p/5360687.html
转载于:https://www.cnblogs.com/ning-JML/p/5360800.html
