本文主要是介绍POJ 1860 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题用的是Bellman Ford检查图里面是否有负环的做法。稍微不同的是，这里检测的是“正环”，即从S出发，看是否存在一个环，使得换到的钱（按S计算）能够不断增加。值得注意的是S不一定在这个环上，但是由于按照这个环的次序交换货币能使货币总量无限增加，总可以再换到S，使得钱比一开始增加了。
| thestoryofsnow | 1860 | Accepted | 152K | 32MS | C++ | 2285B |
/*
ID: thestor1
LANG: C++
TASK: poj1860
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;const int MAXN = 100;
const int MAXM = 100;class Edge
{
public:int A, B;double commission, rate;int next;Edge() : next(-1) {};Edge(int A, int B, double commission, double rate) : commission(commission), rate(rate), next(-1) {}
};void addEdge(const int A, const int B, const double Cab, const double Rab, Edge edges[], int &edgeno)
{edges[edgeno].A = A;edges[edgeno].B = B;edges[edgeno].commission = Cab;edges[edgeno].rate = Rab;edgeno++;
}int main()
{Edge edges[2 * MAXM];int edgeno = 0;int N, M, S;double V;scanf("%d%d%d%lf", &N, &M, &S, &V);S--;for (int i = 0; i < M; ++i){int A, B;double Rab, Cab, Rba, Cba; scanf("%d%d%lf%lf%lf%lf", &A, &B, &Rab, &Cab, &Rba, &Cba);A--, B--;addEdge(A, B, Cab, Rab, edges, edgeno);addEdge(B, A, Cba, Rba, edges, edgeno);}// printf("[debug]edges:\n");// for (int e = 0; e < edgeno; ++e)// {// printf("[%d]%d->%d(%lf, %lf)\n", e, edges[e].A, edges[e].B, edges[e].commission, edges[e].rate);// }// Bellman–Ford algorithm// see: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithmdouble distance[MAXN];for (int i = 0; i < N; ++i){distance[i] = 0;}distance[S] = V;for (int i = 0; i < N - 1; ++i){for (int e = 0; e < edgeno; ++e){// edges[e].A, edges[e].B, edges[e].commission, edges[e].ratedouble dis = (distance[edges[e].A] - edges[e].commission) * edges[e].rate;if (dis > distance[edges[e].B]){distance[edges[e].B] = dis;}}}bool canIncrease = false;// check if there is "positive cycle" (similar with negative cycle)for (int e = 0; e < edgeno; ++e){// edges[e].A, edges[e].B, edges[e].commission, edges[e].ratedouble dis = (distance[edges[e].A] - edges[e].commission) * edges[e].rate;if (dis > distance[edges[e].B]){canIncrease = true; break;}}if (canIncrease){printf("YES\n");}else{printf("NO\n");}return 0;
}这篇关于POJ 1860 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
