厦门微网站建设,贵德网站建设,公司内部网站,广东深圳今天最新通知这个畅通工程还是一交就过#xff0c;看来畅通工程用来入门是最好了#xff0c;以后拿这些来挂就不会那么打击人了#xff0c;天天开心。这里求最小生成树之前要自己构图#xff0c;很简单就是求出点到点之间的距离#xff0c;如果距离大于1000和小于10都视作不连通。点少… 这个畅通工程还是一交就过看来畅通工程用来入门是最好了以后拿这些来挂就不会那么打击人了天天开心。这里求最小生成树之前要自己构图很简单就是求出点到点之间的距离如果距离大于1000和小于10都视作不连通。点少还是Prim就好了。不过这里存在不连通的情况不想前面的的工程那么畅通最后加一个循环判断就好了。 #includestdio.h
#includemath.h
#includestring.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( i0; ic-1; i){for( ji1; jc; j){tDist(pt[i],pt[j]);if( t10t1000){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));pt0; v[0]true; ret0;while( true){for( i0; ic; i) if( !v[i]map[pt][i](d[i]map[pt][i]||d[i]0) )d[i]map[pt][i]; pt-1; mim10000;for( i0; ic; i){if( !v[i]d[i]mimd[i] ){mimd[i];pti;}} v[pt]true;if( pt-1) break;retmim; }for( i0; ic; i)//判断是否联通if( !v[i])return -1; return ret;
}
int main()
{int t,i;double ret;scanf(%d,t);while( t--){scanf(%d,c);for( i0; ic; i)scanf(%d%d,pt[i].x,pt[i].y); Graph();retPrim();if( ret-1)printf(oh!\n);else{retret*100;printf(%.1lf\n,ret);}}return 0;
}转载于:https://www.cnblogs.com/java0721/archive/2012/07/16/2602894.html
