hduoj 畅通工程再续 1875

约定不等于承诺〃 2024-02-19 19:06 49阅读 0赞

## 畅通工程再续 ##

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 41067 Accepted Submission(s): 13793**

Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组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!

Author

8600

Source

[2008浙大研究生复试热身赛（2）——全真模拟 ][2008_2_]

题意解读：

题意很重要，符合条件的小岛才能直接连通，但不意味着：不符合条件的小岛就不能连通。

这点很重要

提供一个测试数据：

0 0

100 0

1 0

#include<iostream>
    #include<cstdio>
    #include<string.h>
    #include<cmath>
    using namespace std;
    #define range 105
    #define inf 0x3f3f3f
    double map[range][range];
    bool vis[range];
    double dis[range];
    struct node
    {
    	int x,y;
    }s[range];
    double Distance(node a,node b)
    {
    	return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
    }
    void Prim(int n)
    {
    	int i,j,f=0;
    	int pos=0;
    	double sum=0;
    	
    	for(i=0;i<n;i++)
    	dis[i]=map[pos][i];
    	vis[pos]=true;
    	for(i=0;i<n-1;i++)
    	{
    		double min=inf;
    		
    		for(j=0;j<n;j++)
    		{
    			if(!vis[j]&&dis[j]<min)
    			{
    				min=dis[j];
    				pos=j;
    			}
    		}
    		if(min==inf)
    		{
    			printf("oh!\n");
    		    return ;
    		}
    		sum+=min;
    		vis[pos]=true;	
    		f++;
    		for(j=0;j<n;j++)
    		{
    			if(!vis[j]&&dis[j]>map[pos][j])
    			{
    		         dis[j]=map[pos][j];
    			}
    		}	
    	}
    	
    	
    	printf("%.1lf\n",sum*100);
    }
    int main()
    {
    	int m,n,i,j;
    	while(~scanf("%d",&m))
    	{
    		
    		
    		while(m--)
    		{   
    		    
    			double d=0;
    			memset(map,inf,sizeof(map));
    			memset(vis,false,sizeof(vis));
    			memset(dis,inf,sizeof(dis));
    			scanf("%d",&n);
    			if(n==0)
    		    break;
    			for(i=0;i<n;i++)
    			scanf("%d %d",&s[i].x,&s[i].y);
    			
    			for(i=0;i<n;i++)
    			{
    				map[i][i]=0;
    				for(j=i+1;j<n;j++)
    				{
    					d=Distance(s[i],s[j]);
    					if(d>=10.000000&&d<=1000.000001)
    					{
    						map[i][j]=map[j][i]=d;
    					}
    					else
    					map[i][j]=map[j][i]=inf;
    				}
    			}
    			Prim(n);
    		}
    	}
    	
    	return 0;
     }

当不符合条件时，map我第一次设为0，然后在

if(min==inf)
    		{
    			printf("oh!\n");
    		    return ;
    		}

在这个地方判断的是min！=0

进行累加，wa了

仔细想想

因为dis数组每次都是找到一个最小值，所以不能设置成0，应该设置成inf，

当min=inf时，要么节点访问完了或剩下的都是不符合条件的小岛。

[2008_2_]: http://acm.hdu.edu.cn/search.php?field=problem&key=2008%D5%E3%B4%F3%D1%D0%BE%BF%C9%FA%B8%B4%CA%D4%C8%C8%C9%ED%C8%FC%A3%A82%A3%A9%A1%AA%A1%AA%C8%AB%D5%E6%C4%A3%C4%E2&source=1&searchmode=source