【杭电oj1863】畅通工程

逃离我推掉我的手 2022-09-25 00:29 127阅读 0赞

# 畅通工程 #

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

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N  
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要  
  
输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

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

Sample Output

3
    ?
       
        #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 105;
    int map[N][N];
    int pre[N],n;
    int prim(int n) {
    	int vis[N],dis[N],ans=0;
    	memset(dis,inf,sizeof(dis));
    	memset(vis,0,sizeof(vis));
    	dis[1]=0;
    	for(int l=1; l<=n; l++) {
    		int k,tp=inf;
    		for(int i=1; i<=n; i++) {
    			if(!vis[i]&&dis[i]<tp) {
    				tp=dis[i];
    				k=i;
    			}
    		}
    		ans+=tp,vis[k]=1;
    		for(int j=1; j<=n; j++) {
    			if(!vis[j]&&map[k][j]<dis[j]) {
    				dis[j]=map[k][j];
    			}
    		}
    	}
    	return ans;
    }
    int find(int x) {
    	int r=x;
    	while(r!=pre[r]) {
    		r=pre[r];
    	}
    	int i=x,j;
    	while(i!=r) {
    		j=pre[i];
    		pre[i]=r;
    		i=pre[i];
    	}
    	return r;
    }
    void Union(int x,int y) {
    	int fx,fy;
    	fx=find(x);
    	fy=find(y);
    	if(fx!=fy) {
    		pre[fx]=fy;
    	}
    }
    void init() {
    	for(int l=1; l<=n; l++) {
    		pre[l]=l;
    	}
    }
    int main() {
    	int m;
    	while(scanf("%d%d",&m,&n)&&m) {
    		int a,b,c,flag=0;
    		init();
    		memset(map,inf,sizeof(map));
    		for(int l=0; l<m; l++) {
    			scanf("%d%d%d",&a,&b,&c);
    			map[a][b]=map[b][a]=c;
    			Union(a,b);
    		}
    		for(int l=1; l<=n; l++) {
    			if(pre[l]==l) {
    				flag++;
    			}
    		}
    		if(flag>1) {
    			printf("?\n");
    			continue;
    		}
    		printf("%d\n",prim(n));
    	}
    	return 0;
    } 
       
        点击打开链接