53. 寻宝（第七期模拟笔试）

prim

#include <iostream>
#include <vector>
#include <climits>using namespace std;int main() {int v, e;cin >> v >> e;int v1, v2 , val;vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));for (int i = 1; i <= e; i++) {cin >> v1 >> v2 >> val;grid[v1][v2] = val;grid[v2][v1] = val; //无向图}vector<int> visit(v + 1, 0);vector<int> minDist(v + 1, 10001);for (int i = 1; i < v; i++) {int cur = -1;int minD = INT_MAX;for (int j = 1; j <= v; j++) {if (!visit[j] && minDist[j] < minD) {minD = minDist[j];cur = j;}}visit[cur] = 1;for (int j = 1; j <= v; j++) {if (!visit[j] && grid[cur][j] < minDist[j] ) {minDist[j] = grid[cur][j];}}}int result = 0;for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边result += minDist[i];}cout << result;return 0;
}

2.kruscal

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;
struct Edge {int v1, v2;int val;
};
vector<int> father(10001, 0);
void init() {for (int i = 0; i < father.size(); i++)father[i] = i;
}int find(int x) {if (x == father[x]) return father[x];return find(father[x]);
}void join(int x, int y) {int fx = find(x);int fy = find(y);if (fx == fy) return;else {father[fx] = fy;return;}
}bool isSame(int x, int y) {int fx = find(x);int fy = find(y);if (fx == fy) return true;else {return false;}
}int main() {int v, e;cin >> v >> e;int v1, v2 , val;vector<Edge> edges(e + 1);for (int i = 1; i <= e; i++) {cin >> v1 >> v2 >> val;edges[i].v1 = v1;edges[i].v2 = v2;edges[i].val = val;}sort(edges.begin(), edges.end(), [&](Edge e1, Edge e2){return e1.val < e2.val;});init();int result = 0;for (Edge &edge: edges) {if (!isSame(edge.v1, edge.v2)) {join(edge.v1, edge.v2);result += edge.val;}}cout << result;return 0;
}

117. 软件构建

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>using namespace std;int main() {int n, m;cin >> n >> m;unordered_map<int, vector<int>> mp;vector<int> indegree(n, 0);int s, t;for (int i = 0; i < m; i++) {cin >> s >> t;mp[s].push_back(t);indegree[t]++;}vector<int> result;queue<int> que;for (int i = 0; i < n; i++) {if (indegree[i] == 0){que.push(i);result.push_back(i);}}while(!que.empty()) {int cur = que.front(); que.pop();;vector<int>& curv = mp[cur];for (int i = 0; i < curv.size(); i++) {indegree[curv[i]]--;if (indegree[curv[i]] == 0) {que.push(curv[i]);result.push_back(curv[i]);}}}if (result.size() != n){cout << -1;} else {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];}return 0;
}

47. 参加科学大会（第六期模拟笔试）

Dijkstra

#include <iostream>
#include <vector>
#include <climits>using namespace std;int main() {int n, m;cin >> n >> m;int s, e, v;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for (int i = 0; i < m; i++) {cin >> s >> e >> v;grid[s][e] = v;}int start = 1, end = n;vector<int> visited(n + 1, 0);vector<int> minDist(n + 1, INT_MAX);minDist[start] = 0;for (int i = 1; i <= n; i++) {int cur = 1;int Dist = INT_MAX;for (int j = 1; j <= n; j++) {if (!visited[j] && minDist[j] < Dist) {Dist = minDist[j];cur  = j;}}visited[cur] = 1;for (int j = 1; j <= n; j++) {if (!visited[j] && grid[cur][j] != INT_MAX && minDist[j] > grid[cur][j] + minDist[cur])  //grid[cur][j] != INT_MAX  反溢出minDist[j] = grid[cur][j] + minDist[cur];}}if (minDist[end] == INT_MAX) cout << -1;else {cout << minDist[end];} return 0;
}