hdoj 1863 畅通工程【最小生成树，kruskal&&prim】

水深无声 2022-08-04 12:45 156阅读 0赞

# 畅通工程 #

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 21867    Accepted Submission(s): 9466**

略

Sample Input

3 3
    1 2 1
    1 3 2
    2 3 4
    1 3
    2 3 2
    0 100

Sample Output

3
    ?

最小生成树模板题：

kruskal版的最小生成树主要思想是：将所有的边按权（即本题中的两城市的距离）从小到大排序，然后从最小的一个开始查看，（这里用的是并查集的内容），

①若当前最小边连接的两个结点不在一颗树上，则将任意一方合并到另一方上面，然后把这条边的长度累加到总长度上，然后接着查看下一条边，

②若当前最小边连接的两个结点在一棵树上，则放弃这条边，继续查看下一条边，

重复上述步骤，知道查看完所有的边；

已Accept代码【c++提交】

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int per[1010];
    void init(int n){
        for(int i=1;i<=n;i++)
            per[i]=i;
    }
    
    struct node{
        int s,c,l;
    }a[10050];
    
    int cmp(node k,node g){
        return k.l<g.l;
    }
    						//--------------------
    int find(int x){		//			    *
        int r=x;			//			   ***
        while(r!=per[r])	//			  * * *
            r=per[r];		//				*
        return r;			//				*
    }						//				*
    						//				*
    bool join(int x,int y){	//			  并查集 
        int fx=find(x);		//				*
        int fy=find(y);		//				*
        if(fx!=fy){			//				*
            per[fx]=fy;		//				*
            return true;	//			  * * *
        }					//			   ***
        return false;		//				*
    }						//--------------------
    
    int main(){
        int n,m,i,j;
        while(scanf("%d",&n),n){
            scanf("%d",&m);
            init(m);
            for(i=0;i<n;i++)
                scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].l);
            sort(a,a+n,cmp);					//从小到大排序 
            int total=0,sum=0;
            for(i=0;i<n;i++){					//从最小的开始查看 
                if(join(a[i].s,a[i].c)){		//判断是否在一颗树上，若不在着则相连，若在，则放弃 
                    total++;					//记录已连接的结点的个数 
                    sum+=a[i].l;				//记录总长度 
                }
                if(total==m-1)					//判断是否所有结点都连在一起， 
                    break;
            }
            if(total==m-1)
                printf("%d\n",sum);
            else
                printf("?\n");
        }
        return 0;
    }

prim版的最小生成树主要思想是：从所有结点中任意选一个（一般都选编号最小的，加入集合A（即把vis集合中对应的点标记为 "1" ）），【haha】然后查看与之连接的 边的长度，把边的长度记录在数组dis中（dis\[i\]中的序号   对应    边的   另一头   结点    的   编号），选最短的然后连接，累加所连接的边的长度，然后把边另一头的结点 加入集合A（即把这个结点与最开始时的结点相连在一棵树上，为了好描述，这里把新加入集合A的结点统一称为K），然后查看与K相连的边的长度，记录这下变得长度，然后回到【haha】，直到所有结点都加入集合A为止；

【空格为停顿】

【注意1：输入时，要判断是否重边，若重边，取短的】

【注意2：要定义一个数组标记结点是否被查看过，使用前初始化为 零 】

【注意3：dis数组使用前要初始化为无穷大，笔者一般都初始化为INF   (\#define INF 0x3f3f3f3f)】

已Accept代码【c提交】

#include<stdio.h>
    #include<string.h>
    #define INF 0x3f3f3f3f
    int n,m;
    int v[101],dis[101];
    int map[101][101];
    
    void prim(){
    	int i,j,min,pos,total=0;
    	memset(v,0,sizeof(v));
    	v[1]=1,pos=1;			//选 "1" 为初始结点 
    	for(i=1;i<=m;i++)
    		dis[i]=map[1][i];	//记录与"1"线连接的边的长度 
    	for(i=1;i<m;i++){		//【haha】 
    		min=INF;
    		for(j=1;j<=m;j++)
    			if(!v[j]&&min>dis[j]){	//比较边的长度 ，记录最短的 
    				min=dis[j];
    				pos=j;
    			}
    		total+=min;			//累加边的长度 
    		v[pos]=1;			//标记为集合A的元素 
    		for(j=1;j<=m;j++)	//查看新加入点周围的边 
    			if(!v[j]&&dis[j]>map[pos][j])
    				dis[j]=map[pos][j];		//更新到这些点的距离 
    	}
    	if(total>=INF)
    		printf("?\n");
    	else
    		printf("%d\n",total);
    }
    int main(){
    	int i,j;
    	while(scanf("%d%d",&n,&m)!=EOF){
    		if(n==0) break;
    		memset(map,INF,sizeof(map));
    		for(i=1;i<=m;i++)
    			map[i][i]=0;
    		int a,b,c;
    		for(i=1;i<=n;i++){
    			scanf("%d%d%d",&a,&b,&c);
    			if(c<map[a][b])			//判断是否重边，若重边则保留短的 
    				map[a][b]=map[b][a]=c;
    		}
    		prim();
    	}
    	return 0;
    }