(最小生成树 Prim) HDU 1233 还是畅通工程

Problem Description 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。  

 

Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。  

 

Output 对每个测试用例，在1行里输出最小的公路总长度。  

 

Sample Input 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  

 

Sample Output 3 5   Hint Huge input, scanf is recommended.   这是一个最小生成树的模板题，由于节点的个数不大于100，所以可以直接套用Prim模板，除此之外，这个可以用Kruskal算法。 C++代码： #include<iostream> #include<cstdio> using namespace std; const int maxn = 110; const int INF = 0x3f3f3f3f; int mp[maxn][maxn]; int lowcost[maxn]; bool vis[maxn]; void Prim(int n, int u0, int mp[maxn][maxn]){ vis[u0] = true; for(int i = 1; i <= n; i++){ if(i != u0){ lowcost[i] = mp[u0][i]; vis[i] = false; } else lowcost[i] = 0; } for(int i = 1; i <= n; i++){ int minn = INF,u = u0; for(int j = 1; j <= n; j++){ if(!vis[j] && lowcost[j] < minn){ minn = lowcost[j]; u = j; } } if(u == u0) break; vis[u] = true; for(int j = 1; j <= n; j++){ if(!vis[j] && lowcost[j] > mp[u][j]) lowcost[j] = mp[u][j]; } } } int main(){ int N; while(cin>>N){ if(N==0) break; int M = (N*(N-1))/2; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ mp[i][j] = INF; } } int a,b,c; for(int i = 1; i <= M; i++){ cin>>a>>b>>c; if(c < mp[a][b]){ mp[a][b] = mp[b][a] = c; } } Prim(N,1,mp); int sum = 0; for(int i = 1; i <= N; i++){ sum += lowcost[i]; } cout<<sum<<endl; } return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10898295.html