Net~~最小生成树

比较简单的题目.

直接附AC的代码：

#include <iostream>#include <cstdio>#include <algorithm>using namespace std;class data{public:int form, to, height;};data Edge[10005];int N, num, par[105];int cmp(const data& a, const data& b) //从小到大排序{return a.height < b.height;}int finds(int x)//并查集查找函数{if(x == par[x])return x;elsereturn par[x] = finds(par[x]);}void join(int x, int y)//并查集合并函数{x = finds(x);y = finds(y);if(x != y)par[y] = x;}int Kruskal()//最小生成树算法Kruskal{int i, ans = 0;for(i = 0; i < 105; i++)par[i] = i;sort(Edge, Edge + num, cmp);for(i = 0; i < num; i++){data e = Edge[i];if(finds(e.form) != finds(e.to)) //判是否属于同一个并查集，，避免形成环{join(e.form, e.to);ans += e.height;}}return ans;}int main(){int i, j, cost;while(scanf("%d", &N) != EOF){num = 0;for(i = 1; i <= N; i++)for(j = 1; j <= N; j++){scanf("%d", &cost);if(i != j){Edge[num].form = i;Edge[num].to = j;Edge[num++].height = cost;}}int ans = Kruskal();printf("%d\n", ans);}return 0;}

眼睛可以近视，目光不能短浅。