b.c

ACM精彩程序02(University_of_Waterloo_2_1_June_2002)包括源题目和解答

#include <stdio.h>
#include <string.h>

int m,n,i,j,k,p,tot;

int d[21][21], e;

int cost[1<<20+1];

match(int e){
   int i,j,k,best=0x7fffffff;
   if (!e) return 0;
   if (cost[e] != 0) return cost[e];
   for (i=1;!(e & (1<<i));i++);
   for (j=i+1;j<=n;j++){
      if (!(e & (1<<j))) continue;
      k = match(e - (1<<i) - (1<<j));
      if (d[i][j] + k < best) best = d[i][j] + k;
   }
   return cost[e] = best;
}

main(){
   while (2 == scanf("%d%d",&n,&m)){
      for (i=1;i<=n;i++) for (j=1;j<=n;j++) d[i][j] = (i!=j) * 0x3fffffff;
      memset(cost,0,sizeof(cost));
      e = 0;
      tot = 0;
      for (i=0;i<m;i++) {
         scanf("%d%d%d",&j,&k,&p);
         if (p < d[j][k]) d[j][k] = d[k][j] = p;
         tot += p;
         e ^= (1<<j);
         e ^= (1<<k);
      }
      for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=1;k<=n;k++) {
         if (d[j][i]+d[i][k] < d[j][k]) d[j][k] = d[j][i]+d[i][k];
      }
      printf("%d\n",tot+match(e));
   }
   if (n) printf("input data missing end delim\n");
}