Floyd变形，求最大路径，如果自身到自身的权值大于1则可认为盈利。这个地方需要注意下，自身到自身的初始权值应该是1而不是0。
#include
#include
#include
using namespace std;
map money;
double dist[35][35];
void floyd(double dist[35][35], int size)
{
for (int i = 1; i <= size; i++)
{
for (int j = 1; j <= size; j++)
{
for (int k = 1; k <= size; k++)
{
if (dist[i][j] < dist[i][k] * dist[k][j])
dist[i][j] = dist[i][k] * dist[k][j];//max path length
}
}
}
}
int main()
{
int n;
int countt = 1;
while (cin >> n && n)
{
memset(dist, 0, sizeof(dist));
money.clear();
for (int i = 1; i <= n; i++)
{
string temp;
cin >> temp;
money.insert(make_pair(temp, i));
dist[i][i] = 1;//pay attention
}
/*for (auto i : money)
{
cout << i.first << ' ' << i.second << endl;
}*/
int m;
cin >> m;
for (int i = 1; i <= m; i++)
{
string a, b;
double rate;
cin >> a >> rate >> b;
dist[money[a]][money[b]] = rate;
}
floyd(dist, n);
bool flag = false;
for (int i = 1; i <= n; i++)
{
if (dist[i][i] > 1)//profit
{
flag = true;
break;
}
}
if (flag)
cout << "Case " << countt++ << ": Yes" << endl;
else
cout << "Case " << countt++ << ": No" << endl;
}
return 0;
}