http://poj.org/problem?id=1860 题意:有n种货币,m个相互兑换关系,初始拥有货币s共v元,求是否可以财富增加。 题意并不是说要走简单路径,他只是说了简单路径这个东西。 这个题暴露了对
http://poj.org/problem?id=1860
题意:有n种货币,m个相互兑换关系,初始拥有货币s共v元,求是否可以财富增加。
题意并不是说要走简单路径,他只是说了简单路径这个东西。
这个题暴露了对SPFA的认识不够。
首先这个SPFA是没有带优化的,玄学算法不需要优化。
一般的SPFA是节点入队次数超过n次就认为它存在负环,但是这里并不是这样判断(这里就是这样判断,WA是自己写错了,直接返回YES了),存在负环并不代表一定可以兑换回s(说不定在负环里只有0的汇率换回来s,导致白搞)但是这又是怎么阻止算法死循环的呢?
#include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<map> #include<set> #include<stack> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int MAXN = 105; const int MAXM = 1005; int top; int head[MAXN]; struct Edge { int v, nxt; double w1, w2; } edge[MAXM]; void init() { top = 0; memset(head, -1, sizeof(head)); } void add_edge(int u, int v, double w1, double w2) { ++top; edge[top].v = v; edge[top].w1 = w1; edge[top].w2 = w2; edge[top].nxt = head[u]; head[u] = top; } bool vis[MAXN]; double dis[MAXN]; queue<int>q; bool spfa(int s, int n, double val) { memset(vis, 0, sizeof(vis)); for(int i = 0; i < MAXN; ++i) dis[i] = 0; while(!q.empty()) q.pop(); q.push(s); vis[s] = 1; dis[s] = val; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].v; double w1 = edge[i].w1; double w2 = edge[i].w2; if(dis[u] < w2) continue; if(dis[v] < (dis[u] - w2)*w1) { dis[v] = (dis[u] - w2) * w1; if(dis[s] > val) return 1; if(!vis[v]) { vis[v] = 1; q.push(v); } } } } return 0; } int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku int n, m, s; double v; while(~scanf("%d%d%d%lf", &n, &m, &s, &v)) { if(n == 0) break; init(); for(int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); double w1, w2; scanf("%lf%lf", &w1, &w2); add_edge(u, v, w1, w2); scanf("%lf%lf", &w1, &w2); add_edge(v, u, w1, w2); } if(spfa(s, n, v)) puts("YES"); else puts("NO"); } }
判断存在负环,则直接返回YES,因为反正会越滚越大的,终有一天是可以的。上面的代码为什么不会T我也不知道,可能是指数增长的确很快,最后很快就凑够手续费回去了。
#include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<map> #include<set> #include<stack> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int MAXN = 105; const int MAXM = 1005; int top; int head[MAXN]; struct Edge { int v, nxt; double w1, w2; } edge[MAXM]; void init() { top = 0; memset(head, -1, sizeof(head)); } void add_edge(int u, int v, double w1, double w2) { ++top; edge[top].v = v; edge[top].w1 = w1; edge[top].w2 = w2; edge[top].nxt = head[u]; head[u] = top; } bool vis[MAXN]; int cnt[MAXN]; double dis[MAXN]; queue<int>q; bool spfa(int s, int n, double val) { memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); for(int i = 0; i < MAXN; ++i) dis[i] = 0; while(!q.empty()) q.pop(); q.push(s); vis[s] = 1; cnt[s] = 1; dis[s] = val; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].v; double w1 = edge[i].w1; double w2 = edge[i].w2; if(dis[v] < (dis[u] - w2)*w1) { dis[v] = (dis[u] - w2) * w1; if(!vis[v]) { vis[v] = 1; if(++cnt[v] <= n) q.push(v); else return 1; } } } if(dis[s] > val) return 1; } return dis[s] > val; } int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku int n, m, s; double v; while(~scanf("%d%d%d%lf", &n, &m, &s, &v)) { if(n == 0) break; init(); for(int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); double w1, w2; scanf("%lf%lf", &w1, &w2); add_edge(u, v, w1, w2); scanf("%lf%lf", &w1, &w2); add_edge(v, u, w1, w2); } if(spfa(s, n, v)) puts("YES"); else puts("NO"); } }