http://acm.pku.edu.cn/JudgeOnline/problem?id=1860
感谢aowarmen 指出我的错误
题意 ： 就是套汇的问题，汇率Rab， 增加了一个手续费 Cab 。。。。。。。每次的结果是 (本金 - 手续费) * 汇率，而且一个人拥有的钱的类型是已知的，拥有的value 钱的个数也是已知的， 问你能不能增值。
输入 ：
3 2 1 20.0 //钱种类个数 汇率的个数，拥有第几种钱， 拥有多少钱
1 2 1.00 1.00 1.00 1.00 //钱a， 钱b， rab， cab， rba， cba
2 3 1.10 1.00 1.10 1.00
想法： 应用bellman-ford ：
应用bellman求解最短路径（上界松弛）和最长路径（下界松弛）的时候，都是松弛 点 - 1 次， 然后再看能否再进行松弛了。如果能，就证明有环。否则为最短或者最长路径（希望错了请大家指出）
当时看这个题的时候，被bellman求解最短路给束缚了， 即循环是 点 - 1 次， 但是这种最长路的正环不一定就在 点 - 1 次松弛后，就能让目标点符合要求，也即是说不一定能松弛连接目标点的边，因为要看d[u]与d[目标点(v)]的关系，也就是边，就像最短路得负环一样，他们是无限的增长下去的。
所以这个题 循环的终止条件有2个 ：
1。 当不能松弛的时候停止， 这样就代表这个图中没有正环，这样判断一下d[x]是否大于value就可以了。
2。 发现d[x] 〉value了，这种时候有可能是图有正环，也有可能图还没有松弛完毕，但是只要发现满足条件，就可以了。
对了，这个题还要注意精度
代码如下：
1 #include <stdio.h>
2 #include <string.h>
3 #define eps 1e-8
4 using namespace std;
5 int m, n, x, el;double value;
6 struct E{
7 int u, v;
8 double r, c;
9 }e[1001];
10 bool bellman(){
11 int i, j, f, p[102], u, v;double r, c, d[102];
12 memset(d, 0, sizeof(d));
13 d[x] = value;
14 while(d[x] <= value + eps){
15 f = 0;
16 for(j = 0; j <= el; j++){
17 if(d[e[j].v] + eps < (d[e[j].u] - e[j].c) * e[j].r ){
18 d[e[j].v] = (d[e[j].u] - e[j].c) * e[j].r;
19 p[e[j].v] = e[j].u;
20 f = 1;
21 }
22 }
23 if(!f)
24 return d[x] > value + eps;
25 }
26 return 1;
27 }
28 int main(){
29 freopen("1860.in","r",stdin);
30 freopen("1860.out","w",stdout);
31 int i, j, u, v, f;double ruv, cuv, rvu, cvu;
32 while(scanf("%d%d%d%lf", &m, &n, &x, &value) != -1){
33 el = 0;
34 for(i = 0; i < n; i++){
35 scanf("%d%d%lf%lf%lf%lf", &u, &v, &ruv, &cuv, &rvu, &cvu);
36 e[el].u = u;
37 e[el].v = v;
38 e[el].r = ruv;
39 e[el++].c = cuv;
40 e[el].u = v;
41 e[el].v = u;
42 e[el].r = rvu;
43 e[el++].c = cvu;
44 }
45 if(bellman())puts("YES");
46 else puts("NO");
47 }
48 return 0;
49 }
50
51