poj_2240_bellmannbsp;ford

题目描述：

   给出货币兑换关系，问是否能用其中一种货币换回更多的值。

解题思路：

   bellman-ford。

   回顾下：适用于含负权边的图。可检测图中是否存在负权回路。算法简单描述为做n次边松弛操作，用数组D[]记下每个点处的值。若第n次仍然有边可以进行松弛，则说明存在负权回路。否则该D[]求得从源点s到图G的任意丁点v的最短路径D[].

  这个题要注意自己和自己兑换的情况。同时不固定源点。

代码：

#include <stdio.h>
#include <stdlib.h>
#define N 31
#define M 10000

typedef struct{
   int s;
   int e;
   double r;
}Edge;

char vertex[N][30];
Edge edge[M];
int n,m;
double D[N];

int bellman_ford(){
   int i, j, f, k;
   memset(D,0,sizeof(D));
   for(k=1;k<=n;k++){
      if(D[k]!=0)
         continue;
       memset(D,0,sizeof(D));
       D[k] = 1;
       for(i=1;i<=n;i++){
          f = 0;
          for(j=1;j<=m;j++){
             if(D[edge[j].e] < D[edge[j].s]*edge[j].r){
                f = 1;
                D[edge[j].e] = D[edge[j].s]*edge[j].r;
             }
          }
    //      printf("此时D数组情况：\n");
    //      for(k=1;k<=n;k++)
    //         printf("%f\t",D[k]);
    //      printf("\n");
          if(f==0)
             i = n+1;
       }
       if(f)
          return 1;
    }
    return 0;
}

main()
{
   char ver[2][30];
   int s, e, i, j, f, k=1;
   double r;
  
   scanf("%d",&n);
  
   while(n!=0){
       for(i=1;i<=n;i++)
          scanf("%s",vertex[i]);
         
       scanf("%d",&m);
       for(i=1;i<=m;i++){
          scanf("%s %lf %s",ver[0], &r, ver[1]);
          for(j=1;j<=n;j++)
             if(strcmp(ver[0],vertex[j])==0)
                break;
           s = j;
           for(j=1;j<=n;j++)
              if(strcmp(ver[1],vertex[j])==0)
                 break;
           e = j;
           edge[i].s = s;
           edge[i].e = e;
           edge[i].r = r;
       }
       //查看边
    //   for(i=1;i<=m;i++)
    //      printf("s:%d -> e:%d = rate:%f\n",edge[i].s, edge[i].e, edge[i].r);
      
       f = bellman_ford();
       if(f == 1)
          printf("Case %d: Yes\n",k);
       else
          printf("Case %d: No\n",k);
       scanf("%d",&n);
       k++;
   }

   system("pause");
   return 0;
}