题目:有n个点,接下来输入m行,表示从a点到b点有向边距离为c,求从S(start)起点到F(Final)终点最大路径。
解析:求最大路径问题
1. Bellman-Ford算法
2. 拓扑,利用入度(In-degree)。从入度等于0(只可能有出度)的点开始拓扑,相邻的点入度-1代表还剩in-degree个点还没拓扑到他,如果该点所有可到他的点均已经寻找完,则把该点加入queue,即可以从该点进行下一步拓扑。
错误提示:
1. WA3 Dijskra算法写错
2. TLE16 Dijskra算法因为只要小于就要加入queue,比入度算法复杂度高,不要用Dijskra改版算法,换算法
3. WA9和WA10。小部分神奇原因:输出强制类型转换成int。大部分原因:不要第一个就从开始点开始拓扑(我也不知道为什么,就是错的)。
Bellman-Ford算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<iostream> #include<unordered_map> #include<vector> #include<queue> #define INF 0x3f3f3f3f using namespace std; int n, m, beginPoint, endPoint; struct Point { Point() { distence = INF; done = false; } vector<pair<int, int>> neighbor; long long distence; bool done; }point[500]; void SPFA() { queue<int> q; point[beginPoint - 1].distence = 0; q.push(beginPoint - 1); while (!q.empty()) { int x = q.front(); q.pop(); point[x].done = false; for (auto ptr : point[x].neighbor) { if (point[ptr.first].distence > point[x].distence - ptr.second) { point[ptr.first].distence = point[x].distence - ptr.second; if (!point[ptr.first].done) { point[ptr.first].done = true; q.push(ptr.first); } } } } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; point[a - 1].neighbor.push_back(make_pair(b - 1, c)); } cin >> beginPoint >> endPoint; SPFA(); if (point[endPoint - 1].distence == INF) cout << "No solution" << endl; else cout << -point[endPoint - 1].distence << endl; } |
In-degree
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<unordered_map> #include<vector> #define INF 0x3f3f3f3f using namespace std; int n, m, beginPoint, endPoint; struct Point { Point() { distence = -INF; } unordered_map<Point*, int> neighbor; long long distence; int degree; }point[500]; void extend() { vector<Point*>queue; point[beginPoint - 1].distence = 0; Point* now; unordered_map<Point*, int>::iterator ptr; for (int i = 0; i < n; i++) if (point[i].degree == 0) queue.push_back(&point[i]); while (!queue.empty()) { now = *queue.begin(); queue.erase(queue.begin()); for (ptr = now->neighbor.begin(); ptr != now->neighbor.end(); ptr++) { ptr->first->distence = max(ptr->first->distence, now->distence + ptr->second); ptr->first->degree--; if (ptr->first->degree == 0) queue.push_back(ptr->first); } if (point[endPoint - 1].degree == 0) return; } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; point[a - 1].neighbor.insert({ &point[b - 1], c }); point[b - 1].degree++; } cin >> beginPoint >> endPoint; extend(); if (point[endPoint - 1].distence < 0) cout << "No solution" << endl; else cout << point[endPoint - 1].distence << endl; } |