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;
9 int vis;
10 int N,M,S;
11 double V;
12 struct node{
13 int to;
14 double rate,tax;
15 };
16
17 vector <node> E;
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=V;vis=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<(d-y)*x){
35 d=(d-y)*x;
36 if(vis==0) Q.push(v),vis=1;
37 }
38 if(d>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.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,G1,G2,d;
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)*G1>map)
16 map=(map-G2)*G1;
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=c;G2=d;
32 G1=e;G2=f;
33 }
34 map=v;
35 Floyd();
36 if(Floyd()) cout<<"YES"<<endl;
37 else cout<<"NO"<<endl;
38 return 0;
39 }
页:
[1]