这个中国邮路问题不太懂，有人帮我解释一下吗
#include <limits.h>#include <iostream>
#include <cstdlib>
#include <set>
#include <vector>
using namespace std;
#define MAX_NODE 26
#define COST_NO_LINK INT_MAX
int Graph[MAX_NODE][MAX_NODE];
int Cost[MAX_NODE][MAX_NODE];
int V_dingdianshu, E_bianshu, Start_Point;
int Odd_Grouping[MAX_NODE];
int Bak_Odd_Grouping[MAX_NODE];
int SHORTEST_PATH_WEIGHT(COST_NO_LINK);
int Dist[MAX_NODE];
int ShortCache[MAX_NODE][MAX_NODE];
void Input()//构造图
{
int i, j;
int m, n;
char cs, cm, cn;
int w;
cout << "输入图的顶点数：";
cin >> V_dingdianshu;
cout << "输入图边的数目：";
cin >> E_bianshu;
cout << "输入起点：";
cin >> cs;
Start_Point = cs - 'a';
for(i = 0; i < V_dingdianshu; i++)
{
for(j = 0; j < V_dingdianshu; j++)
{
Graph[i][j] = 0;
ShortCache[i][j] = 0;
Cost[i][j] = COST_NO_LINK;
}
Cost[i][i] = 0;
}
cout << "输入" << E_bianshu << "条边对应的顶点和权值（顶点从开始编号）：" << endl;
for(i = 0; i < E_bianshu; i++)
{
cin >> cm >> cn >> w;
m = cm - 'a';
n = cn - 'a';
Graph[m][n] += 1;
Graph[n][m] += 1;
Cost[m][n] = w;
Cost[n][m] = w;
}
}
int Dijstra(int v0, int v1, bool useCache)
{
if(useCache && ShortCache[v0][v1] != 0)
return ShortCache[v0][v1];
int i, s, w, min, minIndex;
bool Final[MAX_NODE];
for (s = 0; s < V_dingdianshu; s++)
{
Final[s] = false;
Dist[s] = COST_NO_LINK;
}
Final[v0] = true;
Dist[v0] = 0;
s = v0;
for (i = 0; i < V_dingdianshu; i++)
{
for(w = 0; w < V_dingdianshu; w++)
{
if(!Final[w]
&& Cost[s][w] < COST_NO_LINK
&& Dist[w] > Dist[s] + Cost[s][w])
{
if(Dist[s] + Cost[s][w] <= 0)
{
cout << "求最短路径数据溢出。" << endl;
exit(-1);
}
Dist[w] = Dist[s] + Cost[s][w];
}
}
if(s == v1)
{
ShortCache[v0][v1] = Dist[s];
ShortCache[v1][v0] = Dist[s];
return Dist[s];
}
min = COST_NO_LINK;
for(w = 0; w < V_dingdianshu; w++)
{
if(!Final[w]
&& Dist[w] < min)
{
minIndex = w;
min = Dist[w];
}
}
s = minIndex;
Final[s] = true;
}
cout << "程序异常！应该早找到了最短路径！" << endl;
exit(-1);
}
bool ConnectivityTest(int start, bool& bNoPoints)
{
set<int> nodeSet;
vector<int> for_test_nodes;
int i, j;
set<int> singlePoints;
bool hasEdge = false;
for(i = 0; i < V_dingdianshu; i++)
{
hasEdge = false;
for(j = 0; j < V_dingdianshu; j++)
{
if (Graph[i][j] > 0)
{
hasEdge = true;
break;
}
}
if (!hasEdge)
{
singlePoints.insert(i);
}
}
bNoPoints = (singlePoints.size() == V_dingdianshu);
if(singlePoints.find(start) != singlePoints.end())
return false;
for_test_nodes.push_back(start);
while(for_test_nodes.size() > 0)
{
int testNode = for_test_nodes.back();
for_test_nodes.pop_back();
for(i = 0; i < V_dingdianshu; i++)
{
if(Graph[testNode][i] > 0)
{
if(nodeSet.insert(i).second)
for_test_nodes.push_back(i);
}
}
}
for(i = 0; i < V_dingdianshu; i++)//检测图的连通性
if (singlePoints.find(i) == singlePoints.end()
&& nodeSet.find(i) == nodeSet.end())
return false;
return true;
}
int OddTest()//检测图中的奇度点
{
int i, j, rSum, count;
for(i = 0; i < V_dingdianshu; i++)
{
Odd_Grouping[i] = 0;
Bak_Odd_Grouping[i] = 0;
}
count = 0;
for(i = 0; i < V_dingdianshu; i++)
{
rSum = 0;
for(j = 0; j < V_dingdianshu; j++)
{
rSum += Graph[i][j];
}
if(rSum % 2 == 1)
{
Odd_Grouping[i] = 1;
count++;
}
}
return count;
}
void Bak_Grouping()
{
int i;
for(i = 0; i < V_dingdianshu; i++)
Bak_Odd_Grouping[i] = Odd_Grouping[i];
}
bool Grouping(int level)
{
if(level < 2)
{
cout<< "小于的level值是不允许的。" << endl;
exit(-1);
}
int i, j, findI = -1;
for(i = 0; i < V_dingdianshu; i++)
{
if(Odd_Grouping[i] == 1)
{
Odd_Grouping[i] = level;
findI = i;
break;
}
}
bool re = true;
if(findI == -1)
{
int weightSum = 0;
for(i = 2; i < level; i++)
{
int index[2];
int *pIndex = index;
for(j = 0; j < V_dingdianshu; j++)
{
if(Odd_Grouping[j] == i)
{
*pIndex = j;
if(pIndex == index + 1) break;
pIndex++;
}
}
weightSum += Dijstra(index[0], index[1], true);
}
if(weightSum < SHORTEST_PATH_WEIGHT)
{
Bak_Grouping();
SHORTEST_PATH_WEIGHT = weightSum;
return true;
}
else return false;
}
else if(findI > -1)
{
for(; i < V_dingdianshu; i++)
{
if(Odd_Grouping[i] == 1)
{
Odd_Grouping[i] = level;
re = Grouping(level + 1);
Odd_Grouping[i] = 1;
}
}
}
else
{
cout<< "findCount值异常！" << endl;
exit(-1);
}
if(findI > -1) Odd_Grouping[findI] = 1;
return re;
}
void AddShortPath(int from, int to)//添加最短路径
{
int i, back;
Dijstra(from, to, false);
back = to;
while(back != from)
{
for(i = 0; i < V_dingdianshu; i++)
{
if(i != back
&& Dist[i] < COST_NO_LINK
&& Dist[back] < COST_NO_LINK
&& Dist[i] + Cost[i][back] == Dist[back])
{
Graph[i][back]++;
Graph[back][i]++;
back = i;
break;
}
}
if(i == V_dingdianshu)
{
cout << "程序异常，最短路径出问题了。" << endl;
exit(-1);
}
}
}
void AddShortPaths()
{
int i, j;
for(i = 0; i < V_dingdianshu; i++)
{
if(Bak_Odd_Grouping[i] > 1)
{
for(j = i + 1; j < V_dingdianshu; j++)
{
if(Bak_Odd_Grouping[j] == Bak_Odd_Grouping[i])
{
AddShortPath(i, j);
break;
}
}
}
}
}
void OddDeal()
{
int oddCount = OddTest();
if(oddCount > 0)
{
if(oddCount % 2 == 1)
{
cout << "这是个奇怪的图，存在奇数个奇度顶点的连通图吗？" << endl;
exit(-1);
}
Grouping(2);
AddShortPaths();
}
}
void Fleury(int start)//弗洛伊德算法
{
int i;
int vi = start;
bool bNoPoints, bCnecTest;
cout << "你要的结果：";
while(true)
{
for(i = 0; i < V_dingdianshu; i++)
{
if (Graph[vi][i] > 0)
{
Graph[vi][i]--;
Graph[i][vi]--;
bCnecTest = ConnectivityTest(i, bNoPoints);
if(!bNoPoints && !bCnecTest)
{
Graph[vi][i]++;
Graph[i][vi]++;
continue;
}
cout << (char)('a' + vi) << "-" << (char)('a' + i) << " ";
vi = i;
break;
}
}
if (i == V_dingdianshu)
{
cout << endl;
break;
}
}
}
int main()//主函数
{
Input();
bool b;
if(!ConnectivityTest(0, b))
{
cout << "该图不是连通图！\n";
exit(0);
}
OddDeal();
Fleury(Start_Point);
system("PAUSE");
return 0;
}
