Currency Exchange(寻找正权环)

寻找正权环就是常规Bellman算法的反向操作,将松弛更小值改为松弛更大值。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
#include <map>
#include <stack>
#define MAXN 104
#define MOD 1000000009
#define INF 0x7ffffff
#define lowbit(x) (x)&(-x)

using namespace std;            

struct EDGE{
    int u;
    int v;
    double r;
    double c;
}edge[204];

int n,m,s;
double v;

double dis[MAXN];
int cnt;

void init(){
    for(int i=1;i<=n;++i){
        dis[i] = 0.0;
    }
    dis[s] = v;
    cnt = 0;
}

bool Bellman(){
    for(int i=1;i<n;++i){
        for(int j=0;j<cnt;++j){
            int u = edge[j].u;
            int v = edge[j].v;
            double r = edge[j].r;
            double c = edge[j].c;
            if(dis[v] < (dis[u]-c)*r){
                dis[v] = (dis[u]-c)*r;
            }
        }        
    }
    for(int i=0;i<cnt;++i){
        int u = edge[i].u;
        int v = edge[i].v;
        double r = edge[i].r;
        double c = edge[i].c;
        if(dis[v] < (dis[u]-c)*r){
            return true;
        }
    }
    return false;
}

inline void add(int u,int v,double r,double c){
    edge[cnt].u = u;
    edge[cnt].v = v;;
    edge[cnt].r = r;
    edge[cnt].c = c;
    ++cnt;
}

int main(){
    while(cin >> n >> m >> s >> v){
        init();
        int a,b;
        double r1,c1,r2,c2;
        while(m--){
            cin >> a >> b;
            cin >> r1 >> c1 >> r2 >> c2;
            add(a,b,r1,c1);
            add(b,a,r2,c2);    
        }
        if(Bellman()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

 

上一篇:常用 jstl 表达式


下一篇:【Python 12】汇率兑换5.0(Lambda函数)