当前位置: 首页 > >

poj 2240 Arbitrage(Bellman_ford变形)

发布时间:

题目链接:http://poj.org/problem?id=2240


题目就是要通过还钱涨自己的本钱最后还能换回到自己原来的钱种。


就是判一下有没有负环那么就直接用bellman_ford来判断有没有负环


?


#include
#include
#include
using namespace std;
int n , m , s , a , b , counts;
double rx , ry , cx , cy , v , dis[110];
struct TnT {
int u , v;
double r , c;
}T[210];
bool relax(int u , int v , double r , double c) {
if(dis[v] < (dis[u] - c) * r) {
dis[v] = (dis[u] - c) * r;
return true;
}
return false;
}
bool bellman_ford() {
bool flag;
for(int i = 1 ; i < n ; i++) {
flag = false;
for(int j = 1 ; j <= counts ; j++) {
if(relax(T[j].u , T[j].v , T[j].r , T[j].c))
flag = true;
}
if(dis[s] > v)
return true;
if(!flag)
return false;
}
for(int i = 1 ; i <= counts ; i++) {
if(relax(T[i].u , T[i].v , T[i].r , T[i].c))
return true;
}
return false;
}
int main() {
cin >> n >> m >> s >> v;
for(int i = 1 ; i <= n ; i++) {
dis[i] = 0.0;
}
dis[s] = v;
counts = 0;
for(int i = 1 ; i <= m ; i++) {
cin >> a >> b >> rx >> cx >> ry >> cy;
T[++counts].u = a , T[counts].v = b , T[counts].r = rx , T[counts].c = cx;
T[++counts].u = b , T[counts].v = a , T[counts].r = ry , T[counts].c = cy;
}
int flag = bellman_ford();
if(flag) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}


转载于:https://www.cnblogs.com/TnT2333333/p/6544598.html



友情链接: