过的诡异。。。。。
貌似听aowarmen 讲是要判断正环，但是。。。我加了一个点，用最长路做的。。。汗。。。。
而且重边判断的不行， re 了n次。。。。。
水过。。。。。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2240
后来改的，仍然判不了重边。。。
1 #include <stdio.h>
2 #include <string.h>
3 #include <string>
4 #include <map>
5 #define eps 1e-30
6 #define max 1000
7 using namespace std;
8 map<string, int> mp;
9 map<string, int> :: iterator it;
10 int m, n, el;
11 double mm[max][max];
12 struct E{
13 int u, v;
14 };
15 E e[1000000];
16 double bellman(){
17 int i, j, f;
18 double d[max];
19 for(i = 0; i < max; i++)d[i] = -1;
20 d[0] = 1;
21 for(i = 0; i < m; i++){
22 f = 0;
23 for(j = 0; j < el; j++){
24 if(d[e[j].v] < d[e[j].u] * mm[e[j].u][e[j].v] + eps){
25 d[e[j].v] = d[e[j].u] * mm[e[j].u][e[j].v];
26 f = 1;
27 }
28 }
29 if(!f)return d[n] > 1.0 + eps;
30 }
31 return d[n] > 1.0 + eps;
32 }
33
34 int main()
35 {
36 char input[1000], u[1000], v[1000];
37 int i, j, l, a, b, c = 1;
38 double w;
39 while(scanf("%d", &m), m){
40 l = el = 0;
41 printf("Case %d: ", c++);
42 memset(mm, 0, sizeof(mm));
43 for(i = 0; i < m; i++){
44 scanf("%s", input);
45 mp.insert(make_pair(input, l++));
46 }
47 scanf("%d", &n);
48 for(i = 0; i < n; i++){
49 scanf("%s%lf%s", u, &w, v);
50 a = mp.find(u)->second;
51 b = mp.find(v)->second;
52 e[el].u = a;
53 if(b == 0)b = n;
54 if(!mm[a][b] || mm[a][b] < w + eps){
55 mm[a][b] = w;
56 e[el++].v = b;
57 }
58 }
59 if(bellman())
60 printf("Yes\n");
61 else printf("No\n");
62 mp.clear();
63 }
64 return 0;
65 }