网站登录系统怎么做,珠海做网站公司,手机排行榜最新,wordpress移动顶部导航菜单开始编程前分析设计思路和程序的整体的框架#xff0c;以及作为数学问题的性质#xff1a; 程序流程图#xff1a; 数学原理#xff1a; 本质上是找到一条欧拉回路#xff0c;考虑图中的边权重、顶点的度数以及如何通过添加最少的额外边来构造欧拉回路#xff0c;涉及到欧…开始编程前分析设计思路和程序的整体的框架以及作为数学问题的性质 程序流程图 数学原理 本质上是找到一条欧拉回路考虑图中的边权重、顶点的度数以及如何通过添加最少的额外边来构造欧拉回路涉及到欧拉回路、最短路径算法以及奇点匹配。 时间复杂度分析 程序的时间复杂度主要来自于Floyd算法和ADD函数。Floyd是动态规划算法。它的时间复杂度是O(n^3)。 ADD函数是一个递归函数它的时间复杂度是O(2^n)其中n是奇点的数量。在最坏情况下奇点的数量可能接近于节点的数量ADD函数的时间复杂度可能接近于O(2^n)。综合看这段程序的时间复杂度是O(n^3 2^n)。由于2^n的增长速度非常快当n较大时2^n将远大于n^3因此这段程序的时间复杂度应该为O(2^n) 源代码 #include stdio.h
#include bits.h
// 定义常量
const int N 105;
const int inf 100000000;
// 建立矩阵和路径数组
int matrix[N][N], mapp[N][N];
int p[N][N];
int path[N], d[N];
int sg[N];
int cont[N];
int vis[N];
int n, m;
int top;
// 设置结构体将边和权重关联
struct node
{int v, u, cost;
} gg[N];
// 使用深度优先递归搜索
void DFS(int beg)
{for (int i 1; i n; i){if (matrix[beg][i]){matrix[beg][i]--;matrix[i][beg]--;DFS(i);}}path[top] beg;
}
void Fleury(int beg)
{top 0;DFS(beg);
}
// 寻找最短路径
void Floyed()
{for (int i 1; i n; i){for (int j 1; j n; j){for (int k 1; k n; k){if (mapp[i][j] mapp[i][k] mapp[k][j]){p[i][j] k;mapp[i][j] mapp[i][k] mapp[k][j];}}}}
}
// 通过递归对奇数边进行加边
int ADD(int cn)
{ // 将奇点进行匹配得一个最小的int ans inf;if (cn 2)return 0; // 奇点个数小于2无需匹配。for (int i 1; i cn; i){if (sg[i] ! 0){for (int j i 1; j cn; j){if (sg[j] ! 0){int tem1 sg[i], tem2 sg[j];sg[i] 0;sg[j] 0;if (ans ADD(cn - 2) mapp[tem1][tem2]){
// 第i个奇点匹配的奇点是第j个奇点cont[i] tem2;
// 第j个奇点匹配的奇点是第i个奇点cont[j] tem1; ans ADD(cn - 2)mapp[tem1][tem2];}sg[i] tem1;sg[j] tem2;}}}}return ans;
}
// 将找到的路径存储
void AddPath(int cn)
{memset(vis, 0, sizeof(vis));for (int i 1; i cn; i){if (!vis[sg[i]]){vis[sg[i]] 1;vis[cont[i]] 1;while (p[sg[i]][cont[i]]){int sss cont[i];cont[i] p[sg[i]][cont[i]];matrix[sss][cont[i]];matrix[cont[i]][sss];}matrix[sg[i]][cont[i]];matrix[cont[i]][sg[i]];}}
}
// 输出路径
void Print_Path()
{printf(top%d\n, top);for (int i top - 1; i 0; i--){printf(%d, path[i]);if (i)printf(-);}puts();
}
//初始化各边信息
void Inif()
{for (int i 0; i N; i){for (int j 0; j N; j){mapp[i][j] (i j) ? 0 : inf;}}
}
// 中国邮路信息建立
void CNLoad()
{while (~scanf(%d%d, n, m)){Inif();int i, beg, sum 0; // sum用来计算路径长度memset(matrix, 0, sizeof(matrix));memset(d, 0, sizeof(d));memset(sg, 0, sizeof(sg));memset(path, 0, sizeof(path));memset(p, 0, sizeof(p));memset(cont, 0, sizeof(cont));// 存储各边信息for (i 1; i m; i){int a, b, c;scanf(%d%d%d, a, b, c);d[a];d[b];matrix[a][b] 1;matrix[b][a] 1;mapp[a][b] c;mapp[b][a] c;gg[i].v a;gg[i].u b;gg[i].cost c;sum c;}beg 1;int cnt 0;for (i 1; i n; i){if (d[i] 1){cnt;sg[cnt] i;beg i;}}if (!cnt){printf(sum%d\n, sum);Fleury(beg);Print_Path();}else{Floyed();printf(sum%d\n, sum ADD(cnt));AddPath(cnt);Fleury(beg);Print_Path();}}
}
int main()
{CNLoad();return 0;
}测试用例图结构 输出结果
