PKU 1086解题报告

发布时间:2016-12-8 8:17:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"PKU 1086解题报告",主要涉及到PKU 1086解题报告方面的内容,对于PKU 1086解题报告感兴趣的同学可以参考一下。

这道提很多人说是最短路径问题,可是我认为,用最短路的算法不稳定,及时间复杂度不缺定。 题意是关于换钱的问题,多种货币,换来换去,最后还是那种钱,但是钱却多了。 换钱法则是:自己的钱 减去 税费后的钱乘以汇率。 我用的是搜索方法。 代码中慢慢解释。 1 2 3 #include<stdio.h> 4 5 #include<string.h> 6 7 #include<queue> 8 9 using namespace std; 10 11 const int N=105; 12 13 int n,m,s,p1,p2; 14 15 double sum,r[N][N],c[N][N]; 16 17 18 19 //若可以赚钱,那么从某一起点起存在一条回路,转一圈回到起点时钱增多了,而且从初始位置到那个起点的过程中钱不为负。 20 21 //对于不赚钱的,就需要设置一个开关来控制出口,及下面的V数组。首先每个定点初始值为0,从而保证每个定点可以至少访问一次。 22 23 //如果不赚钱时,将不能在访问其他定点,循环也就结束。 24 25 bool ok() 26 27 { 28 29 double d[N]; 30 31 memset(d,0,sizeof(d)); 32 33 d[s]=sum; 34 35 bool v[N]; 36 37 memset(v,0,sizeof(v)); 38 39 v[s]=1; 40 41 42 43 queue<int>que; 44 45 que.push(s); 46 47 while(!que.empty()) 48 49 { 50 51 int u=que.front(); 52 53 que.pop(); 54 55 v[u]=0; 56 57 58 59 for(int i=0;i<n;i++) 60 61 { 62 63 double t=(d[u]-c[u][i])*r[u][i]; 64 65 if(t>d[i]) 66 67 { 68 69 d[i]=t; 70 71 if(!v[i]) 72 73 { 74 75 v[i]=1; 76 77 if(i==s)return 1;//判断是否已经赚钱 78 79 que.push(i); 80 81 } 82 83 } 84 85 } 86 87 } 88 89 return d[s]>sum; 90 91 } 92 93 94 95 int main() 96 97 { 98 99 memset(r,0,sizeof(r)); //初始化,r数组为汇率100 101 memset(c,0X3f,sizeof(c)); //初始化,c数组是税费,由于memset初始化时是一个字节一个字节的初始化的,102 103 //一个字节的最大值就是二进制的7个1,所以是十六进制0X3F.104 105 scanf("%d%d%d%lf",&n,&m,&s,&sum);106 107 s--; //从0开始,所以减1108 109 for(int i=0;i<m;i++)110 111 {112 113 scanf("%d%d",&p1,&p2);114 115 p1--;116 117 p2--;118 119 scanf("%lf%lf%lf%lf",&r[p1][p2],&c[p1][p2],&r[p2][p1],&c[p2][p1]);120 121 }122 123 printf("%s\n",ok()?"YES":"NO"); //OK()函数来判断是否可以赚钱124 125 return 0;126 127 }

上一篇:.NET数据连接和用户验证函数
下一篇:智力测验:硬币问题

相关文章

相关评论