? ? ? ? ? 這個暢通工程還是一交就過，看來暢通工程用來入門是最好了，以后拿這些來掛就不會那么打擊人了，天天開心。這里求最小生成樹之前要自己構(gòu)圖，很簡單就是求出點到點之間的距離，如果距離大于1000和小于10都視作不連通。點少，還是Prim就好了。不過這里存在不連通的情況，不想前面的的工程那么暢通，最后加一個循環(huán)判斷就好了。

#include<stdio.h> #include<math.h> #include<string.h> struct Point {int x,y; } pt[105]; double d[105],map[105][105]; bool v[105]; int c; double Dist(Point a,Point b) {return sqrt( (a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y) ); } void Graph() {int i,j;double t;memset(map,0,sizeof(map));for( i=0; i<c-1; i++){for( j=i+1; j<c; j++){t=Dist(pt[i],pt[j]);if( t>=10&&t<=1000){map[i][j]=t;map[j][i]=t;}}} } double Prim() {int i,j,pt;double ret,mim;memset(d,0,sizeof(d));memset(v,false,sizeof(v));pt=0; v[0]=true; ret=0;while( true){for( i=0; i<c; i++) if( !v[i]&&map[pt][i]&&(d[i]>map[pt][i]||d[i]==0) )d[i]=map[pt][i]; pt=-1; mim=10000;for( i=0; i<c; i++){if( !v[i]&&d[i]&&mim>d[i] ){mim=d[i];pt=i;}} v[pt]=true;if( pt==-1) break;ret+=mim; }for( i=0; i<c; i++)//判斷是否聯(lián)通if( !v[i])return -1; return ret; } int main() {int t,i;double ret;scanf("%d",&t);while( t--){scanf("%d",&c);for( i=0; i<c; i++)scanf("%d%d",&pt[i].x,&pt[i].y); Graph();ret=Prim();if( ret==-1)printf("oh!\n");else{ret=ret*100;printf("%.1lf\n",ret);}}return 0; }

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

總結(jié)

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

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