题目：有N个路由器，给出M个无向连接方式及其长度，需要将所有点可以连接起来，找到最大的连接长度中最小的。但是输出的时候输出总长度没啥关系，你可以输出很多长度小于最小的最大连接长度的点的关系。
解析：最小生成树算法。
我的代码很垃圾，模仿Prim算法，但是把所有相邻信息升序保存在neighbor中，代码写起来更简单，但是复杂度会变大很多很多。（但是能过就行）
|
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 54 55 |
#include<iostream> #include<set> #include<vector> using namespace std; set<pair<int, pair<int, int>>>neighbors; set<int>node; set<pair<int, pair<int, int>>>result; bool in(int i) { set<int>::iterator ptr = node.find(i); if (ptr != node.end()) return 1; else return 0; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; neighbors.insert(make_pair(c, make_pair(a - 1, b - 1))); } pair<int, int>connection; int cost; bool a, b; node.insert(neighbors.begin()->second.first); while (node.size() != n) { auto ptr = neighbors.begin(); while (1) { cost = ptr->first; connection = ptr->second; a = in(connection.first); b = in(connection.second); if (!a && !b) { ptr++; continue; } if (a && !b) { node.insert(connection.second); result.insert(make_pair(cost, make_pair(connection.first, connection.second))); } if (!a && b) { node.insert(connection.first); result.insert(make_pair(cost, make_pair(connection.first, connection.second))); } ptr = neighbors.erase(ptr); break; } } cout << (--result.end())->first << endl; cout << result.size() << endl; for (auto i : result) cout << i.second.first + 1 << " " << i.second.second + 1 << endl; return 0; } |
浙公网安备 33010902002953号