Posted on 2008-10-16 15:15
岁月流逝 阅读(209)
评论(0) 编辑 收藏 引用
题意 ： 就是套汇的问题，汇率Rab， 增加了一个手续费 Cab 。。。。。。。每次的结果是 (本金 - 手续费) * 汇率，而且一个人拥有的钱的类型是已知的，拥有的value 钱的个数也是已知的， 问你能不能增值。
输入 ：
3 2 1 20.0 //钱种类个数 汇率的个数，拥有第几种钱， 拥有多少钱1 2 1.00 1.00 1.00 1.00 //钱a， 钱b， rab， cab， rba， cba2 3 1.10 1.00 1.10 1.00
算法：判断有无正环，采用bellman的最大路的松弛法去做.PS:要注意两个条件的跳出：1.有正环会不停的松弛，只要>val后叫结束循环.2.一旦不能循环了就结束循环,这是返回dist[s]>val就可以了
#include<stdio.h>
#include<memory.h>
struct node
{
int u,v;
double r,c;
};
int n,m,s;
double val;
node edge[1001];
int eg;
#define eps 1e-8
bool bellman()
{
double dist[102];
memset(dist,0,sizeof(dist));
int i;
int flag = 0;
dist[s] = val;
while(dist[s]<=val+eps)
{
flag = 0;
for(i = 0;i<=eg;i++)
{
if(dist[edge[i].v]+eps<(dist[edge[i].u]-edge[i].c)*edge[i].r)
{
dist[edge[i].v] = (dist[edge[i].u]-edge[i].c)*edge[i].r;
flag=1;
}
}
if(!flag)
return dist[s]>val;
}
return true;
}
int main()
{
int i;
int a,b;
double rab, cab, rba ,cba;
while(scanf("%d %d %d %lf",&n,&m,&s,&val)!=EOF)
{
eg = 0;
for(i = 0;i<m;i++)
{
scanf("%d %d %lf %lf %lf %lf",&a,&b,&rab,&cab,&rba,&cba);
edge[eg].u = a;
edge[eg].v = b;
edge[eg].r = rab;
edge[eg].c = cab;
eg++;
edge[eg].u = b;
edge[eg].v = a;
edge[eg].r = rba;
edge[eg].c = cba;
eg++;
}
if(bellman())
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
Tags -
bellman ,
松弛 ,
最长路
文章来源:
http://www.feng5166.com/blog/read.php?125