poj 1060

关于bellman-ford的一些思考

松弛操作

这个算法的要点在于对给定图G(N,E)$G(N,E)$中的所有边进行松弛操作，假如有一条边a→b$a\to b$，那么我们就可以通过这条边进行松弛，b.d=max(b.d,a.d+w(a,b))$b.d=max(b.d,a.d+w(a,b))$，且对于距离的更新操作，只能根据松弛操作来进行。

关于这道题目的理解

这道题目可以用bf$bf$算法进行求解是因为，交换是双向的，可以经过正环不断增加，然后再兑换为原来的货币。

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

struct Node{
    int a,b;
    double r,m;
    Node(int a,int b, double r, double m):a(a),b(b),r(r),m(m){}
};
double dis[101];
int n,m,s;
double v;
vector<Node> nodelist;
bool bf(){
    // init the dis;
    memset(dis,0, sizeof(dis));
    dis[s] = v;
    bool flag = false;
    for (int i = 0; i < n - 1; ++i) {
        flag = false;
        for (int j = 0; j < nodelist.size(); ++j) {
            Node node = nodelist[j];
            if (dis[node.b] < (dis[node.a]-node.m)*node.r){
                dis[node.b] = (dis[node.a] - node.m)*node.r;
                flag = true;
            }
        }
        if (!flag) return false;
    }

    for (int i = 0; i < nodelist.size(); ++i) {
        Node node = nodelist[i];
        if (dis[node.b] < (dis[node.a]-node.m)*node.r){
            return true;
        }
    }
    return false;
}
int main(){
    cin>>n>>m>>s>>v;
    int a, b;
    double rab, cab, rba, cba;
    while (m--){
        cin>>a>>b>>rab>>cab>>rba>>cba;
        nodelist.push_back(Node(a, b, rab, cab));
        nodelist.push_back(Node(b, a, rba, cba));
    }
    /**
     * bellman-ford algorithm
     */
    puts(bf()?"YES":"NO");
}

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXSIZE = 105;
int N, M, S;
double V;
double rate[MAXSIZE][MAXSIZE];
double commission[MAXSIZE][MAXSIZE];
double dis[MAXSIZE];

bool bf() {
    memset(dis, 0, sizeof(dis));
    dis[S] = V;
    bool flag;
    for (int k = 1; k <= N-1; ++k) {
        flag = false;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                //说明有一条从i->j的边可以用来松弛
                if (i == j) continue;
                if (rate[i][j]) {
                    if (dis[j] < rate[i][j] * (dis[i] - commission[i][j])){
                        flag = true;
                        dis[j] = rate[i][j] * (dis[i] - commission[i][j]);
                    }
                }
            }
        }
        if (!flag) return false;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            //说明有一条从i->j的边可以用来松弛
            if (i == j) continue;
            if (rate[i][j]) {
                if (dis[j] < rate[i][j] * (dis[i] - commission[i][j])){
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
//    freopen("../in.txt", "r", stdin);
    cin >> N >> M >> S >> V;
    memset(rate, 0, sizeof(rate));
    for (int i = 0; i < M; ++i) {
        int a, b;
        double rab, rba, cab, cba;
        cin >> a >> b >> rab >> cab >> rba >> cba;
        rate[a][b] = rab, rate[b][a] = rba;
        commission[a][b] = cab, commission[b][a] = cba;
    }
    puts(bf() ? "YES" : "NO");
}