HDU 1875

• 一开始把不符合条件的边删掉
• 判断是否能 生成最小生成树

  #include <iostream>
  #include <string.h>
  #include <math.h>
  
  #define INF 0x3f3f3f3f
  using namespace std;
  const int maxn = 1e3;
  
  double e[maxn][maxn];
  int vis[maxn];
  double dist[maxn];
  int n,m;
  
  struct point {
  	int x,y;
  	point(){}
  	point(int a,int b) {
  		x=a; y=b;
  	}
  } points[maxn];
  
  double Distance(point& a,point& b) {
  	double dx = (a.x - b.x)*(a.x - b.x);
  	double dy = (a.y - b.y)*(a.y - b.y);
  	return sqrt(dx + dy);
  }
  
  int prim() {
  	memset(vis, 0 ,sizeof vis);
  	vis[1] = 1; //随便找一个点加入最小生成树中
  	for (int i=1; i<=n; i++) dist[i] = e[1][i]; // 更新每个点到树的距离
  	double sum = 0;//最短的路径长度
  	for (int i=1; i<n; i++) { // 开始找n-1条边
  		double minn = INF; // 距离树最短的边
  		int point = INF; // 距离树最近的点
  		for (int i=1; i<=n; i++) {
  			if (!vis[i] && dist[i]<minn ) {
  				point = i;
  				minn = dist[i];
  			}
  		}
  		if (minn == INF) {
  			printf("oh!\n");
  			return 0;
  		}
  		vis[point] = true; // 该点访问过（在树中）
  		sum += dist[point];
  		for (int i=1; i<=n; i++) {
  			if ( !vis[i] && e[point][i]<dist[i] )
  				dist[i] = e[point][i];
  		}
  	}
  	printf("%.1lf\n",sum*100);
  	return 0;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	int times; scanf("%d",&times);
  	while (times--) {
  		scanf("%d",&n);
  		for (int i=1; i<=n; i++) {
  			int x,y;
  			scanf("%d%d",&x,&y);
  			points[i] = point(x,y);
  		}
  		for (int i=1; i<=n; i++) 
  			for (int j=1; j<=n; j++) {
  				double dis = Distance(points[i],points[j]);
  				if (10.00000<=dis && dis <=1000.000001)
  					e[i][j] = e[j][i] = dis;
  				else e[i][j] = (double)0x3f3f3f3f;
  			}
  		prim();
  	}
  	return 0;
  }