POJ 2240 Arbitrage——spfa判正环||flody

POJ 2240 Arbitrage——spfa判正环||flody

spfa：判正环只要遍历每一个点判断松弛次数是否大于n次即可，注意此时求得是最长路，dis数组清零，dis[s]设为1；

flody：先把dis数组设0，主对角线设1， 然后跑一边flody，最后查看主对角线元素是否有大于1的就可以

spfa：

#include #include #include #include #include #include #include #include

G[maxn];map m;bool spfa(int s) { for (int i = 1; i <= n; i++) dis[i] = 0, vis[i] = false, num[i] = 0; dis[s] = 1, vis[s] = true, num[s] = 1; queue q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].first; double val = G[u][i].second; if (dis[v] < dis[u] * val) { dis[v] = dis[u] * val; if (!vis[v]) { vis[v] = true, num[v]++; q.push(v); if (num[v] > n) return true; } } } } return false;}int main() { while (~scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) G[i].clear(); m.clear(); int cnt = 0; for (int i = 1; i <= n; i++) { cin >> s1; if (!m[s1]) m[s1] = ++cnt; } int t; scanf("%d", &t); while (t--) { cin >> s1 >> temp >> s2; int u = m[s1], v = m[s2]; G[u].push_back(make_pair(v, temp)); //G[v].push_back(make_pair(u, 1.0 / temp)); } bool ok = false; for (int i = 1; i <= n; i++) { if (spfa(i)) { ok = true; break; } } printf("Case %d: %s\n", ++flag, ok ? "Yes" : "No"); } return 0;}

flody：

#include #include #include #include #include #include #include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。