spfa找正环
注意:POJ1860这题卡精度,要加eps(这个卡了好久qwq,还以为spfa被卡了)
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;
const double eps = 1e-9;
int n, m, s, cnt;
double v;
int e[N], ne[N], h[N], idx;
double w[N], f[N], d[N];
int st[N], q[N];
void add(int a, int b, double x, double y) {
e[idx] = b, w[idx] = x, f[idx] = y, ne[idx] = h[a], h[a] = idx++;
}
bool spfa() {
memset(d, -0x3f, sizeof d);
d[s] = v;
int hh = 0, tt = 1;
q[0] = s;
while (hh != tt) {
int t = q[hh++];
if (hh == N) hh = 0;
st[t] = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] + eps < (d[t] - f[i]) * w[i]) {
d[j] = (d[t] - f[i]) * w[i];
if (j == s) return true;
if (!st[j]) {
st[j] = 1;
q[tt++] = j;
if (tt == N) tt = 0;
}
}
}
}
return false;
}
int main() {
cin >> n >> m >> s >> v;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
double rab, cab, rba, cba;
cin >> a >> b >> rab >> cab >> rba >> cba;
add(a, b, rab, cab);
add(b, a, rba, cba);
}
if (spfa()) puts("YES");
else puts("NO");
return 0;
}