随笔-65  评论-6  文章-0  trackbacks-0
/*哈希*//*31MS*/
 1 #include <cstdio>
 2 #include <string>
 3 using namespace std;
 4 
 5 double exchange[30][30];
 6 unsigned int currencys[30];
 7 int n,m;
 8 
 9 unsigned int ELFHash(char *str){
10     unsigned int hash = 0;
11     unsigned int x    = 0;
12     while (*str){
13         hash = (hash << 4) + (*str++);
14         if ((x = hash & 0xF0000000L) != 0){
15             hash ^= (x >> 24);
16             hash &= ~x;
17         }
18     }
19     return (hash & 0x7FFFFFFF);
20 }
21 inline int findSame(char a[]){
22     int i,p=ELFHash(a);
23     for(i=0;i<n;i++)
24         if(currencys[i]==p)
25             return i;
26     return -1;
27 }
28 bool floyd(){
29     int i,j,k;
30     for(k=0;k<n;k++)
31         for(i=0;i<n;i++)
32             for(j=0;j<n;j++)
33                 if(exchange[i][k]*exchange[k][j]>exchange[i][j])
34                     exchange[i][j]=exchange[i][k]*exchange[k][j];
35     for(i=0;i<n;i++)
36             if(exchange[i][i]>1)
37                 return true;
38     return false;
39 }
40 int main(){
41     #ifdef ONLINE_JUDGE
42     #else
43         freopen("in.txt","r",stdin);
44     #endif
45     int no=1;
46     while (scanf("%d",&n)&&n){
47         memset(exchange,0,sizeof(exchange));
48         int i;
49         char curren[40];
50         for(i=0;i<n;i++){
51             scanf("%s",curren);
52             currencys[i]=ELFHash(curren);
53         }
54         scanf("%d",&m);
55         while (m--){
56             char str[2][40];
57             double ex;
58             scanf("%s%lf%s",str[0],&ex,str[1]);
59             exchange[findSame(str[0])][findSame(str[1])]=ex;
60         }
61         if(floyd()) printf("Case %d: Yes\n",no++);
62         else printf("Case %d: No\n",no++);
63 
64     }
65     return 0;
66 }
/*map容器*/ /*62MS*/
 1 #include <cstdio>
 2 #include <string>
 3 #include <map>
 4 using namespace std;
 5 
 6 map<string,int>mapmap;
 7 double exchange[30][30];
 8 int n,m;
 9 
10 bool floyd(){
11     int i,j,k;
12     for(k=0;k<n;k++)
13         for(i=0;i<n;i++)
14             for(j=0;j<n;j++)
15                 if(exchange[i][k]*exchange[k][j]>exchange[i][j])
16                     exchange[i][j]=exchange[i][k]*exchange[k][j];
17     for(i=0;i<n;i++)
18             if(exchange[i][i]>1)
19                 return true;
20     return false;
21 }
22 int main(){
23     #ifdef ONLINE_JUDGE
24     #else
25         freopen("in.txt","r",stdin);
26     #endif
27     int no=1;
28     while (scanf("%d",&n)&&n){
29         memset(exchange,0,sizeof(exchange));
30         mapmap.clear();
31         int i;
32         char currencys[40];
33         for(i=0;i<n;i++){
34             scanf("%s",currencys);
35             mapmap[currencys]=i;
36         }
37         scanf("%d",&m);
38         while (m--){
39             char str[2][40];
40             double ex;
41             scanf("%s%lf%s",str[0],&ex,str[1]);
42             exchange[mapmap[str[0]]][mapmap[str[1]]]=ex;
43         }
44         if(floyd()) printf("Case %d: Yes\n",no++);
45         else printf("Case %d: No\n",no++);
46         mapmap.clear();
47     }
48     return 0;
49 }
/*普通字符串处理*//*46MS*/
 1 #include <string.h>
 2 #include <cstdio>
 3 
 4 char currencys[30][40];
 5 double exchange[30][30];
 6 int n,m;
 7 int findSame(char a[]){
 8     int i;
 9     for(i=0;i<n;i++)
10         if(strcmp(a,currencys[i])==0)
11             return i;
12     return -1;
13 }
14 bool floyd(){
15     int i,j,k;
16     for(k=0;k<n;k++)
17         for(i=0;i<n;i++)
18             for(j=0;j<n;j++)
19                 if(exchange[i][k]*exchange[k][j]>exchange[i][j])
20                     exchange[i][j]=exchange[i][k]*exchange[k][j];
21     for(i=0;i<n;i++)
22             if(exchange[i][i]>1)
23                 return true;
24     return false;
25 }
26 int main(){
27     #ifdef ONLINE_JUDGE
28     #else
29         freopen("in.txt","r",stdin);
30     #endif
31     int no=1;
32     while (scanf("%d",&n)&&n){
33         memset(exchange,0,sizeof(exchange));
34         int i;
35         for(i=0;i<n;i++)
36             scanf("%s",currencys[i]);
37         scanf("%d",&m);
38         while (m--){
39             char str[2][40];
40             double ex;
41             scanf("%s%lf%s",str[0],&ex,str[1]);
42             exchange[findSame(str[0])][findSame(str[1])]=ex;
43         }
44         if(floyd()) printf("Case %d: Yes\n",no++);
45         else printf("Case %d: No\n",no++);
46     }
47     return 0;
48 }

posted on 2012-03-23 12:52 Leo.W 阅读(199) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理