poj 2404 中国邮递员问题欧拉回路判定+状压dp

/*

状压dp

邮递员问题：求经过任意点出发经过每一条边一次并回到原点。

解法：1、如果是欧拉回路那么就是所有的边的总和。

      2、一般的解法，找出所有的奇度顶点，任意两个顶点匹配，即最小完美匹配，可用状压dp。

*/

#include<stdio.h>

#include<string.h>

#define N  20

#define inf 1000000000

int ma[N][N];

int lower[N];

int dp[1<<16];//注意这里数组要开够

void floyd(int n) {

  int i,j,k;

  for(k=1;k<=n;k++)

    for(i=1;i<=n;i++)

    for(j=1;j<=n;j++) {

            if(ma[i][k]>=inf||ma[k][j]>=inf)continue;

    if(ma[i][j]>ma[i][k]+ma[k][j])

    ma[i][j]=ma[i][k]+ma[k][j];

    }

  return ;

}

int vis[N];

int judge(int n) {

  int k=0,num=0;

  while(n) {

    vis[k]=n%2;

    if(vis[k])

        num++;

    n/=2;

    k++;

  }

  return num;

}

int main() {

      int n,m,i,j,k,sum,degree[N],f,to[N],low,last;

      lower[0]=1;

      for(i=1;i<=17;i++)//二进制

        lower[i]=lower[i-1]*2;

      while(scanf("%d",&n),n) {

        scanf("%d",&m);

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

            ma[i][j]=(i==j)?0:inf;

            memset(degree,0,sizeof(degree));

            sum=0;

        while(m--) {

            scanf("%d%d%d",&i,&j,&k);

            if(ma[i][j]>k)

                ma[i][j]=ma[j][i]=k;

            degree[i]++;//求解度数

            degree[j]++;

            sum+=k;

        }

        f=0;

        for(i=1;i<=n;i++)

            if(degree[i]%2==1)

                to[f++]=i;

            if(f==0) {//判断是否是欧拉回路

                printf("%d\n",sum);

                continue;

            }

        floyd(n);//求解任意两点的距离实际用的只有奇度顶点

        // printf("z\n");

        low=1<<f;

         for(i=1;i<low;i++)//初始化

            dp[i]=inf;

            dp[0]=0;

            //printf("%d\n",f);

        for(i=1;i<low;i++) {

            memset(vis,0,sizeof(vis));

            if(judge(i)%2==1)continue;//如果是奇数不符合

            for(j=0;j<f;j++)

            for(k=0;k<f;k++) {

                    if(j==k)continue;//不能相同

                 if(!vis[j]||!vis[k])continue;//只要有一个没有就不符合

                 last=i^lower[j]^lower[k];

                 if(dp[i]>dp[last]+ma[to[j]][to[k]])//当前的状态=去掉j和k的状态+j和k的最短路

                 dp[i]=dp[last]+ma[to[j]][to[k]];

            }

        }

       // printf("%d\n",dp[low-1]);

        printf("%d\n",sum+dp[low-1]);//奇度顶点的总的最小匹配为重复边+总的边数

      }

return 0;

}
巴特西

poj 2404 中国邮递员问题欧拉回路判定+状压dp

最新文章

热门文章

巴特西

poj 2404 中国邮递员问题 欧拉回路判定+状压dp

最新文章

热门文章

poj 2404 中国邮递员问题欧拉回路判定+状压dp
