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 ? 这个是最小生成树的模板题，根据节点（村庄）的数目可知，这个可以用Prim算法。可以直接套用Prim算法的模板题，不过需要注意的无向图的多重边的情况。 C++代码： #include<iostream> #include<algorithm> #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,M; while(cin>>N>>M){ if(N == 0) break; for(int i = 1; i <= M; i++){ for(int j = 1; j <= M; j++){ mp[i][j] = INF; } } int a,b,c; for(int i = 1; i <= N; i++){ cin>>a>>b>>c; if(c < mp[a][b]) mp[a][b] = mp[b][a] = c; //需要注意无向图的多重边的情况，选取其中最小的权就行。 } Prim(M,1,mp); int sum = 0; bool flag = true; //判断，判断是否构成了一个生成树。 for(int i = 1; i <= M; i++){ if(lowcost[i] == INF){ flag = false; } sum += lowcost[i]; } if(!flag) cout<<"?"<<endl; else cout<<sum<<endl; } return 0; }
转载于:https://www.cnblogs.com/Weixu-Liu/p/10898083.html
