首页 > 代码库 > POJ 2404 Jogging Trails（最小权完美匹配）
POJ 2404 Jogging Trails（最小权完美匹配）
【题目链接】 http://poj.org/problem?id=2404
【题目大意】
给出一张图，求走遍所有的路径至少一次，并且回到出发点所需要走的最短路程
【题解】
如果图中所有点为偶点，那么一定存在欧拉回路，
否则一定存在偶数个奇点，将这些奇点取出构建新图，
任意两点之间的边权威原图中两点的最短距离，
用状压DP求最小权完美匹配，加上原图所有边权和就是答案。
【代码】
#include <cstdio>#include <algorithm>#include <cstring> #define rep(i,n) for(int i=1;i<=n;i++)using namespace std;const int INF=0x3f3f3f3f;int n,m,all,top,tot,d[20],q[20],bin[20],dp[65536],dis[20][20];int main(){ bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; while(~scanf("%d",&n),n){ scanf("%d",&m); top=tot=0; memset(dis,INF,sizeof(dis)); memset(d,0,sizeof(d)); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); dis[u][v]=dis[v][u]=min(dis[u][v],w); d[u]++; d[v]++; tot+=w; }rep(k,n)rep(i,n)rep(j,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int i=1;i<=n;i++)if(d[i]&1)q[++top]=i; all=bin[top]-1; memset(dp,INF,sizeof(dp)); dp[0]=0; for(int i=0;i<all;i++){ int x=1; while((1<<(x-1))&i)x++; for(int y=x+1;y<=top;y++){ if(!(i&bin[y-1]))dp[i|bin[y-1]|bin[x-1]] =min(dp[i|bin[y-1]|bin[x-1]],dp[i]+dis[q[x]][q[y]]); } }printf("%d\n",dp[all]+tot); }return 0;}POJ 2404 Jogging Trails（最小权完美匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。