心累,陕西邀请赛学校不支持,可能要自费了。。
思路:套用Bellman-Ford判断负环的思路,把大于改成小于即可判定是否存在从源点能到达的正环。如果存在正环,那么完全多跑几次正环就可以把钱增加到足够返回到S并且大于原来的金额。
AC代码
#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 200 + 5; int u[maxn], v[maxn]; double r[maxn], c[maxn]; double d[maxn]; bool bell(double st, int s, int n, int m) { for(int i = 0; i < n; ++i) d[i] = -inf; d[s] = st; for(int i = 0; i < n-1; ++i) for(int j = 0; j < m; ++j) { int x = u[j], y = v[j]; if(d[x] > -inf) d[y] = max(d[y], (d[x] - c[j])*r[j]); } for(int i = 0; i < m; ++i) { int x = u[i], y = v[i]; if(d[y] < (d[x] - c[i])*r[i] && d[x] > -inf) return true; //存在正环 } return false; } int main() { int n, m, s; double V; while(scanf("%d%d%d%lf", &n, &m, &s, &V) == 4) { int cur = 0; for(int i = 0; i < m; ++i) { scanf("%d%d", &u[cur], &v[cur]); scanf("%lf%lf", &r[cur], &c[cur]); ++cur; u[cur] = v[cur-1], v[cur] = u[cur-1]; scanf("%lf%lf", &r[cur], &c[cur]); ++cur; } if(bell(V, s, n, cur)) printf("YES\n"); else printf("NO\n"); } return 0; }
如有不当之处欢迎指出!