B - 畅通工程再续 最小生成树

时间：2021-04-09 20:28:59
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在*决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，*决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

Input输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

Output每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.Sample Input

2

2

10 10

20 20

3

1 1

2 2

1000 1000

Sample Output

1414.2

oh!

因为要求最小花费，所以很明显是最小生成树。
具体和之前那个有点不同，就是cost 没有直接给出，但是题目给出c的范围，所以可以断定不会超时。
具体最好用prim算法，因为这个它的边特别多，但是呢，我学的prime和kruskal差不多，所以都可以试试，然后再学一下不一样的prim
具体怎么写呢，就是先输入，输入之后，求出cost，再建图。这题有点特别就是有两种不能搭桥，所以要特殊化一下。
特殊化之后再进行prim算法，最后再判断有没有都连起来，没有就输出oh！


#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#include <queue>

#include <math.h>

#include <vector>

using namespace std;

const  int maxn=110;

struct ed

{

	int x,y;

}exa[maxn];

struct node

{

	int to;

	double cost;

	node(int to=0,double cost=0) : to(to), cost(cost) {}

	bool operator<(const node &a) const{

	    return a.cost<cost;

	}

};

std::priority_queue<node>que;

std::vector<node>g[maxn];

int c;

bool vis[maxn];

double dis(ed a,ed b)

{

	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));

}

void build_map()

{

	double len;

	for(int i=1;i<=c;i++)

	{

		for(int j=1;j<=c;j++)

		{

			if(i==j) continue;

			len=dis(exa[i],exa[j]);

			//printf("%d %d %lf\n",i,j,len);

			if(len<10||len>1000) len=-1;

			g[i].push_back(node(j,len));

		}

	}

}

double prim()

{

	double res=0;

	vis[1]=1;

	for(int i=0;i<g[1].size();i++) que.push(g[1][i]);

	//printf("%d\n",que.size());

	while(que.size())

	{

		node ex=que.top();

		que.pop();

		//printf("%d %lf\n",ex.to,ex.cost);

		if(vis[ex.to]) continue;

		if(ex.cost==-1) continue;

		vis[ex.to]=1;

		res+=ex.cost;

		for(int i=0;i<g[ex.to].size();i++) que.push(g[ex.to][i]);

	}

	return res;

}

int main()

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

	    scanf("%d",&c);

		while(que.size()) que.pop();

		for(int i=1;i<=c;i++) g[i].clear();

		memset(vis,0,sizeof(vis));

		for(int i=1;i<=c;i++)

		scanf("%d%d",&exa[i].x,&exa[i].y);

		build_map();

		double res=prim();

		for(int i=1;i<=c;i++) if(!vis[i]) res=-1;

		if(res<0) printf("oh!\n");

		else printf("%.1lf\n",res*100);

	}

	return 0;

}

　　

相关文章