? ? ? ? ?實(shí)在傷心，一口氣A了三個暢通工程，太簡單的原因把。這個暢通工程求的是最小的公路長度，就是最小生成樹，點(diǎn)太少無向圖，prim就好了。

#include<stdio.h> #include<string.h> int map[100][100],d[100],n; bool v[100]; int Prim() {int i,j,mim,pt,ret;memset(d,0x7f,sizeof(d));memset(v,false,sizeof(v));pt=1; v[1]=true; ret=0;while( true){for( i=1; i<=n; i++) if( !v[i]&&map[pt][i]&&d[i]>map[pt][i])d[i]=map[pt][i]; pt=-1; mim=0x7fffffff;for( i=1; i<=n; i++){if( !v[i]&&mim>d[i] ){mim=d[i];pt=i;}} if( pt==-1) break;ret+=mim; v[pt]=true;}return ret; } int main() {int m,i,j,c;while( scanf("%d",&n)&&n){m=n*(n-1)/2;memset(map,0,sizeof(map));while( m--){scanf("%d%d%d",&i,&j,&c);map[i][j]=c;map[j][i]=c;} printf("%d\n",Prim());}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/java0721/archive/2012/07/16/2602895.html

總結(jié)

以上是生活随笔為你收集整理的HDOJ 1233 还是畅通工程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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