POJ 2404 Jogging Trails（最小权完美匹配）

【题目大意】

　　给出一张图，求走遍所有的路径至少一次，并且回到出发点所需要走的最短路程

【题解】

　　如果图中所有点为偶点，那么一定存在欧拉回路，
　　否则一定存在偶数个奇点，将这些奇点取出构建新图，
　　任意两点之间的边权威原图中两点的最短距离，
　　用状压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（最小权完美匹配）

相关文章