时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：1653
解决：838
- 题目描述：
-
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
- 输入：
-
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
- 输出：
-
对每个测试用例，在1行里输出最小的公路总长度。
- 样例输入：
-
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
- 样例输出：
-
3 5
- 来源：
- 2006年浙江大学计算机及软件工程研究生机试真题
-
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define maxs 0x3f3f3f3f using namespace std; int mat[105][105]; int main() { int ans,mins,i,j,n,a,b,v,p,low[105]; bool visited[105]; while(scanf("%d",&n)!=EOF&&n) { ans=0,p=0; for(i=0; i<n; i++) for(j=0; j<n; j++) mat[i][j]=maxs; memset(visited,false,sizeof(visited)); for(i=0; i<(n*(n-1)/2); i++) { scanf("%d%d%d",&a,&b,&v); mat[--a][--b]=v; mat[b][a]=v; } visited[0]=true; low[0]=maxs; for(i=1; i<n; i++) low[i]=mat[0][i]; for(i=0; i<n-1; i++) { mins=maxs; for(j=0; j<n; j++) if(!visited[j]&&low[j]<mins) { mins=low[j]; p=j; } ans+=mins; visited[p]=true; for(j=0; j<n; j++) if(!visited[j]&&low[j]>mat[p][j]) low[j]=mat[p][j]; } printf("%d\n",ans); } return 0; }畅通工程
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13011 Accepted Submission(s): 5315
Problem Description省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
Output对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
Sample Input3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
Sample Output3 ?
Source
Recommendlcy#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define maxs 0x3f3f3f3f using namespace std; int mat[200][200]; int main() { int n,m,a,b,v,low[200],ans,i,j,mins,p; bool visited[200]; while(scanf("%d%d",&n,&m)!=EOF&&n)//n为边 { ans=0; memset(visited,false,sizeof(visited)); for(i=0; i<m; i++) for(j=0; j<m; j++) mat[i][j]=maxs; for(i=0; i<n; i++) { cin >> a >> b >> v; mat[--a][--b]=v; mat[b][a]=v; } low[0]=maxs,visited[0]=true,p=0; for(i=1; i<m; i++) low[i]=mat[0][i]; for(i=0; i<m-1; i++) { mins=maxs; for(j=0; j<m; j++) if(!visited[j]&&low[j]<mins&&low[j]!=maxs)//多加啦一个判断条件，判断是否联通 { mins=low[j]; p=j; } ans+=mins; visited[p]=true; for(j=0; j<m; j++) if(!visited[j]&&mat[p][j]<low[j]) low[j]=mat[p][j]; } for(i=0; i<m; i++)//不是所有点都访问过那么就不连通 if(!visited[i])break; if(i==m) cout << ans << endl; else cout << "?" << endl; } return 0; }