就是裸的最小生成树，复习一下。
prim算法：
G=(V,E),V是点集，E是边集
假设T=（U，TE）是最小生成树。U，TE初始化为空
首先从V中任取一点 假设取V1，然后U={V1},只要U是V的真子集，就从那些一个端点在T中，一个端点在T外的边中，找一条最短边。一直下去，直到找到n-1条边
找边使用 堆优化，复杂度（ElogV） 邻接表复杂度（V2）
1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 const int maxn=110; 7 const int inf=0x3f3f3f3f; 8 9 struct node{ 10 int v,dis; 11 node(){} 12 node(int _v,int _dis){ 13 v=_v; 14 dis=_dis; 15 } 16 bool operator<(const node &b) const { 17 return dis>b.dis; 18 } 19 }; 20 21 int n,dis[maxn]; 22 vector<node> G[maxn]; 23 bool vis[maxn]; 24 25 void prim() { 26 int ans=0,num=0; 27 priority_queue<node> pq; 28 for(int i=0;i<n;i++) { 29 vis[i]=false; 30 dis[i]=inf; 31 } 32 pq.push(node(0,0)); 33 node f; 34 while(num<n&&!pq.empty()) { 35 do{ 36 f=pq.top(); 37 pq.pop(); 38 }while(vis[f.v]&&!pq.empty()); 39 if(!vis[f.v]) { 40 ans+=f.dis; 41 vis[f.v]=true; 42 num++; 43 for(int i=0;i<G[f.v].size();i++) { 44 int v=G[f.v][i].v; 45 if(!vis[v]) { 46 if(dis[v]>G[f.v][i].dis) { 47 dis[v]=G[f.v][i].dis; 48 pq.push(node(v,dis[v])); 49 } 50 } 51 } 52 } 53 } 54 if(num<n) printf("-1 ");//因为这里记录的是点的个数。不是边 55 else printf("%d ",ans); 56 } 57 58 int main() { 59 while(~scanf("%d",&n)) { 60 memset(G,0,sizeof(G)); 61 for(int i=0;i<n;i++) { 62 for(int j=0;j<n;j++) { 63 int x; 64 scanf("%d",&x); 65 if(x) G[i].push_back(node(j,x)); 66 } 67 } 68 prim(); 69 } 70 }
krusual算法：
将图G中的边按权值从小到大选取，使选取的不与生成树构成回路。直到n-1条边为止
判断回路就用并查集搞一下。
1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int maxn=110; 8 const int inf=0x3f3f3f3f; 9 10 int n; 11 struct Edge{ 12 int u,v,dis; 13 Edge(){} 14 Edge(int _u,int _v,int _dis) { 15 u=_u; 16 v=_v; 17 dis=_dis; 18 } 19 bool operator <(const Edge &b) const { 20 return dis<b.dis; 21 } 22 }; 23 24 vector<Edge> edge; 25 26 int fa[maxn]; 27 28 int Find(int x) { 29 if(fa[x]==-1) return x; 30 else return fa[x]=Find(fa[x]); 31 } 32 33 void Union(int x,int y) { 34 int fx=Find(x); 35 int fy=Find(y); 36 if(fx!=fy) { 37 fa[fx]=fy; 38 } 39 } 40 41 int main() { 42 while(~scanf("%d",&n)) { 43 memset(fa,-1,sizeof(fa)); 44 edge.clear(); 45 for(int i=0;i<n;i++) { 46 for(int j=0;j<n;j++) { 47 int x; 48 scanf("%d",&x); 49 if(x&&j<i) edge.push_back(Edge(i,j,x)); 50 } 51 } 52 sort(edge.begin(),edge.end()); 53 int num=0,ans=0; 54 for(int i=0;i<edge.size();i++) { 55 int u=edge[i].u,v=edge[i].v,dis=edge[i].dis; 56 if(Find(u)!=Find(v)) { 57 num++; 58 ans+=dis; 59 Union(u,v); 60 } 61 } 62 if(num==n-1) printf("%d ",ans); 63 else printf("-1 "); 64 } 65 }