# CCF 201412-4 最优灌溉(最小生成树,prime算法，kurskal算法)

xiaoxiao2021-02-28  25

#include<algorithm> #include<cstdio> #include<bits\stdc++.h> using namespace std; const int N = 1005; const int INF = 1e6; int vis[N], g[N][N], n, m, x, y, z,index, total = 0,cost[N]; void prime() { //初始化 vis[1] = 1; for (int i = 1; i <= n; i++) { cost[i] = g[1][i]; } //开始搜索 for (int i = 1; i < n; i++) { int mincost = INF; //找到此点出发最短的边 for (int j = 1; j <= n; j++) { if (!vis[j] && cost[j] < mincost) { mincost = cost[j]; index = j; } } vis[index] = 1; total += mincost; //更新周围点的最小cost for (int j = 1; j <= n; j++) { if (!vis[j] && cost[j] > g[index][j]) { cost[j] = g[index][j]; } } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { g[i][j] = INF; } } while (m--) { cin >> x >> y >> z; g[x][y] = z; g[y][x] = z; } prime(); cout << total; }

2.kruskal算法

#include<algorithm> #include<cstdio> #include<bits\stdc++.h> using namespace std; const int N = 1005; struct edge { int u, v, cost; bool operator < (const edge& n) const { return cost > n.cost; } }; priority_queue<edge> q; //使用并查集判断当前图是否联通 int id[N], n, m, total = 0; class UF { public: void build() { for (int i = 1; i <= n; i++) { id[i] = i; } } int find(int x) { if (id[x] == x) { return x; } else return find(id[x]); } void connect(int x, int y) { x = find(x); y = find(y); if (x == y) return; else{ id[x] = y; return; } } }; bool cmp(edge x, edge y) { return x.cost<y.cost; } void kruskal() { UF uf; uf.build(); while(!q.empty()) { edge e = q.top(); q.pop(); if (uf.find(e.u) != uf.find(e.v)) { uf.connect(e.u, e.v); total += e.cost; } } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { edge e; cin >> e.u >> e.v >> e.cost; q.push(e); } kruskal(); cout << total; return 0; }