题目大意：

给你几种货币，以及几种汇率关系，问是否存在套利的可能？

思路：

初步想法：图上存在一个环的路径上权值相乘大于1....

再者：该如何找到图上所有环呢....

好吧 经过鸟神 和 况神的指点,,,这题就是一道floyed求最小环而已（权重取负）（虽然差不多，其实还是差挺远..）

对于乘法处理转换为ln...Orz一下鸟神

Floyed求最小环（后来才发现没关系）

一开始天真的以为.....只要求一遍Floyed 再判断一下F[i][i]就好，但要记住这个图是带负权值的....所以可能是走过几圈的........

（但其实这个题没有影响，只需要判断最终的结果是否小于0即可，多走几圈，依旧会小于0。。事实上也A了..)

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#include <map>

#define oo 0x13131313

using namespace std;

const double e=2.718281828459;

const int    maxn=31;

double F[maxn][maxn];

map<string,int> money;

int n,m;                          //number of price

void Clear()

{

    for(int i=0;i<maxn;i++)

        for(int j=0;j<maxn;j++)

         F[i][j]=2100000000;

    money.clear();

}

double ans=2100000000;

void solve()

{

     ans=2100000000;

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

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

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

    {

        if(F[i][k]+F[k][j]<F[i][j])

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

    }

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

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

    {

        if(F[i][k]+F[k][i]<F[i][i])

            F[i][i]=F[i][k]+F[k][i];

        if(F[i][i]<ans) ans=F[i][i];

    }

}

void input()

{

    string a,b;

    double c;

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

    {

        cin>>a;

        money[a]=i;

    }

    scanf("%d",&m);

    for(int i=1;i<=m;i++)

    {

        cin>>a>>c>>b;

        c=-log(c);

        F[money[a]][money[b]]=c;

    }

}

void init()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

}

int main()

{

   // init();

    int Case=0;

    while(cin>>n&&n)

    {

        Case++;

        printf("Case %d: ",Case);

        Clear();

        input();

        solve();

        if(ans<0) printf("Yes\n");

        else printf("No\n");

    }

}

即时这个题不需要。

但还是要搞懂怎么求最小环！！未完待续..。

带负权求不出