HDU 1217 Arbitrage 곱셈 최 단 길

전재 이 링크 를 명시 해 주 십시오.
제목: 환율 로 돈 버 는 문제.1 단위 화폐 a 는 x 단위 화폐 b 를 바 꿀 수 있 고 1 단위 화폐 b 는 y 단위 화폐 c 를 바 꿀 수 있 으 며 1 단위 화폐 c 는 z 단위 화폐 a 를 바 꿀 수 있다.이런 순환 화폐 a 를 통 해 1 단위 보다 많 으 면 돈 을 벌 수 있다.일부 화폐의 환율 을 바 꾸 어 이런 고리 가 돈 을 벌 수 있 는 지 물 었 다.
생각:
1. 우선 이런 링 이 있 는 지 물 어보 면 벨 맨 - 포드 알고리즘 링 이 생각 나 기 쉽 지만 BF 알고리즘 은 마이너스 링 만 판단 할 수 있 기 때문에 문 제 를 바 꿔 야 합 니 다.
2. 제목 처럼 마지막 에 바 꾼 화 폐 는 1 * x * y * z, 즉 xyz > 1 이면 돈 을 벌 수 있 습 니 다. 마이너스 링 이 필요 하 다 는 점 을 감안 하여 경 로 를 모두 부 호 를 붙 이 는 것 을 생각 할 수 있 습 니 다.
3. 마이너스 링 은 0 보다 작 기 때문에 1 은 어떻게 0 이 될 수 있 습 니까? 대 수 를 취하 면 됩 니 다. 그래서 logx + logy + logz > 0, 마이너스 번 호 를 취하 면 (- logx) + (- logy) + (- logz) < 0 이 됩 니 다.
4. 그래서 생각 이 떠 올 랐 다. 모든 변 e 를 - loge 로 만 든 다음 에 모든 화 폐 를 원점 으로 하 는 BF 알고리즘 을 사용 했다. 하나의 원점 의 네 거 티 브 링 만 존재 하면 Yes 이다.
5. 출력 앞 에 case 수 를 추가 하고 Yes 와 No 의 대소 문 자 를 잘못 쓰 지 않도록 주의 하 세 요.
코드:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>

using namespace std;

const int N=40;
const double inf=1<<30;
const double eps=1e-8;

#define Equ(a,b) ((fabs((a)-(b)))<eps)
#define More(a,b) ((a)-(b)>eps)

int n,m,num;
double d[N],E[N][N];
map<string,int> dict;

inline int change(char *s)
{
    if(dict.count(s)) return dict[s];
    else return dict[s]=num++;
}

bool Bellman_Ford(int s)
{
    fill(d,d+N,inf);
    d[s]=0;
    for(int i=0;i<n-1;i++)
    {
        for(int u=0;u<n;u++)
        {
            for(int v=0;v<n;v++)
            {
                if(!Equ(E[u][v],inf))
                {
                    if(More(d[v],E[u][v]+d[u]))
                    {
                        d[v]=E[u][v]+d[u];
                    }
                }
            }
        }
    }
    for(int u=0;u<n;u++)
    {
        for(int v=0;v<n;v++)
        {
            if(More(d[v],E[u][v]+d[u])) return false;
        }
    }
    return true;
}

int main()
{
    char s1[30],s2[30];
    int s,t,tcase=1;
    double c;
    while(scanf("%d",&n),n)
    {
        num=0;
        dict.clear();
        fill(E[0],E[0]+N*N,inf);
        for(int i=0;i<n;i++)
        {
            scanf("%s",s1);
            s=change(s1);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s %lf %s",s1,&c,s2);
            s=change(s1),t=change(s2);
            E[s][t]=-log(c);
        }
        bool flag=false;
        for(int i=0;i<n;i++)
        {
            if(Bellman_Ford(i)==false) flag=true;
        }
        if(flag) printf("Case %d: Yes
",tcase++);
        else printf("Case %d: No
",tcase++);
    }
    return 0;
}