題目連結:點選打開連結
題意:
一個人有一種鈔票,面值S;
銀行有N種鈔票,每兩種鈔票之間可以進行兌換;
其規則是:
S' = (S - com) * rate
其中 com 是手續費,rate 是兌換率,S' 是最終的錢;
問經過多次兌換後,錢是否會增加;
了解:
這就是一個負環問題;
不過說起來應該叫“正環”;
先建圖,然後推導遞推式;
把遞推是改一下就可以知道;
遞推式:
d[v] = max(d[v], fac(d[u]));
其中 fac() 是上述計算規則;
根據spfa;
如果有些點一直都在進隊列;
那麼它們的值一直在增大;
那麼就說明存在“正環”;
代碼如下:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x7fffffff;
const double EPS = 1e-7;
typedef pair<int, int> PII;
#define X first
#define Y second
const int MAXE = 222;
const int MAXV = 222;
struct node {
int to, next;
double rate;
double com;
}e[MAXE * 2];
int n, m, s;
double value;
int head[MAXV];
int tot = 0;
void init() {
memset(head, -1, sizeof head);
tot = 0;
}
void add_edge(int u, int v, double rate, double com) {
e[tot].to = v;
e[tot].next = head[u];
e[tot].rate = rate;
e[tot].com = com;
head[u] = tot++;
}
double dis[MAXV];
int outque[MAXV];
bool vis[MAXV];
bool spfa() {
for (int i = 1; i <= n; ++i) {
dis[i] = 0;
vis[i] = false;
outque[i] = 0;
}
queue<int> que;
que.push(s);
dis[s] = value;
vis[s] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
if (++outque[u] > n) {
return false;
}
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
double tp = (dis[u] - e[i].com) * e[i].rate;//cout << dis[u] << endl;
if (tp - dis[v] < EPS) {
continue;
}
dis[v] = tp;
if (vis[v] == true) {
continue;
}
que.push(v);
vis[v] = true;
}
}
return true;
}
int main() {
cin >> n >> m >> s >> value;
init();
for (int i = 0; i < m; ++i) {
int u, v;
double rate_u_v, com_u_v, rate_v_u, com_v_u;
cin >> u >> v >> rate_u_v >> com_u_v >> rate_v_u >> com_v_u;
add_edge(u, v, rate_u_v, com_u_v);
add_edge(v, u, rate_v_u, com_v_u);
}
if (spfa()) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}//for (int i = 1; i <= n; ++i) cout << dis[i] << " ";cout << endl;
return 0;
}