牛客练习赛——牛能和小镇（最小生成树）

水深无声 2023-07-14 08:22 66阅读 0赞

### 牛能和小镇题目 ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]  
[题目链接][Link 1]  
刚看到这道题的时候，由于我不懂最小生成树。。。我以为是普通的计算题，第一想法就是通过计算每个小镇最少有一条通往花费最少的小镇。于是我写出了下面的代码。

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    ll xz[100010][2];
    bool judge[100010]={ false};
    
    //a城市到b城市花费 
    ll cheek(ll a, ll b)
    { 
    	ll ab;
    	ab=abs(pow(xz[a][0], 2)*xz[a][1]-\
    	pow(xz[b][0], 2)*xz[b][1]+\
    	pow(xz[a][1], 2)*(xz[a][1]-2*xz[a][0])-\
    	pow(xz[b][1], 2)*(xz[b][1]-2*xz[b][0]));
    	
    	return ab;
    }
    
    int main()
    { 
    	ll n, temp=1e9+7, sum=0, i, j, a;
    	cin>>n;
    	for(int i=0; i<n; i++)
    	for(int j=0; j<2; j++)
    	cin>>xz[i][j];
    	
    	for(i=0; i<n; i++)
    	{ 	
    		if(judge[i]==true)
    			continue;
    		for(j=0; j<n; j++)
    		{ 
    			if(j==i) continue;
    			int temp1=min(temp,cheek(i, j));
    			if(temp1!=temp)
    			{ 
    				a=j;
    				temp=temp1;
    			}
    		}
    		judge[a]=true;
    		judge[i]=true;
    		sum+=temp;
    		temp=1e9+7;
    	}
    	cout<<sum;
    	return 0;
    }

但是很显然这里的时间复杂度O(n^2)过大，不能够达到AC条件。  
在比赛后，我查了下AC代码：

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std;
    ll spent_arr[100010];
    int main()
    { 
    	ll x, y, n, sum=0;
    	cin>>n;
    	for(int i=0; i<n; i++)
    	{ 
    		cin>>x>>y;
    		spent_arr[i]=x*x*y+y*y*(y-2*x);
    	}
    	sort(spent_arr, spent_arr+n);
    	for(int i=0; i<n-1; i++)
    	sum+=spent_arr[i+1]-spent_arr[i];
    	cout<<sum;
    	
    	return 0;
    }

根据题目，我们假设要计算A镇(a, b)修路到c镇(c,d)的花费money  
money=|a2b-c2d+b2(b-2*a)-d2(d-2*c)|  
变形得到：money=|a2b+b2(b-2*a)-c2d-d2(d-2*c)|  
再变形：**money=||a2b+b2(b-2*a)|-|c2d-d2(d-2*c)||**  
由这个表达式我们可以知道**A镇修路到c镇的花费只与A镇与B镇自身有关**，A镇与B镇之间没有联系（两个镇修道路的花费，两镇之间竟然没有联系！）。  
设spent=x2y+y2(y-2\*x)  
我们只用计算出每个小镇的spent值，然后在将每个小镇的spent值由小到大排序得到spent\_arr数组。题目要求：每个小镇要互通、花费要最少，spent\_arr数组排好序后，依次将相邻的互减取绝对值，最后求和。  
sum=spent\_arr\[1\] - spent\_arr\[0\] + spent\_arr\[2\] - spent\_arr\[1\] + … + spent\_arr\[n\] - spent\_arr\[n-1\].

**小结**：题目是要我们求一颗最小生成树。我们把距离公式交换一下顺序， 排一下序，相邻两点之间连一条边即可得到最小生成树，时间复杂度O(nlogn)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: /images/20230529/2b33da443aa64c66a28521adf5eb9bde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]: /images/20230529/15409e4a06ed44aba297ff0df1d9ff52.png
[Link 1]: https://ac.nowcoder.com/acm/contest/4743/B