题意：
还是套汇问题，换货币看能不能增加钱
要点：
还是求负权回路，这题没有规定从哪边出发，所以Floyd算法比较好，但我刚学了一下spfa算法，强行用了一下也可以。
SPFA算法详解：
SPFA算法：
| 15380850 | Accepted | 280K | 47MS | 1448B | 2016-04-12 08:34:54 |
#include#include #include #include using namespace std;int n, m;char name[100][100];double map[100][100],dis[100];bool spfa(int x){ queue 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"); else printf("No\n"); } return 0;}
Floyd算法：
| 15380929 | Accepted | 264K | 47MS | 1109B | 2016-04-12 09:26:32 |
#include#include #include #include 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"); else printf("No\n"); } return 0;}