poj 1860 Currency Exchange

18094 단어 Exchange
Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 6628
Accepted: 2097
간단하고 가장 짧은 문제는 벨맨으로 마이너스 고리의 존재 여부를 판단하면 된다
코드:
 

  
    
1 #include < stdio.h >
2 #include < string .h >
3   struct node
4 {
5 int a,b;
6 double rab,cab;
7 }g[ 205 ];
8   int n,m;
9 double dist[ 105 ];
10 int relax( int u, int v, double rab, double cab)
11 {
12 if (dist[v] < (dist[u] - cab) * rab)
13 {
14 dist[v] = (dist[u] - cab) * rab;
15 return 1 ;
16 }
17 return 0 ;
18 }
19 int bellman( int v0, double v)
20 {
21 int i,j;
22 for (i = 1 ;i <= n;i ++ )
23 dist[i] =- 1 ;
24 dist[v0] = v;
25 int flag;
26 for (i = 1 ;i < n;i ++ )
27 {
28 flag = 0 ;
29 for (j = 1 ;j <= 2 * m;j ++ )
30 {
31 if (relax(g[j].a,g[j].b,g[j].rab,g[j].cab))
32 {
33 flag = 1 ;
34 }
35 }
36 if ( ! flag)
37 break ;
38 }
39 for (j = 1 ;j <= m * 2 ;j ++ )
40 {
41 if (relax(g[j].a,g[j].b,g[j].rab,g[j].cab))
42 return 1 ;
43 }
44 return 0 ;
45 }
46 int main()
47 {
48 double v,rab,cab,rba,cba;
49 int i,s,a,b;
50 scanf( " %d%d%d%lf " , & n, & m, & s, & v);
51 for (i = 1 ;i <= m;i ++ )
52 {
53 scanf( " %d%d%lf%lf%lf%lf " , & a, & b, & rab, & cab, & rba, & cba);
54 g[i].a = a;g[i].b = b;
55 g[i].rab = rab;g[i].cab = cab;
56 g[i + m].a = b;g[i + m].b = a;
57 g[i + m].rab = rba;g[i + m].cab = cba;
58 }
59 if (bellman(s,v))
60 printf( " YES
" );
61 else
62 printf( " NO
" );
63 return 0 ;
64 }

좋은 웹페이지 즐겨찾기