UVa 10369 - Arctic Network(求最小生成树的第k小边)

Myth丶恋晨 2022-06-10 12:11 132阅读 0赞

题目链接：https://vjudge.net/contest/179332\#problem/L

**题意：S个卫星设备，可以无条件安装，P个地点，可形成ant个地方，根据这ant个地方的远近，安装卫星设备(免费)和无线电设备，要使总的费用最小，就要找这ant个地方的最小生成树，然后用ans\[ \]记录他们距离的远近，sort排序把前S个远的用卫星设备连接，这样才能使按ans\[ant-S\]最小。题目求得是安装两个无线电设备的最短距离，就是求ans\[ant-S\]。**

**代码：**

#include<stdio.h>
    #include<algorithm>
    #include<math.h>
    #include<string.h>
    using namespace std;
    double map[10010][10010];
    double distance(double a,double b,double x,double y)
    {
    	return sqrt((a-x)*(a-x)+(b-y)*(b-y));
    }
    int main()
    {
    	int T;
    	int s,p,i,j;
    	double x[10010],y[10010];
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d%d",&s,&p);
    		for(i=0;i<p;i++)
    		{
    			scanf("%lf%lf",&x[i],&y[i]);
    		}
    		memset(map,0,sizeof(map));
    		for(i=0;i<p;i++)
    		{
    			for(j=i+1;j<p;j++)
    			{
    				map[i][j]=map[j][i]=distance(x[i],y[i],x[j],y[j]);
    			}
    		}
    		double lowcast[10010];
    		memset(lowcast,0,sizeof(lowcast));
    		double ans[10010];
    		int ant=0;
    		
    		for(i=0;i<p;i++)
    		{
    			lowcast[i]=map[0][i];
    		}
    		for(i=0;i<p-1;i++)
    		{
    				int k;
    				double min=1001010;
    				for(j=0;j<p;j++)
    				{
    					if(lowcast[j]!=0&&lowcast[j]<min)
    					{
    						min=lowcast[j];
    						k=j;
    					}
    				}
    				ans[ant++]=min;
    				lowcast[k]=0;
    				for(j=0;j<p;j++)
    				{
    					if(lowcast[j]!=0&&map[k][j]<lowcast[j])
    					{
    						lowcast[j]=map[k][j];
    					}
    				}	
    		}
    		sort(ans,ans+ant);
    		printf("%.2lf\n",ans[ant-s]);
    	 } 
    	 return 0;
    }

![大哭][wail.gif]

[wail.gif]: /images/20220610/5d730dd9b40a41dab7f88db9ed3d4c90.png