中国邮路问题

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int INF = 0x3f3f3f3f; 
const int N = 3010;typedef struct Node{int number;int cost;int dis;
}node;
int _map[N][N],old_map[N][N];//邻接矩阵
node __map[N][N];
int n,m,cnt,top,flag;
int du[N],id[N],__stack[N]; //id数组是统计奇度顶点,弗洛莱算法需要用到栈,top代表的是栈大小,flag用来结束递归
bool point_connect[N]; //标记需要连接的点
int minn ,num_edge;//num_edge统计的是奇数边的数量
int temp_edge[N],min_edge[N];//temp_edge数组临时保存匹配的奇数组合边，min_edge数组保存最小的奇数组合边
struct Edge{int from,to,dis;
}total_edge[N],odd_edge[N];//odd_edge数组代表的是奇度顶点的边void Floyd(){for(int k=1;k<=n;++k)for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){// _map[i][j] = min(_map[i][j],_map[i][k]+_map[k][j]);__map[i][j].dis = min(__map[i][j].dis,__map[i][k].cost+__map[k][j].cost);}
}void dfs_edge(int sum,int step,int need_num){if(step == need_num){if(sum<minn){for(int i=0;i<step;++i){min_edge[i] = temp_edge[i];}minn = sum;}}for(int i=1;i<=num_edge;++i){int a= odd_edge[i].from;int b = odd_edge[i].to;int w = odd_edge[i].dis;if(point_connect[a]==1 && point_connect[b]==1){point_connect[a] = point_connect[b] = 0;temp_edge[step] = i;dfs_edge(sum+w,step+1,need_num);point_connect[a] = point_connect[b] = 1;}}
}
void dijkstra(int st,int ed){int dist[N];bool used[N];int pre[N];memset(dist,0x3f,sizeof dist);memset(used,false,sizeof used);memset(pre,0,sizeof pre);dist[st] = 0;for(int i=0;i<n-1;++i){int t = -1;for(int j=1;j<=n;++j){if(!used[j] && (t==-1 || dist[j]>dist[t]))t= j;}for(int j=1;j<=n;++j){if(dist[j]>dist[t]+old_map[t][j]){pre[j] = t;dist[j] = dist[t] + __map[t][j].dis;}}}int backup = ed;while(backup!=st){int pre_node = pre[backup];__map[pre_node][backup].number++;__map[backup][pre_node].number++;backup = pre_node;}}
void extend_edge(int add_edge){num_edge = 0;for(int i=1;i<=n;++i){if(du[i] & 1){for(int j=i+1;j<=n;++j){if(du[j] & 1){point_connect[i] = point_connect[j] =1;num_edge++;odd_edge[num_edge].from = i;odd_edge[num_edge].to = j;odd_edge[num_edge].dis = _map[i][j];}}}}minn = INF;dfs_edge(0,0,add_edge);for(int i=0;i<add_edge;++i){int k = min_edge[i];int a = odd_edge[k].from;int b = odd_edge[k].to;int w = odd_edge[k].dis;dijkstra(a,b);point_connect[a]  =point_connect[b] = 0;}
}void Fleury(int st){int i;for(int i=1;i<=n;++i){if(__map[st][i].number>0){__map[st][i].number--;__map[i][st].number--;__stack[top++] = i;if(top==(m+1)){flag = true;return ;}Fleury(i);if(flag) return ;__map[st][i].number++;__map[i][st].number++;top--;}}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(i==j) _map[i][j] = 0;else _map[i][j] = INF;for(int i=1;i<=m;++i){int from, to ,weight;cin>>from>>to>>weight;total_edge[i] = {from,to,weight};du[from]++,du[to]++;// _map[from][to] = weight;// old_map[from][to] = weight;__map[from][to].number++;__map[to][from].number++;__map[from][to].cost = weight;__map[to][from].cost = weight;}Floyd();for(int i=1;i<=n;++i) if(du[i] & 1) cnt++;if(cnt==1 || cnt>2) {puts("不是欧拉回路");return 0;}if(cnt==2){extend_edge(cnt/2);}m+=cnt/2;int first_id = 1;if(cnt==2){for(int i=1;i<=n;++i){if(du[i] & 1){first_id = i;break;}}}__stack[top++] = first_id;Fleury(first_id);char vt_point;int total_res = 0;for(int i=1;i<=m;++i){total_res+=__map[__stack[i-1]][__stack[i]].cost;}printf("%d\n",total_res);for(int i=0;i<=m;++i){vt_point = __stack[i]+'A'-1;printf("%c",vt_point);if(i<m){printf("->");}}puts("");return 0;
}

用到了最短路算法和弗洛莱算法，用结构体代替邻接矩阵