当前位置: 代码迷 >> 综合 >> 最小生成树 hdoj1233 nyoj38
  详细解决方案

最小生成树 hdoj1233 nyoj38

热度:94   发布时间:2024-01-18 23:40:09.0

Minimum Spanning Tree 

prim用于稠密图,kruscal用于稀疏图

1.Prim算法

Prim算法是不断增加顶点的算法

选定任意一个点为起始点,用一个lowcost[i]数组来维护已经生成的树到顶点i的距离

每次从lowcost[i]中选取最小的点连接,并且用这个点来更新lowcost(因为以这个点为起点到到某些点可能更短)

核心数据结构:

isadded[i]:表示点i是否加入

lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST


prim算法本质上和Dijkstra算法是一回事。

最小生成树每次需要获得locost数组中的最小值,之后需要更新其他locost,像Dijkstrea一样,这个过程也可以用一个堆来实现,可以把复杂度降低到VlogV


hdoj1863 浙大考研复试

<span style="font-size:18px;">#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=120;
const int INF=0xffffff;
bool used[maxn];
int dis[maxn][maxn];
int lowcost[maxn];
int N,M;
int prim(){used[1]=true;int weight=0;for(int i=1;i<=M;i++){if(dis[1][i]<lowcost[i])lowcost[i]=dis[1][i];}for(int j=1;j<M;j++){int MIN=INF;int next=-1;for(int i=1;i<=M;i++){if(!used[i] && lowcost[i]<MIN){MIN=lowcost[i];next=i;}}if(next==-1) return -1;weight+=MIN;used[next]=true;for(int i=1;i<=M;i++){if(!used[i]&&dis[next][i]<lowcost[i])lowcost[i]=dis[next][i];}}return weight;
}
int main(int argc, char const *argv[])
{while(scanf("%d%d",&N,&M),N!=0){memset(used,false,sizeof(used));for(int i=1;i<=M;i++){lowcost[i]=INF;for(int j=1;j<=M;j++){if(i==j) dis[i][j]=0;else dis[i][j]=INF;}}int a,b,c;for(int i=0;i<N;i++){scanf("%d%d%d",&a,&b,&c);dis[a][b]=dis[b][a]=c;}int ans=prim();if(ans==-1) printf("?\n");else printf("%d\n",ans);}/* code */return 0;
}</span>




hdoj1233
<span style="font-size:18px;">#include <iostream>
using namespace std;
const int maxn=1010;
const int INF=0x999999;
int lowcost[maxn];
bool isadd[maxn];
int edge[maxn];
int VNUM;
int prim(int start){for(int i=1;i<=VNUM;i++){isadd[i]=false;lowcost[i]=edge[start][i];}isadd[start]=true;for(int i=1;i<VNUM;i++){//n-1条边int next=-1;int min=INF;for(int j=1;j<=VNUM;j++){if(!isadd[j]&&lowcost[j]<min){min=lowcost[j];next=j}}if(next==-1) return INF;isadd[next]=true;weight+=min;for(int j=1;j<=VNUM;j++){if(!isadd[j]&&lowcost[j]>edge[next][j]){lowcost[j]=edge[next][j];}}	}return weight;
}</span>
邻接矩阵 O(V^2)


nyoj 38

修电线,和建路是一样的。多了一个从该位置向外的花销,但是其实从某个位置向外联通都是可以的,所以取其中最小的就可以了

prim做法

<span style="font-size:18px;">#include <iostream>
#include <cstdio>
const int INF=0xffffff;
using namespace std;
const int maxn=505;
int matrix[maxn][maxn];
bool isadd[maxn];
int lowcost[maxn];
int V,E;
int prim(int start){int weight=0;for(int i=1;i<=V;i++) isadd[i]=false;isadd[start]=true;for(int i=1;i<=V;i++){lowcost[i]=matrix[start][i];}for(int i=1;i<V;i++){int next=-1;int minnext=INF;for(int j=1;j<=V;j++){if(!isadd[j]&&lowcost[j]<minnext){minnext=lowcost[j];next=j;}}weight+=minnext;isadd[next]=true;for(int j=1;j<=V;j++){if(!isadd[j]&&lowcost[j]>matrix[next][j]){lowcost[j]=matrix[next][j];}}}return weight;
}
int main(int argc, char const *argv[])
{int tcase;cin>>tcase;while(tcase--){cin>>V>>E;int a,b,c;for(int i=1;i<=V;i++){for(int j=1;j<=V;j++){if(i==j) matrix[i][j]=0;else matrix[i][j]=INF;}}for(int i=0;i<E;i++){scanf("%d%d%d",&a,&b,&c);matrix[a][b]=matrix[b][a]=c;}int minoutcost=INF,outcost;for(int i=1;i<=V;i++){scanf("%d",&outcost);if(outcost<minoutcost) minoutcost=outcost;}cout<<prim(1)+minoutcost<<endl;;}return 0;
}</span>
邻接矩阵 O(V^2)


2.Kruskal

实现:把边(每个边要有起点、终点、长度三个因素)根据长度排序。但要注意的是,在prim算法中,我们可以通过lowcost来寻找和已经形成树的最短连接。但是在prim算法中,我们并不能像prim算法一样确定循环的次数(prim共N-1次)。因此,我们需要一个能够判断完全联通的指标,我们需要把边都扫一遍,对于每条边,用并查集检查是否连通,然后再决定是否相连。如果要判断是否形成最小生成树,还需要再扫一遍。

(注意:并查集由于使用了路径压缩,所以记录sz,把小的树连到大的树的作用其实很小)

nyoj48

Kruskal做法

<span style="font-size:18px;">#include <iostream>
using namespace std;
const int maxn=520;
const int INF=0x9999999;
typedef struct{int s,e,cost;
}edge;
edge Edge[maxn*maxn];
int pre[maxn];
int V,E;
int find(int p){int root=p;while(root!=pre[root]){root=pre[root];}while(p!=root){int next=pre[p];pre[p]=root;p=next;}return root;
}
void join(int p,int q){int rootp=find(p);int rootq=find(q);if(rootp==rootq) return ;pre[rootp]=rootq;
}
void exch(int a,int b){edge temp=Edge[a];Edge[a]=Edge[b];Edge[b]=temp;
}
bool smaller(int a,int b){return Edge[a].cost<Edge[b].cost;
}
void swim(int k){while(k/2&&smaller(k,k/2)){exch(k,k/2);k/=2;}
}
// void sink(int k,int n){
// 	while(k*2<=n){
// 		int j=2*k;
// 		if(j+1<=n&&smaller(j+1,j)) j++;
// 		if(smaller(k,j)) break;
// 		exch(k,j);
// 		k=j;
// 	}
// }
bool connect(int p,int q){return find(p)==find(q);
}
int krustra(){int weight=0;int p,q;int num=0;for(int i=1;i<=E;i++){p=Edge[i].s;q=Edge[i].e;if(connect(q,p)) continue;num++;join(p,q);weight+=Edge[i].cost;}return weight;if(num==V-1) cout<<"not connected"<<endl;return 0;
}int main(int argc, char const *argv[])
{int N;cin>>N;while(N--){cin>>V>>E;for(int i=1;i<=E;i++){cin>>Edge[i].s>>Edge[i].e>>Edge[i].cost;swim(i);}int minout=INF;int outcost;for(int i=1;i<=V;i++) {cin>>outcost;pre[i]=i;if(outcost<minout) minout=outcost;}cout<<krustra()+minout<<endl;}return 0;
}</span>






  相关解决方案