8.1

8.1

//8.1镖局运镖 kruskal

#include<cstdio>
#include<cstdlib>
struct edge
{int u;int v;int w;
};
struct edge e[10];
int f[7];int comp(const void *_a,const void *_b)
{struct edge* a=(struct edge*)_a;struct edge* b=(struct edge*)_b;return a->w-b->w;
}int getf(int v)
{if(f[v]==v)return v;f[v]=getf(f[v]);return f[v];
}int merge(int v,int u)
{int t1,t2;t1=getf(v);t2=getf(u);if(t1!=t2){f[t2]=t1;return 1;}return 0;
}int main()
{freopen("data.in","r",stdin);int i,n,m,sum=0,count=0;scanf("%d %d",&n,&m);for(i=0;i<m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);qsort(&e[1],m,sizeof(struct edge),comp);for(i=1;i<=m;i++)f[i]=i;for(i=1;i<=m;i++){if(merge(e[i].u,e[i].v)){count++;sum+=e[i].w;}if(count==n-1)break;}printf("%d\n",sum);return 0;
}

//镖局运镖 kruskal+quickSort

#include<cstdio>
#include<cstdlib>
struct edge
{int u;int v;int w;
};
struct edge e[10];
int f[7];void quicksort(int left,int right)
{int i,j;struct edge t;if(left>=right)return;i=left;j=right;while(i!=j){while(e[j].w>=e[left].w&&i<j)j--;while(e[i].w<=e[left].w&&i<j)i++;if(i<j){t=e[i];e[i]=e[j];e[j]=t;}}t=e[left];e[left]=e[i];e[i]=t;quicksort(left,i-1);quicksort(i+1,right);
}int getf(int v)
{if(f[v]==v)return v;f[v]=getf(f[v]);return f[v];
}int merge(int v,int u)
{int t1,t2;t1=getf(v);t2=getf(u);if(t1!=t2){f[t2]=t1;return 1;}return 0;
}int main()
{freopen("data.in","r",stdin);int i,n,m,sum=0,count=0;scanf("%d %d",&n,&m);for(i=0;i<m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);quicksort(1,m);for(i=1;i<=m;i++)f[i]=i;for(i=1;i<=m;i++){if(merge(e[i].u,e[i].v)){count++;sum+=e[i].w;}if(count==n-1)break;}printf("%d\n",sum);return 0;
}

//8.2 prim

#include<cstdio>
int main()
{freopen("data.in","r",stdin);int n,m,i,j,k,min,t1,t2,t3;int e[7][7],dis[7],book[7]={0};int inf=999999;int count=0,sum=0;scanf("%d%d",&n,&m);//初始化for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)e[i][j]=0;else    e[i][j]=inf;for(i=1;i<=m;i++){scanf("%d%d%d",&t1,&t2,&t3);e[t1][t2]=t3;e[t2][t1]=t3;} for(i=1;i<=n;i++)dis[i]=e[1][i];//prim核心部分book[1]=1;count++;while(count<n){min=inf;for(i=1;i<=n;i++)if(book[i]==0&&dis[i]<min){min=dis[i];j=i;}book[j]=1;count++;sum=sum+dis[j];//以j为中间点，更新生成树到每一个非数顶点的距离for(k=1;k<=n;k++){if(book[k]==0&&dis[k]>e[j][k])dis[k]=e[j][k];} } printf("%d",sum);
}

栈优化

#include<cstdio>
int dis[7],book[7]={0}; //距离、顶点已在树中 
int h[7],pos[7],size;   //h保存堆、pos保存每个顶点在堆中的位置、size为堆的大小 
void swap(int x,int y)
{int t;t=h[x];h[x]=h[y];h[y]=t;t=pos[h[x]];pos[h[x]]=pos[h[y]];pos[h[y]]=t;
}
//向下调整
void siftdown(int i)
{int t,flag=0;while(i*2<=size&&flag==0){if(dis[h[i]]>dis[h[i*2]])t=i*2;elset=i;if(i*2+1<=size){if(dis[h[t]]>dis[h[i*2+1]])t=i*2+1;}if(t!=i){swap(t,i);i=t;}elseflag=1;}
} 
//向上调整
void siftup(int i)
{int flag=0;while(i!=1&&flag==0){if(dis[h[i]]<dis[h[i/2]])swap(i,i/2);elseflag=1;i=i/2;}
} 
//从堆顶取出一个元素
int pop()
{int t;t=h[1];pos[t]=0;h[1]=h[size];pos[h[1]]=1;size--;siftdown(1);return t;
}
int main()
{freopen("data.in","r",stdin);int n,m,i,j,k;int u[19],v[19],w[19],first[7],next[19];int inf=999999;int count=0,sum=0;scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&u[i],&v[i],&w[i]);//这里是无向图，所以需要将所有的边再反向存储一次 for(i=m+1;i<=2*m;i++){u[i]=v[i-m];v[i]=u[i-m];w[i]=w[i-m];} //邻接表for(i=1;i<=n;i++)first[i]=-1;for(i=1;i<=2*m;i++){next[i]=first[u[i]];first[u[i]]=i;} //pirm核心book[1]=1;count++;//初始化dis数组 dis[1]=0; for(i=2;i<=n;i++)dis[i]=inf;k=first[1];while(k!=-1){dis[v[k]]=w[k];k=next[k];}//初始化堆size=n;for(i=1;i<=size;i++){h[i]=i;pos[i]=i;} for(i=size/2;i>=1;i--)siftdown(i);pop();//先弹出一个堆顶元素，因为此时堆顶是一号顶点while(count<n){j=pop();book[j]=1;count++;sum=sum+dis[j];//扫描当前顶点j所有边，再以j为中间点进行松弛k=first[j];while(k!=-1){if(book[v[k]]==0&&dis[v[k]]>w[k]){dis[v[k]]=w[k];siftup(pos[v[k]]);}k=next[k];} } printf("%d",sum);return 0;
}