题目链接： 传送门
#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #define INF 0x3f3f3f3f using namespace std; const int N = 20010; double d[35]; int n, m; //边的结构体 struct edge{ int start,end; double w; }edges[N]; //用Bellman_ford算法来求是否有正环 bool Bellman_ford() { memset(d, INF, sizeof(d)); d[1] = 1; for(int i = 1; i < n; i++) for(int j = 0; j < m; j++) if(d[edges[j].end]<d[edges[j].start]*edges[j].w) d[edges[j].end]=d[edges[j].start]*edges[j].w; for(int j = 0;j < m; j++) if(d[edges[j].end]<d[edges[j].start]*edges[j].w) return 1; return 0; } int main() { string str, from, to; int ca = 1; double c; //开一个map来把字符串映射成点 map<string,int> id; while(cin >> n) { //等于0时跳出 if(n == 0) break; //把对应的字符串映射成点 for(int i = 1; i <= n; i++) { cin >> str; id[str]=i; } cin >> m; for(int i = 0; i < m; i++) { //把串变成对应的点，把值作为两点间的边权 cin >> from >> c >> to; edges[i].start = id[from]; edges[i].end = id[to]; edges[i].w=c; } //输出第几个样例 cout<<"Case "<<ca++<<": "; //判断是否有正环 if(Bellman_ford()) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }这道题首先明确题意，这道题就是要我们判断这个图是否存在正环。读懂题意后我们就可以开始做题了，这道题我用了Bellman_ford算法变形来做。有关Bellman_ford算法的博客 正常情况下，该算法中的松弛操作（即 if(d[edges[j].end]<d[edges[j].start]*edges[j].w) d[edges[j].end]=d[edges[j].start]*edges[j].w;的这两行代码）如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在回路。所以我们可以执行n-1次松弛操作后，在执行一次，看看这次遍历是否会出现松弛操作，如果出现了则说明这几个点中有回路。 现在将整体思路，首先接受货币的种类数，为零就直接跳出。然后用map把这些字符串映射成点。后面接受操作数，然后根据操作，把对应点及其权值记录下来。然后套Bellman_ford的模板判断一下，最后输出就可以了。
