算法训练营第七十天
最小生成树之prim
题目链接：https://kamacoder.com/problempage.php?pid=1053
- 随意将一个节点放入set作为初始状态。每次从和set中节点相连的权值最小的边相连的节点放入并记录权值。直到set大小和节点数相同。
代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap;// 记录文件依赖关系 vector<int> result; // 记录结果while (m--) {// s->t，先有s才能有tcin >> s >> t;inDegree[t]++; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件} queue<int> que;for (int i = 0; i < n; i++) {// 入度为0的文件，可以作为开头，先加入队列if (inDegree[i] == 0) que.push(i); //cout << inDegree[i] << endl;}// int count = 0;while (que.size()) {int cur = que.front(); // 当前选中的文件 que.pop();//count++;result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件 if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];} else cout << -1 << endl;}
最小生成树之Kruskal
题目链接：https://kamacoder.com/problempage.php?pid=1191
- 用到了并查集，每次对两个节点不连通的情况进行处理，记录最小权值的边。之后对两个节点使用并查集中的join，直到没有不连通的节点
代码如下：
#include <iostream>
#include <vector>using namespace std;int father[10001];void init() {for (int i = 0; i <= 10000; i++) father[i] = i;
}int find(int a) {while (father[a] != a) {a = father[a];}return a;
}bool isSame(int a, int b) {a = find(a);b = find(b);return a == b;
}void join(int a, int b) {if (isSame(a, b)) return;father[find(a)] = b;return;
}int main() {int v, e;cin >> v >> e;vector<vector<int>> edges(e, vector<int>(3, 0));for (int i = 0; i < e; i++) {for (int j = 0; j < 3; j++) {cin >> edges[i][j];}}int dis = 0;init();bool flag = true;while (flag) {flag = false;int min = 10000;int minIndex = -1;for (int i = 0; i < e; i++) {if (isSame(edges[i][0], edges[i][1])) continue;flag = true;if (min > edges[i][2]) {min = edges[i][2];minIndex = i;}}if (flag == true) {dis += min;join(edges[minIndex][0], edges[minIndex][1]);}}cout << dis << endl;
}
软件构建
- 这题之前一次笔试写过，当时最后一个元素后也加了空格，导致只过了30%，大家注意下
代码如下：
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;int main() {int n, m;cin >> n >> m;queue<long int> my_resque;queue<long int> my_midque;map<long int, set<long int>> mymap;map<long int, long int> nummap;set<long int> res;int flag = 0;for (int i = 0; i < n; i++) nummap[i] = 0;for (int i = 0; i < m; i++) {long int a, b;cin >> a >> b;mymap[b].insert(a);nummap[b]=mymap[b].size();}while (res.size() < n) {int num = res.size();for (int i = 0; i < n; i++) {if (res.find(i) == res.end() && nummap[i] == 0) {my_midque.push(i);res.insert(i);my_resque.push(i);}}if (num == res.size() && num != n) break;while (!my_midque.empty()) {long int t = my_midque.front();my_midque.pop();for (int i = 0; i < n; i++) {if (res.find(i) == res.end() &&nummap[i] > 0 && mymap[i].find(t) != mymap[i].end())nummap[i]--;}}}if (res.size() < n) cout << -1 << endl;else {while (!my_resque.empty()) {if (my_resque.size() > 1)cout << my_resque.front() << ' ';else cout << my_resque.front();my_resque.pop();}cout << endl;}return 0;
}
)
