传送门：http://poj.org/problem?id=1860
题意：给出每两种货币之间交换的手续费和汇率，求出从当前货币s开始交换回到s，能否使本金增多。
思路：bellman-Ford模板题。直接跑一遍，判断是否存在正环就好了。（复杂度n*m）
代码：
#include<iostream>
using namespace std;
int n; //货币种数
int m; //兑换点数量
int s; //持有第s种货币
double v; //持有的s货币的本金
double dis[101]; //s到各点的权值
struct node
{
int a; //货币a
int b; //货币b
double r; //汇率
double c; //手续费
} num[202];
bool Bellman_Ford()
{
for(int i = 1; i <= n; i++)
dis[i] = 0;
//初始源点的值即为本金
dis[s] = v;
for(int i = 1; i < n; i++)
{
bool flag = false;
for(int j = 1; j <= 2 * m; j++)
{
if(dis[num[j].b] < (dis[num[j].a] - num[j].c)*num[j].r)
{
dis[num[j].b] = (dis[num[j].a] - num[j].c) * num[j].r;
flag = true;
}
}
if(!flag)
break;
}
//如果还能增加，则代表存在正环
for(int j = 1; j <= 2 * m; j++)
{
if(dis[num[j].b] < (dis[num[j].a] - num[j].c) * num[j].r)
return true;
}
return false;
}
int main()
{
while(cin >> n >> m >> s >> v)
{
for(int i = 1; i <= 2 * m; i += 2)
{
cin >> num[i].a >> num[i].b >> num[i].r >> num[i].c >> num[i + 1].r >> num[i + 1].c;
num[i + 1].a = num[i].b;
num[i + 1].b = num[i].a;
}
if(Bellman_Ford())
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}