hihoCoer 1098 : 最小生成树二·Kruscal算法（并查集）

比眉伴天荒 2024-02-17 21:36 16阅读 0赞

#### \#1098 : 最小生成树二·Kruscal算法 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

##### 描述 #####

随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。

所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。

##### 输入 #####

每个测试点（输入文件）有且仅有一组测试数据。

在一组测试数据中：

第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。

接下来的M行，每行描述一条路线，其中第i行为3个整数N1\_i, N2\_i, V\_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。

对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1\_i, N2\_i<=N, N1\_i≠N2\_i, 1<=V\_i<=10^3.

对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。

##### 输出 #####

对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。

样例输入

5 29
    1 2 674
    2 3 249
    3 4 672
    4 5 933
    1 2 788
    3 4 147
    2 4 504
    3 4 38
    1 3 65
    3 5 6
    1 5 865
    1 3 590
    1 4 682
    2 4 227
    2 4 636
    1 4 312
    1 3 143
    2 5 158
    2 3 516
    3 5 102
    1 5 605
    1 4 99
    4 5 224
    2 4 198
    3 5 894
    1 5 845
    3 4 7
    2 4 14
    1 4 185

样例输出

分析：Kruskal 模板题，并查集的运用。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1e6+10;
    int u[maxn],v[maxn],w[maxn];
    int r[maxn];
    int pre[maxn];
    int N,M;
    int ans;
    
    bool cmp(int i,int j){
    	return w[i]<w[j];
    }
    
    int find(int x){
    	int t=x;
        while(t!=pre[t]){
        	t=pre[t];
    	}
    	
    	int j=x;
    	while(j!=t){
    		pre[j]=t;
    		j=pre[j];
    	}
    	return t;
    }
    
    void Kruskal(){
      	sort(r,r+M,cmp);
      	for(int i=1;i<=N;i++)
      	pre[i]=i;
      	
      	for(int i=0;i<M;i++){
      	  int fx=find(u[r[i]]),fy=find(v[r[i]]);
      	  
      	  if(fx!=fy){
      	  	pre[fx]=fy;
      	  	ans+=w[r[i]];
    		}
    	  }
    }
    
    int main(){
    	while(scanf("%d%d",&N,&M)==2){
    		for(int i=0;i<M;i++)
    		scanf("%d%d%d",&u[i],&v[i],&w[i]);
    		
    		for(int i=0;i<M;i++)
    		r[i]=i;
    		
    		ans=0;
    		Kruskal();
    		printf("%d\n",ans);
    	} 
    	return 0;
    }