整数数组中最大子数组求和04

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