中国邮递员问题（一）

Jogging Trails

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2140		Accepted: 854

Description

Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.

Input

Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord's route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

Output

For each case, there should be one line of output giving the length of Gord's jogging route.

Sample Input

Sample Output

题意：给出一个无向连通图，要求找到一条最短路径且经过每条边至少一次；两个点之间可能存在多条路径，经过每条路径的时候可以以任意的方向经过，起点可以是任何点；

分析：最理想的情况是该图是欧拉回路，即每个点的度都是偶数，最短路径就是所有边的和；，对于一般情况，只要是存在奇度点，则一定是偶数个，那么结下了就是构造一个欧拉回路，把偶数个奇度点两两匹配，任意两个点之间的最短路径可以用floyd算法，最小完备匹配可以用状态压缩dp或者Edmonds算法求。

程序：

#include"stdio.h"
#include"string.h"
#include"queue"
#include"stack"
#include"algorithm"
#include"vector"
#include"iostream"
#include"math.h"
#include"map"
#include"stdlib.h"
#define M 33
#define Max 1<<16
#define inf 100000000
using namespace std;
int dp[Max],dis[M][M],G[M][M],vis[M],po[M],in[M],s[M];
void floyd(int n)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            dis[i][j]=G[i][j];
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
}
int fun(int n)
{
    int s=0;
    int t=0;
    while(n)
    {
        vis[t]=n%2;
        if(vis[t])
            s++;
        n=n/2;
        t++;
    }
    return s;
}
int main()
{
    int n,m,i,j,k,a,b,c;
    po[0]=1;
    for(i=1;i<=17;i++)
        po[i]=po[i-1]*2;
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i==j)G[i][j]=0;
                else G[i][j]=inf;
            }
        }
        memset(in,0,sizeof(in));
        int sum=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(G[a][b]>c)
                G[a][b]=G[b][a]=c;
            in[a]++;
            in[b]++;
            sum+=c;
        }
        floyd(n);
        int num=0;
        for(i=1;i<=n;i++)
            if(in[i]&1)
            s[num++]=i;
        if(num==0)
        {
            printf("%d
",sum);
            continue;
        }
        int val=1<<num;
        for(i=1;i<val;i++)
            dp[i]=inf;
        dp[0]=0;
        for(i=1;i<val;i++)//枚举每种状态
        {
            memset(vis,0,sizeof(vis));
            int p=fun(i);
            if(p&1)continue;
            for(j=0;j<num;j++)
            {
                for(k=0;k<num;k++)
                {
                    if(j==k)continue;
                    if(!vis[j]||!vis[k])continue;
                    int all=i-po[j]-po[k];
                    if(dp[i]>dp[all]+dis[s[j]][s[k]])
                        dp[i]=dp[all]+dis[s[j]][s[k]];
                }
            }
        }
        printf("%d
",sum+dp[val-1]);
    }
    return 0;
}