题意：
还是套汇问题，换货币看能不能增加钱
要点：
还是求负权回路，这题没有规定从哪边出发，所以Floyd算法比较好，但我刚学了一下spfa算法，强行用了一下也可以。
SPFA算法详解：点击打开链接
SPFA算法：
| 15380850 | Seasonal | 2240 | Accepted | 280K | 47MS | C++ | 1448B | 2016-04-12 08:34:54 |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
int n, m;
char name[100][100];
double map[100][100],dis[100];bool spfa(int x)
{queue<int > que;bool vis[100];int count[100];memset(vis, false, sizeof(vis));memset(dis, 0, sizeof(dis));memset(count, 0, sizeof(count));dis[x] = 100.0;vis[x] = true;que.push(x);count[x]++;while (!que.empty()){int temp = que.front(); que.pop();vis[temp] = false;for (int i = 0; i < n;i++)if (dis[temp] * map[temp][i] > dis[i]){dis[i] = map[temp][i] * dis[temp];//松弛操作，有的点已经在队列中就不用入队if (!vis[i]) //如果当前点不在队列中{que.push(i);count[i]++;vis[i] = true;if (count[i] >= n)//如果入队次数大于等于n即有负权回路return true;}} }return false;
}int main()
{int num = 1;int x, y,i,j;while (~scanf("%d", &n), n){memset(map, 0, sizeof(map));for (i = 0; i < n; i++)scanf("%s", name[i]);scanf("%d", &m);char temp1[100], temp2[100];double rate; while(m--){scanf("%s %lf %s", temp1, &rate, temp2);for (j = 0; j < n;j++)if (strcmp(name[j], temp1) == 0){x = j;break;}for (j = 0; j < n; j++)if (strcmp(name[j], temp2) == 0){y = j;break;}map[x][y] = rate;}bool flag = true;printf("Case %d: ", num++);for (i = 0; i < n;i++) //每个点都找是否存在负权回路if (spfa(i)){flag = false;break;}if (!flag)printf("Yes\n");elseprintf("No\n");}return 0;
}Floyd算法：
| 15380929 | Seasonal | 2240 | Accepted | 264K | 47MS | C++ | 1109B | 2016-04-12 09:26:32 |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
int n, m;
char name[100][100];
double map[100][100];void floyd()
{for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (map[i][j] < map[i][k] * map[k][j])map[i][j] = map[i][k] * map[k][j];
}int main()
{int num = 1;int x, y,i,j;while (~scanf("%d", &n), n){memset(map, 0, sizeof(map));for (i = 0; i < n; i++)map[i][i] = 1; //一开始到自己的设成1，如果经过Floyd算法后改变这说明有负权回路for (i = 0; i < n; i++)scanf("%s", name[i]);scanf("%d", &m);char temp1[100], temp2[100];double rate; while(m--){scanf("%s %lf %s", temp1, &rate, temp2);for (j = 0; j < n;j++)if (strcmp(name[j], temp1) == 0){x = j;break;}for (j = 0; j < n; j++)if (strcmp(name[j], temp2) == 0){y = j;break;}map[x][y] = rate;}bool flag = true;floyd();for (i = 0; i < n;i++)if (map[i][i]>1){flag = false;break;}printf("Case %d: ", num++);if (!flag)printf("Yes\n");elseprintf("No\n");}return 0;
}