| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 17745 | Accepted: 6262 |
Description
Input
Output
Sample Input
3 2 1 20.0 1 2 1.00 1.00 1.00 1.00 2 3 1.10 1.00 1.10 1.00
Sample Output
YES
题意：
有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加
货币的交换是可以重复多次的，所以我们需要找出是否存在正权回路，且最后得到的s金额是增加的
怎么找正权回路呢？（正权回路：在这一回路上，顶点的权值能不断增加即能一直进行松弛）
分析：
一种货币就是一个点
一个“兑换点”就是图上两种货币之间的一个兑换方式，是双边，但A到B的汇率和手续费可能与B到A的汇率和手续费不同。
唯一值得注意的是权值，当拥有货币A的数量为V时，A到A的权值为K，即没有兑换
而A到B的权值为(V-Cab)*Rab
本题是“求最大路径”，之所以被归类为“求最小路径”是因为本题题恰恰与bellman-Ford算法的松弛条件相反，求的是能无限松弛的最大正权路径，但是依然能够利用bellman-Ford的思想去解题。
因此初始化dis(S)=V 而源点到其他点的距离（权值）初始化为无穷小（0），当s到其他某点的距离能不断变大时，说明存在最大路径；如果可以一直变大，说明存在正环。判断是否存在环路，用Bellman-Ford和spfa都可以。
spfa算法：
//spfa
//376K 63MS C++
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int N = 110;
int n, m, s;
double dis[N], v, rate[N][N], cost[N][N];
bool spfa(int start)
{
bool inq[110];
memset(inq, 0, sizeof(inq));
memset(dis, 0, sizeof(dis));
dis[start] = v;
queue<int> Q;
Q.push(start);
inq[start] = true;
while(!Q.empty())
{
int x = Q.front();
Q.pop();
inq[x] = false;
for(int i = 0; i <= n; i++)
{
if(dis[i] < (dis[x] - cost[x][i]) * rate[x][i])
{
dis[i] = (dis[x] - cost[x][i]) * rate[x][i];
if(dis[start] > v)
return true;
if(!inq[i])
{
Q.push(i);
inq[i] = true;
}
}
}
}
return false;
}
int main()
{
int i, j;
while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
{
int a, b;
double rab, rba, cab, cba;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
if(i == j)
rate[i][j] = 1;
else
rate[i][j] = 0;
cost[i][j] = 0;
}
for(i = 0; i < m; i++)
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
rate[a][b] = rab;
rate[b][a] = rba;
cost[a][b] = cab;
cost[b][a] = cba;
}
if(spfa(s))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
//Bellman-Ford
//192K 0MS C++
#include<stdio.h>
#include<string.h>
int n, m, s, C;
double v, dis[110];
struct point
{
int a, b;
double rate, cost;
}p[500];
bool Bellman_Ford()
{
memset(dis, 0, sizeof(dis)); //此处与Bellman-Ford的处理相反，初始化为源点到各点距离0，到自身的值为原值
dis[s] = v;
for(int i = 1; i <= n - 1; i++)
{
bool flag = false;
for(int j = 0; j < C; j++)
{
int a = p[j].a, b = p[j].b;
double r = p[j].rate, c = p[j].cost;
if(dis[b] < (dis[a] - c) * r)
{
dis[b] = (dis[a] - c) * r;
flag = true;
}
}
if(!flag)
break;
}
for(int i = 0; i < C; i++)
if(dis[p[i].b] < (dis[p[i].a] - p[i].cost) * p[i].rate) //正环能够无限松弛
return true;
return false;
}
int main()
{
int i, j, a, b;
double rab, rba, cab, cba;
while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
{
C = 0;
for(i = 0; i < m; i++)
{
scanf("%d%d%lf%lf%lf%lf",&a, &b, &rab, &cab, &rba, &cba);
p[C].a = a;
p[C].b = b;
p[C].rate = rab;
p[C++].cost = cab;
p[C].a = b;
p[C].b = a;
p[C].rate = rba;
p[C++].cost = cba;
}
if(Bellman_Ford())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}原文：http://blog.csdn.net/lyhvoyage/article/details/19281013