本文共 3813 字，大约阅读时间需要 12 分钟。
/**题目大意：* 有n种货币，而且每两种之间有汇率，如果a->b,b->c,c->a,然后他们之间的* 所有汇率乘积大于1，那么就是一种获得利润的手段，题目要求输出yes.*解题思路：* 其实画图就知道，题目要的就是找到存在一个圈，并且这个圈所有权值的乘积* 是正的，如果把最长路的关系条件由加法改为乘法，那么就是说找一个所有乘* 积为的环。dij,floyd可以办到吗？显然不行，他们都处理不了带环的。这个时候* spfa跟Bellman_ford就可以发挥无可比拟的优势了，不过囧了，这道题居然spfa* 比优化了的Bellman_ford慢了那么多，Bellman_ford 47ms,spfa要219ms*解题感想：* 记住想想咯，spfa的话，一个点入队n次，就马上判断有不可收敛的环了，入队n* 次，代表了人家松弛了n-1次。*/
Bellman_ford:
#include #include #include #include #include #include using namespace std;const int MAXN = 35;const int MAXE = 100005;const double inf = 0x3f3f3f3f;typedef struct _node{ int u, v; double w; int next;}N;map index;N edge[MAXE];int head[MAXN], cntEdge;void init(int n){ index.clear(); cntEdge = 0; for(int i = 0; i <= n; i++) { head[i] = -1; }}void addEdge(int u, int v, double w){ edge[cntEdge].u = u; edge[cntEdge].v = v; edge[cntEdge].w = w; edge[cntEdge].next = head[u]; head[u] = cntEdge++;}bool Bellman_ford(int s, int n){ double dis[MAXN]; for(int i = 0; i < n; i++) { dis[i] = -inf; } dis[s] = 1; for(int i = 0; i < n-1; i++) { bool flag = false; for(int j = 0; j < cntEdge; j++) { int u = edge[j].u, v = edge[j].v; double w = edge[j].w; if(dis[v] < dis[u] * w) { dis[v] = dis[u] * w; flag = true; } } if(!flag) break; } for(int f = 0; f < cntEdge; f++) { int u = edge[f].u, v = edge[f].v; double w = edge[f].w; if(dis[v] < dis[u] * w) return true;//有可以增值的环 } return false;}int main(void){#ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin);#endif int n, m, cas_c = 1; while(scanf("%d", &n), n) { init(n); int cnt = 0; char name[1024], name1[1024]; for(int i = 0; i < n; i++) { scanf("%s", name); if(!index.count(name)) index[name] = cnt++; } scanf("%d", &m); double w; for(int i = 0; i < m; i++) { scanf("%s %lf %s", &name, &w, &name1); addEdge(index[name], index[name1], w); } //正图 bool sol = Bellman_ford(0, n); if(sol) printf("Case %d: Yes\n", cas_c++); else printf("Case %d: No\n", cas_c++); } return 0;}
spfa:
#include #include #include #include #include #include #include #include using namespace std;const int MAXN = 35;const int MAXE = 100005;const double inf = 0x3f3f3f3f;typedef struct _node{ int u, v; double w; int next;}N;map index;N edge[MAXE];int head[MAXN], cntEdge;void init(int n){ index.clear(); cntEdge = 0; for(int i = 0; i <= n; i++) { head[i] = -1; }}void addEdge(int u, int v, double w){ edge[cntEdge].u = u; edge[cntEdge].v = v; edge[cntEdge].w = w; edge[cntEdge].next = head[u]; head[u] = cntEdge++;}bool spfa(int s, int n){ int inQ[MAXN] = { 0}, in[MAXN] = { 0}; double dis[MAXN]; for(int i = 0; i < n; i++) dis[i] = -inf; dis[s] = 1; queue Q; Q.push(s); inQ[s] = 1; in[s]++; while(!Q.empty()) { int pre = Q.front(); Q.pop(); inQ[pre] = 0; for(int f = head[pre]; f != -1; f = edge[f].next) { int v = edge[f].v; double w = edge[f].w; if(dis[v] < dis[pre] * w) { dis[v] = dis[pre] * w; if(!inQ[v]) { inQ[v] = 1; Q.push(v); in[v]++; if(in[v] > n) return true; } } } } return false;}int main(void){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif int n, m, cas_c = 1; while(scanf("%d", &n), n) { init(n); int cnt = 0; char name[1024], name1[1024]; for(int i = 0; i < n; i++) { scanf("%s", name); if(!index.count(name)) index[name] = cnt++; } scanf("%d", &m); double w; for(int i = 0; i < m; i++) { scanf("%s %lf %s", &name, &w, &name1); addEdge(index[name], index[name1], w); } //正图 bool sol = spfa(0, n); if(sol) printf("Case %d: Yes\n", cas_c++); else printf("Case %d: No\n", cas_c++); } return 0;}
转载于:https://www.cnblogs.com/cchun/archive/2012/09/02/2667594.html
View Code