POJ2485 贪心算法求最小生成树——prim算法与kruskal算法
题目分析
http://poj.org/problem?id=2485
本题输入为邻接矩阵，任意两点均直接相连，典型的求最小生成树问题。
prim算法
从源点开始，每次从所有可选边（起点在当前生成树中但是终点不在）中选取权值最小加入当前的生成树中，直到边数为n-1为止。如边数不足n-1但是已经无法选取权值最小边，那么不存在最小生成树。（执行n-1次选取操作，中途选取不了就不存在最小生成树）
用一个数组记录每个点是否在当前最小生成树中，一个数组来记录当前最小生成树距离所有点的最短边长度（初始化为根距离其他所有点的最短边长度，用每次新加入的点距离所有点的短边长度来更新这个最短边数组），用邻接表或邻接矩阵存储图均可，这里使用邻接矩阵。
#include<stdio.h>
#include<string.h>
using namespace std;const int INF=0x3f3f3f;
const int MAXN=505;bool vis[MAXN];
int lowc[MAXN];int prim(int mat[][MAXN],int n){int max = 0;memset(vis,false,sizeof(vis));memset(lowc,INF,sizeof(lowc));//initializevis[0] = true;for(int i = 0;i < n;i++){lowc[i] = mat[0][i];}//n-1 loopsfor(int i = 1;i < n;i++){int p = -1;//added dotint min = INF;for(int j = 0;j < n;j++){if(!vis[j]&&min>lowc[j]){min = lowc[j];p = j;}}if(p == -1) return -1;if(min > max) max = min;vis[p] = true;//update lowc[]for(int j = 0;j < n;j++){if(lowc[j]>mat[p][j])lowc[j] = mat[p][j];}}return max;
}
int main(){int T;scanf("%d",&T);while(--T!=-1){int N;scanf("%d",&N);int mat[MAXN][MAXN];for(int i = 0;i < N;i++){for(int j = 0; j < N;j++){scanf("%d",&mat[i][j]);}}printf("%d\n",prim(mat,N));}return 0;
}1304K 172MS
kruskal算法
对所有的边按权值进行排序操作，从小到大遍历每一条边，假如该边连接的两个点不在同一个连通分量中，就这条边加入最小生成树。假如所有边遍历完成后，所有的点不在同一个连通分量中，那么不存在最小生成树；假如所有点在一个连通分量中，则找到了最小生成树。
kruskal算法用到一个并查集。思想：https://blog.csdn.net/qq_41754350/article/details/81271567，https://blog.csdn.net/zjy_code/article/details/80634149
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;const int INF=0x3f3f3f;
const int MAXN=505;int f[MAXN];//并查集
int fcnt = 0;//不同的连通分量数量void UFinit(int n){//初始化并查集中有n个不相关元素for(int i = 0;i < n;i++){f[i] = i;}fcnt = n;
}int find(int a){//寻找a所在集合的代表元素return a==f[a]?f[a]:find(f[a]);
}bool Union(int a,int b){//合并a与b所在集合if(find(a)!=find(b)){f[find(a)] = find(b);fcnt--;return true;}else return false;
}struct Edge{int cost,u,v;Edge(int cost_,int u_,int v_){cost = cost_;u = u_;v = v_;}
};vector<Edge> e;bool cmp(Edge x,Edge y){return x.cost < y.cost;
}int kruskal(int n){sort(e.begin(),e.end(),cmp);int max = 0;UFinit(n);for(int i = 0;i < e.size();i++){if(Union(e[i].u,e[i].v)){if(max<e[i].cost) max = e[i].cost;}}if(fcnt == 1) return max;else return -1;
}int main(){int T;scanf("%d",&T);while(--T!=-1){int N;scanf("%d",&N);int mat[MAXN][MAXN];for(int i = 0;i < N;i++){for(int j = 0; j < N;j++){scanf("%d",&mat[i][j]);}}for(int i = 0;i < N;i++){for(int j = 0;j <= i;j++){e.push_back(Edge(mat[i][j],i,j));}}
// for(int i = 0; i < e.size();i++)
// printf("%d %d",e[i].u,e[i].v);printf("%d\n",kruskal(N));e.clear();}return 0;
}2092K 219MS