POJ——T1860 Currency Exchange
http://poj.org/problem?id=1860Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 29874
Accepted: 11251
题目大意：
´有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加。
题解：
´货币的交换是可以重复多次的，所以我们需要找出是否存在正权回路，且最后得到的s金额是增加的。
所以用SPFA求正环就可以了
DFS求环法：
1 #include <cstring>
2 #include <cstdio>
3
4 #define dou double
5 #define INF 1<<29
6 #define MAX(a,b) ( a>b ?a :b )
7
8 using namespace std;
9
10 const int N(10015);
11 int n,m,s,u,v;
12 dou money,uvr,uvl,vur,vul;
13 int head,sumedge;
14 struct Edge
15 {
16 int to,next;
17 dou rate,lose;
18 Edge(int to=0,int next=0,dou rate=0.00,dou lose=0.00) :
19 to(to),next(next),rate(rate),lose(lose) {}
20 }edge;
21
22 void ins(int from,int to,dou rate,dou lose)
23 {
24 edge[++sumedge]=Edge(to,head,rate,lose);
25 head=sumedge;
26 }
27
28 dou change_money(dou x,dou rate,dou lose)
29 { return (x-lose)*rate ; }
30
31 int vis,if_YES;
32 dou dis;
33
34 void SPFA(int now)
35 {
36 vis=1;
37 if(if_YES) return ;
38 for(int i=head;i;i=edge.next)
39 {
40 int go=edge.to;
41 dou rate=edge.rate,lose=edge.lose;
42 dou cmoney=change_money(dis,rate,lose);
43 if(cmoney>dis)
44 {
45 if(vis)
46 {
47 if_YES=true;
48 break ;
49 }
50 dis=cmoney;
51 SPFA(go);
52 }
53 }
54 vis=0;
55 return ;
56 }
57
58 void init(int n)
59 {
60 if_YES=sumedge=0;
61 memset(dis,0,sizeof(dis));
62 memset(head,0,sizeof(head));
63 }
64
65 int main()
66 {
67 // freopen("made.txt","r",stdin);
68 // freopen("myout.txt","w",stdout);
69
70 while(~scanf("%d%d%d%lf",&n,&m,&s,&money))
71 {
72 if(s>n)
73 {
74 printf("NO\n");
75 continue;
76 }
77 init(n);
78 for(;m;m--)
79 {
80 scanf("%d%d%lf%lf%lf%lf",&u,&v,&uvr,&uvl,&vur,&vul);
81 ins(u,v,uvr,uvl); ins(v,u,vur,vul);
82 }
83 dis=money; SPFA(s);
84 if(if_YES) printf("YES\n");
85 else printf("NO\n");
86 }
87 return 0;
88 }
BFS求环法：
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 int u,v,w;
8 const int maxn = 1011;
9 const int maxm = 10011;
10 const int oo = 1<<29;
11 struct node
12 {
13 int u;
14 int v;
15 double x,y ;
16 int next;
17 }edge;
18 double dis;
19 int m,n,num;
20 double ount;
21 int head,cnt,sum;
22 int vis = {0};
23 queue<int>qu;
24 void add(int u,int v,double x,double y)
25 {
26 edge.u = u ;
27 edge.v = v ;
28 edge.x = x ;
29 edge.y = y ;
30 edge.next = head;
31 head = cnt++ ;
32 }
33 int spfa(int s)
34 {
35 for(int i = 0 ; i < m ; i++)
36 {
37 dis = 0;
38 vis = 0 ;
39 }
40 dis = ount;
41 qu.push(s);
42 vis = 1 ;
43 while(!qu.empty())
44 {
45 int u = qu.front();
46 qu.pop();
47 vis = 0;
48 for(int i = head ; i != -1 ; i = edge.next)
49 {
50 int v = edge.v;
51 if((dis-edge.y)*edge.x > dis)
52 {
53 dis = (dis-edge.y)*edge.x;
54 if(!vis)
55 {
56 vis = 1;
57 qu.push(v);
58 }
59 sum++;
60 if(sum > m)
61 return -1;
62 }
63 }
64 }
65 return 1;
66 }
67 void Init()
68 {
69 cnt = 0 ;
70 memset(head,-1,sizeof(head));
71 memset(sum,0,sizeof(sum));
72 while(!qu.empty())
73 qu.pop();
74 }
75 int main()
76 {
77 freopen("made.txt","r",stdin);
78 freopen("stdout.txt","w",stdout);
79
80 while(scanf("%d %d %d %lf",&m,&n,&num,&ount)!=EOF)
81 {
82 Init();
83 int u,v;
84 double x,y,xx,yy ;
85 for(int i = 0 ; i < n ; i++)
86 {
87 scanf("%d %d %lf %lf %lf %lf",&u,&v,&x,&y,&xx,&yy);
88 add(u,v,x,y);
89 add(v,u,xx,yy);
90 }
91 if(spfa(num) > 0)
92 cout<<"NO"<<endl;
93 else cout<<"YES"<<endl;
94 }
95 return 0;
96 }
页:
[1]