最短路(Bellman_Ford) POJ 1860 Currency Exchange

题目传送门

 /*
最短路(Bellman_Ford):求负环的思路,但是反过来用,即找正环
详细解释:http://blog.csdn.net/lyy289065406/article/details/6645778
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; const int MAXN = + ;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-;
struct NODE
{
int u, v;
double r, c;
}node[MAXN*];
double d[MAXN]; bool Bellman_Ford(int s, int n, int tot, double V)
{
memset (d, , sizeof (d));
d[s] = V;
bool flag;
for (int i=; i<=n-; ++i)
{
flag = false;
for (int j=; j<=tot; ++j)
{
NODE e = node[j];
if (d[e.v] < (d[e.u] - e.c) * e.r)
{
d[e.v] = (d[e.u] - e.c) * e.r; flag = true;
}
}
if (!flag) break;
} for (int i=; i<=tot; ++i)
{
NODE e = node[i];
if (d[e.v] < (d[e.u] - e.c) * e.r) return true;
} return false;
} int main(void) //POJ 1860 Currency Exchange
{
//freopen ("A.in", "r", stdin); int n, m, s;
double V;
while (~scanf ("%d%d%d%lf", &n, &m, &s, &V))
{
int tot = ;
for (int i=; i<=m; ++i)
{
int x, y;
double rab, cab, rba, cba;
scanf ("%d%d%lf%lf%lf%lf", &x, &y, &rab, &cab, &rba, &cba);
//printf ("%d %d %lf %lf %lf %lf\n", x, y, rab, cab, rba, cba);
node[++tot].u = x; node[tot].v = y;
node[tot].r = rab; node[tot].c = cab;
node[++tot].u = y; node[tot].v = x;
node[tot].r = rba; node[tot].c = cba;
} if (Bellman_Ford (s, n, tot, V)) puts ("YES");
else puts ("NO");
} return ;
}

SPFA重写一遍

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std; const int N = 100 + 10;
struct Edge {
int v, nex;
double r, c;
Edge() {}
Edge(int v, double r, double c, int nex) : v (v), r (r), c (c), nex (nex) {}
}edge[N*2];
int head[N];
double d[N];
bool vis[N];
int cnt[N];
int n, m, e;
double val; void init(void) {
memset (head, -1, sizeof (head));
e = 0;
} void add_edge(int u, int v, double r, double c) {
edge[e] = Edge (v, r, c, head[u]);
head[u] = e++;
} bool SPFA(int s) {
memset (vis, false, sizeof (vis));
memset (d, 0, sizeof (d));
memset (cnt, 0, sizeof (cnt));
d[s] = val; cnt[s] = 0; vis[s] = true;
queue<int> que; que.push (s);
while (!que.empty ()) {
int u = que.front (); que.pop ();
vis[u] = false;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v; double r = edge[i].r, c = edge[i].c;
if (d[v] < (d[u] - c) * r) {
d[v] = (d[u] - c) * r;
if (!vis[v]) {
vis[v] = true; que.push (v);
if (++cnt[v] > n) return true;
}
}
}
}
return false;
} int main(void) {
int s;
while (scanf ("%d%d%d%lf", &n, &m, &s, &val) == 4) {
init ();
for (int i=1; i<=m; ++i) {
int u, v;
double r1, c1, r2, c2;
scanf ("%d%d%lf%lf%lf%lf", &u, &v, &r1, &c1, &r2, &c2);
add_edge (u, v, r1, c1); add_edge (v, u, r2, c2);
}
if (SPFA (s)) puts ("YES");
else puts ("NO");
} return 0;
}

  

上一篇:POJ 1860 Currency Exchange 最短路+负环


下一篇:"当前方法的代码已经过优化,无法计算表达式的值"的这个错误的解决方案!!!