hdu 1217 Arbitrage

点击打开链接hdu 1217

思路：最短路变形题（floyd 或 SPFA）

分析：
2 题目要求的是经过一轮的转换之后，原来的比例能够大于1。比如原先的“美元：美元 = 1：1”,最后要求能够达到“美元：美元 > 1”
3 假设dis[i][j]表示“i ： j”的比例，那么初始化dis[i][i] = - 1。
4 由于n最大为30，所以果断选择floyd算法。但是这里有个地方不同的是，这里并不是要求最小而是求最大，所以应该要把“小于改成大于”
5 最后只要能够找到一种货币的兑换比例大于1即满足条件

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
#define MAXN 40

int n , m , flag;
double dis[MAXN][MAXN];
char ch[MAXN][MAXN];

/*返回最大值*/
double max(double a , double b){
    return a > b ? a : b;
}

/*floyd算法*/
void floyd(){
    for(int k = 1 ; k <= n ; k++){
       for(int i = 1 ; i <= n ; i++){
          for(int j = 1 ; j <= n ; j++)  
             dis[i][j] = max(dis[i][k]*dis[k][j] , dis[i][j]);/*求最大值*/
       }
    }
}

int main(){
    double v;
    int a , b , cnt;
    char str1[MAXN] , str2[MAXN];
    cnt = 1;
    while(scanf("%d" , &n) && n){
        flag = 0;
        memset(dis , 0 , sizeof(dis));
       /*初始化为-1*/
        for(int i = 1 ; i <= n ; i++){
           for(int j = 1 ; j <= n ; j++)
              dis[i][j] = -1;
        }
        for(int i = 1 ; i <= n ; i++)
           scanf("%s" , ch[i]);
        scanf("%d" , &m);
        for(int i = 0 ; i < m ; i++){
           scanf("%s%lf%s" , str1 , &v , str2);
           for(int i = 1 ; i <= n ; i++){
              if(!strcmp(str1 , ch[i]))
                a = i;
              if(!strcmp(str2 , ch[i]))
                b = i;
           }
           if(dis[a][b] < v)
               dis[a][b] = v;
        }
        floyd();
        for(int i = 1 ; i <= n ; i++){
           if(dis[i][i] > 1.0){/*找到一种满足条件即可*/
              flag = 1;
              break;
           }
        }
        if(flag)
           printf("Case %d: Yes\n" , cnt++);
        else
           printf("Case %d: No\n" , cnt++);
    }
    return 0;
}

/*利用SPFA来判断是否存在环，只要能够形成环就说明满足条件*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 40
#define INF 0xFFFFFFF

int n , m , flag;
double value[MAXN][MAXN];
double dis[MAXN];
int vis[MAXN];
int num[MAXN];
char ch[MAXN][100];
queue<int>q;

void SPFA(int s){
    while(!q.empty())
        q.pop();
    memset(vis , 0 , sizeof(vis));
    memset(dis , 0 , sizeof(dis));

   memset(num , 0 , sizeof(num));

    dis[s] = 1; vis[s] = 1; q.push(s); while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = 1 ; i <= n ; i++){ if(value[x][i]){ if(dis[i] < dis[x] * value[x][i]){ dis[i] = dis[x] * value[x][i]; num[i]++; if(num[i] >= n){/*判断当前的边的松弛操作是否大于等于n*/ flag = 1; return; } if(!vis[i]){ vis[i] = 1; q.push(i); } } } } }} int main(){ int a , b , cnt = 1; double rate; char str1[MAXN] , str2[MAXN]; while(scanf("%d" , &n) && n){ memset(value , 0 , sizeof(value)); for(int i = 1 ; i <= n ; i++){ scanf("%s" , ch[i]); value[i][i] = 1; } scanf("%d" , &m); for(int i = 0 ; i < m ; i++){ scanf("%s %lf %s" , str1 , &rate , str2); for(int i = 1 ; i <= n ; i++){ if(!strcmp(ch[i] , str1)) a = i; if(!strcmp(ch[i] , str2)) b = i; } value[a][b] = rate; } flag = 0; for(int i = 1 ; i <= n ; i++){ SPFA(i); if(flag) break; } if(flag) printf("Case %d: Yes\n" , cnt++); else printf("Case %d: No\n" , cnt++); } return 0;}