点击打开链接hdu 1217
思路:最短路变形题(floyd 或 SPFA)
分析:
2 题目要求的是经过一轮的转换之后,原来的比例能够大于1。比如原先的“美元:美元 = 1:1”,最后要求能够达到“美元:美元 > 1”
3 假设dis[i][j]表示“i : j”的比例,那么初始化dis[i][i] = - 1。
4 由于n最大为30,所以果断选择floyd算法。但是这里有个地方不同的是,这里并不是要求最小而是求最大,所以应该要把“小于改成大于”
5 最后只要能够找到一种货币的兑换比例大于1即满足条件
代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
#define MAXN 40
int n , m , flag;
double dis[MAXN][MAXN];
char ch[MAXN][MAXN];
/*返回最大值*/
double max(double a , double b){
return a > b ? a : b;
}
/*floyd算法*/
void floyd(){
for(int k = 1 ; k <= n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
dis[i][j] = max(dis[i][k]*dis[k][j] , dis[i][j]);/*求最大值*/
}
}
}
int main(){
double v;
int a , b , cnt;
char str1[MAXN] , str2[MAXN];
cnt = 1;
while(scanf("%d" , &n) && n){
flag = 0;
memset(dis , 0 , sizeof(dis));
/*初始化为-1*/
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
dis[i][j] = -1;
}
for(int i = 1 ; i <= n ; i++)
scanf("%s" , ch[i]);
scanf("%d" , &m);
for(int i = 0 ; i < m ; i++){
scanf("%s%lf%s" , str1 , &v , str2);
for(int i = 1 ; i <= n ; i++){
if(!strcmp(str1 , ch[i]))
a = i;
if(!strcmp(str2 , ch[i]))
b = i;
}
if(dis[a][b] < v)
dis[a][b] = v;
}
floyd();
for(int i = 1 ; i <= n ; i++){
if(dis[i][i] > 1.0){/*找到一种满足条件即可*/
flag = 1;
break;
}
}
if(flag)
printf("Case %d: Yes\n" , cnt++);
else
printf("Case %d: No\n" , cnt++);
}
return 0;
}
/*利用SPFA来判断是否存在环,只要能够形成环就说明满足条件*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 40
#define INF 0xFFFFFFF
int n , m , flag;
double value[MAXN][MAXN];
double dis[MAXN];
int vis[MAXN];
int num[MAXN];
char ch[MAXN][100];
queue<int>q;
void SPFA(int s){
while(!q.empty())
q.pop();
memset(vis , 0 , sizeof(vis));
memset(dis , 0 , sizeof(dis));
memset(num , 0 , sizeof(num));
dis[s] = 1; vis[s] = 1; q.push(s); while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = 1 ; i <= n ; i++){ if(value[x][i]){ if(dis[i] < dis[x] * value[x][i]){ dis[i] = dis[x] * value[x][i]; num[i]++; if(num[i] >= n){/*判断当前的边的松弛操作是否大于等于n*/
flag = 1; return; } if(!vis[i]){ vis[i] = 1; q.push(i); } } } } }} int main(){ int a , b , cnt = 1; double rate; char str1[MAXN] , str2[MAXN]; while(scanf("%d" , &n) && n){ memset(value , 0 , sizeof(value)); for(int i = 1 ; i <= n ; i++){ scanf("%s" , ch[i]);
value[i][i] = 1; } scanf("%d" , &m); for(int i = 0 ; i < m ; i++){ scanf("%s %lf %s" , str1 , &rate , str2); for(int i = 1 ; i <= n ; i++){ if(!strcmp(ch[i] , str1)) a = i; if(!strcmp(ch[i] , str2)) b = i; } value[a][b] = rate; } flag = 0; for(int i = 1 ;
i <= n ; i++){ SPFA(i); if(flag) break; } if(flag) printf("Case %d: Yes\n" , cnt++); else printf("Case %d: No\n" , cnt++); } return 0;}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
HDU图论题目分类
自己做的HDU ACM已经AC的题目
hdu 1005.比较简单的一道题,有兴趣的可以看看。