Posted on 2008-10-16 15:15
歲月流逝 閱讀(230)
評論(0) 編輯 收藏 引用
題意 ： 就是套匯的問題，匯率Rab， 增加了一個手續(xù)費 Cab 。。。。。。。每次的結(jié)果是 (本金 - 手續(xù)費) * 匯率，而且一個人擁有的錢的類型是已知的，擁有的value 錢的個數(shù)也是已知的， 問你能不能增值。
輸入 ：
3 2 1 20.0 //錢種類個數(shù) 匯率的個數(shù)，擁有第幾種錢， 擁有多少錢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
算法：判斷有無正環(huán)，采用bellman的最大路的松弛法去做.PS:要注意兩個條件的跳出：1.有正環(huán)會不停的松弛，只要>val后叫結(jié)束循環(huán).2.一旦不能循環(huán)了就結(jié)束循環(huán),這是返回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