HDU 1217 SPFA算最小生成树

本文主要是介绍HDU 1217 SPFA算最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

你敢信？第一份AC 第二分TE!

一个31*31的循环居然TE!

好吧吃一堑长一智喽！

题目本身还是很好的；

这是一个带负权边的最小生成树

学了一下SPFA算法

#include <bits/stdc++.h>
using namespace std;
map<string, int>transfer;
const int MAX_N = 31;
double cost[MAX_N][MAX_N];
double d[MAX_N];
int n, m;
bool SPFA(int ans)
{queue<int >q;bool inq[MAX_N];memset(inq, 0, sizeof(inq));memset(d, 0, sizeof(d));while (!q.empty())	q.pop();d[ans] = 1;inq[ans] = 1;q.push(ans);while (!q.empty()){int x = q.front();q.pop();inq[x] = false;for (int i = 0; i < n; i++)if (d[i] < d[x] * cost[x][i]){d[i] = d[x] * cost[x][i];if (d[ans] > 1.0)return 1;if (!inq[i]){inq[i] = true;q.push(i);}}}return 0;
}
int main(int argc, char const *argv[])
{std::ios::sync_with_stdio(false);int kase = 0;string s1, s2, str;double change;while (cin >> n && n){transfer.clear();memset(cost, 0, sizeof(cost));for (int i = 0; i < n; i++){cin >> str;transfer[str] = i;cost[i][i] = 1;}cin >> m;for (int i = 0; i < m; i++){cin >> s1 >> change >> s2;cost[transfer[s1]][transfer[s2]] = change;}int ans = 0;while (SPFA(ans) && ans < n) ans++;cout << "Case " << ++kase << ": " << (ans == n ? "Yes" : "No") << endl;}return 0;
}

题目不难理解，此处用map很方便；

有超过1的就可以了

这篇关于HDU 1217 SPFA算最小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---