問題描述:

省政府“暢通工程”的目標(biāo)是使全省任何兩個村莊間都可以實現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。經(jīng)過調(diào)查評估，得到的統(tǒng)計表中列出了有可能建設(shè)公路的若干條道路的成本。現(xiàn)請你編寫程序，計算出全省暢通需要的最低成本

Input

測試輸入包含若干測試用例。每個測試用例的第1行給出評估的道路條數(shù) N、村莊數(shù)目M ( < 100 )；隨后的 N?
行對應(yīng)村莊間道路的成本，每行給出一對正整數(shù)，分別是兩個村莊的編號，以及此兩村莊間道路的成本（也是正整數(shù)）。為簡單起見，村莊從1到M編號。當(dāng)N為0時，全部輸入結(jié)束，相應(yīng)的結(jié)果不要輸出。?

Output

對每個測試用例，在1行里輸出全省暢通需要的最低成本。若統(tǒng)計數(shù)據(jù)不足以保證暢通，則輸出“?”。?

Sample Input

3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100 Sample Output

3 ?

題目題意:題目給我們m個點之間的幾條路，問有沒有最小生成樹，有輸出結(jié)果，沒有輸出?

代碼如下:

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;const int INF=0x3f3f3f3f; const int maxn=105; int cost[maxn][maxn]; int mincost[maxn]; bool vis[maxn]; int V,res;//答案void prim() {for (int i=1;i<=V;i++) {mincost[i]=INF;vis[i]=false;}res=0;mincost[1]=0;while (true) {int v=-1;for (int u=1;u<=V;u++) {if (!vis[u]&&(v==-1||mincost[u]<mincost[v])) v=u;}if (v==-1) break;vis[v]=true;res+=mincost[v];for (int u=1;u<=V;u++)mincost[u]=min(mincost[u],cost[v][u]);} } int main() {int m;while (scanf("%d%d",&m,&V)!=EOF) {if (m==0) break;for (int i=1;i<=V;i++)for (int j=1;j<=V;j++)cost[i][j]=INF;for (int i=0;i<m;i++) {int a,b,c;scanf("%d%d%d",&a,&b,&c);cost[a][b]=cost[b][a]=c;}prim();if (res>INF)//大于INF就沒有結(jié)果printf("?\n");elseprintf("%d\n",res);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 1863 (图论基础prim算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。