样题可见SYZOJ
最近发现最小生成树居然属于NOIP考察范围之内，就顺带膜了一发Kruscal。
Kruscal的主要思想就是贪心，这点感觉跟Dijkstra有点像，但是并不用进行堆优化之类的神奇的东西。。
其实挺简单的，比dinic不知道好写到哪里去了。
|
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 56 |
#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; } |