开始编程前分析设计思路和程序的整体的框架，以及作为数学问题的性质：

程序流程图：

数学原理：

        本质上是找到一条欧拉回路，考虑图中的边权重、顶点的度数以及如何通过添加最少的额外边来构造欧拉回路，涉及到欧拉回路、最短路径算法以及奇点匹配。

时间复杂度分析：

        程序的时间复杂度主要来自于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;
}

测试用例：（图结构）

输出结果：