样题可见SYZOJ
最近发现最小生成树居然属于NOIP考察范围之内,就顺带膜了一发Kruscal。
Kruscal的主要思想就是贪心,这点感觉跟Dijkstra有点像,但是并不用进行堆优化之类的神奇的东西。。
其实挺简单的,比dinic不知道好写到哪里去了。
#include <algorithm> #include <iostream> #include <cstdio> using namespace std; const int MX = 305; const int inf = 1000000007; class edge { public: int x, y, v; }e[MX * MX]; int bing[MX], c[MX]; int n, tot; int find_father(int x) { return x == bing[x] ? x : find_father(bing[x]); } bool cmp(edge a, edge b) { return a.v < b.v; } int kruscal() { sort(e + 1, e + tot + 1, cmp); int cnt = tot; int ans = 0; for (int i = 0; i <= n; i++) bing[i] = i; for (int i = 1; i <= tot; i++) { int f1 = find_father(e[i].x); int f2 = find_father(e[i].y); if (f1 != f2) { bing[f1] = f2; ans += e[i].v; cnt--; if (cnt == 1) break; } } return ans; } int main() { cin >> n; for (int i = 1; i <= n; i++) { scanf("%d", &c[i]); e[++tot].x = 0; e[tot].y = i; e[tot].v = c[i]; } int tmp; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &tmp); if (tmp) { e[++tot].x = i; e[tot].y = j; e[tot].v = tmp; } } } cout << kruscal() << endl; }