POJ

偷瓜的贼

　　题目链接：http://poj.org/problem?id=1860
　　题意：货币之间转换问题，有N种钱，M种转换，初始第S种钱有V价值，然后转换（转换公式：（钱价值-税）*汇率），问是否能有一种转换可以是初始S的钱价值增加。
　　题解：
　　1.SPFA
　　因为可能钱会减少，就是可能出现负边，所以肯定不能用dijkstra。
　　SPFA的话就是把每种情况都搜寻一下，判断初始的钱是否增加。



1 #include <queue>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 #include <algorithm>
6 using namespace std;
7
8 double d[111];
9 int vis[111];
10 int N,M,S;
11 double V;
12 struct node{
13     int to;
14     double rate,tax;
15 };
16
17 vector <node> E[111];
18
19 int SPFA(){
20     double x,y;
21     int u,v;
22     memset(d,0,sizeof(d));
23     memset(vis,0,sizeof(vis));
24     queue <int> Q;
25     Q.push(S);
26     d[S]=V;vis[S]=1;
27     while(!Q.empty()){
28         u=Q.front();Q.pop();
29         vis=0;//使得往外跑的点还能再往回跑，因为是双向的嘛。整个VIS去掉都没关系（时间慢点罢了），如果有正环肯定会return，没有的话就进不去，慢慢就终止了。
30         for(int i=0;i<E.size();i++){
31             v=E.to;
32             x=E.rate;
33             y=E.tax;
34             if(d[v]<(d-y)*x){
35                 d[v]=(d-y)*x;
36                 if(vis[v]==0) Q.push(v),vis[v]=1;
37             }
38             if(d[S]>V) return 1;
39         }
40     }
41     return 0;
42 }
43
44 int main(){
45     scanf("%d %d %d %lf",&N,&M,&S,&V);
46     int a,b;
47     double c,d;
48     for(int i=1;i<=M;i++){
49         scanf("%d %d %lf %lf",&a,&b,&c,&d);
50         E[a].push_back((node){b,c,d});
51         scanf("%lf %lf",&c,&d);
52         E.push_back((node){a,c,d});
53     }
54     if(SPFA()) cout<<"YES"<<endl;
55     else cout<<"NO"<<endl;
56     return 0;
57 }
　　2.Floyd
　　看到网上有人用Floyd做，用两次Floyd，找正环，就是第一次相当于赋予一个初始值，然后第二次，如果还能再增加的话，相当于形成了一个正环。
　　循环一圈，肯定能增加初始的钱。（很巧妙的方法，OrzOrz。。。



1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <iostream>
5 using namespace std;
6
7 double map[111],G1[111][111],G2[111][111],d[111];
8 int n,m,s;
9
10 int Floyd(){
11     for(int i=1;i<=n;i++) d=map;
12     for(int k=1;k<=n;k++)
13     for(int i=1;i<=n;i++)
14     for(int j=1;j<=n;j++)
15     if((map-G2[j])*G1[j]>map[j])
16     map[j]=(map-G2[j])*G1[j];
17     for(int i=1;i<=n;i++) if(d<map) return 1;
18     return 0;
19 }
20
21 int main(){
22     memset(map,0,sizeof(map));
23     memset(G1,0,sizeof(G1));
24     memset(G2,0,sizeof(G2));
25     double v;
26     cin>>n>>m>>s>>v;
27     for(int i=1;i<=m;i++){
28         int a,b;
29         double c,d,e,f;
30         cin>>a>>b>>c>>d>>e>>f;
31         G1[a]=c;G2[a]=d;
32         G1[a]=e;G2[a]=f;
33     }
34     map=v;
35     Floyd();
36     if(Floyd()) cout<<"YES"<<endl;
37     else cout<<"NO"<<endl;
38     return 0;
39 }