rt

请大佬看看，有两个问题：

1.题为什么要求最小生成树的单个子图，不挨着的两个子图不能是最优解吗？

以下是题解的AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=510;
const int M=250010;

int n;
int s,p;
pair<int,int> d[N];
int cnt;
int fa[N];

struct node
{
	int x,y;
	double z;
}edg[M];

bool operator<(node a,node b)
{
	return a.z<b.z;
}

int zfind(int x)
{
	if(x==fa[x]) return x;
	else return fa[x]=zfind(fa[x]);
}

double getdis(int x1,int x2,int y1,int y2)
{
	double a=x1-x2,b=y1-y2;
	return sqrt(a*a+b*b);
}

void kruskal()
{
	int ans=0; 
	sort(edg+1,edg+cnt+1);
	for(int i=1;i<=p;i++) fa[i]=i;
	for(int i=1;i<=cnt;i++)
	{
		int x=zfind(edg[i].x);
		int y=zfind(edg[i].y);
		if(x==y) continue;
		fa[x]=y;
		ans++;
		if(ans==p-s)
		{
			printf("%.2lf\n",edg[i].z);
			return;
		}
	}
}

int main()
{
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d %d",&s,&p);
		for(int i=1;i<=p;i++)
			scanf("%d %d",&d[i].first,&d[i].second);
		
		cnt=0;
		for(int i=1;i<p;i++)
		{
			for(int j=i+1;j<=p;j++)
			{
				cnt++;
				edg[cnt].x=i;
				edg[cnt].y=j;
				edg[cnt].z=getdis(d[i].first,d[j].first,d[i].second,d[j].second);
			}
		}
		
		if(s==p) printf("0.00\n");
		else kruskal();
	}
	return 0;
}

2.我的最初思路是将kruskal所选的边标记，因为sort过了所以我从后标记的开始向前遍历，如果s足够支持删边就-1或-2（有可能一个点已经被标记删除了）并标记这两个点，直到无法再次删除最大边为止。有什么问题吗？

以下是最初思路的代码

#include <bits/stdc++.h>
using namespace std;
const int N=510;
const int M=250010;

int n;
int s,p;
pair<int,int> d[N];
int cnt;
int fa[N];
vector<int> V;
bool vis[N];

struct node
{
	int x,y;
	double z;
}edg[M];

bool operator<(node a,node b)
{
	return a.z<b.z;
}

int zfind(int x)
{
	if(x==fa[x]) return x;
	else return fa[x]=zfind(fa[x]);
}

double getdis(int x1,int x2,int y1,int y2)
{
	double a=x1-x2,b=y1-y2;
	return sqrt(a*a+b*b);
}

void kruskal()
{
	V.clear();
	sort(edg+1,edg+cnt+1);
	for(int i=1;i<=p;i++) fa[i]=i;
	for(int i=1;i<=cnt;i++)
	{
		int x=zfind(edg[i].x);
		int y=zfind(edg[i].y);
		if(x==y) continue;
		fa[x]=y;
		V.push_back(i);
	}
}

int main()
{
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d %d",&s,&p);
		for(int i=1;i<=p;i++)
			scanf("%d %d",&d[i].first,&d[i].second);
		
		cnt=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<p;i++)
		{
			for(int j=i+1;j<=p;j++)
			{
				cnt++;
				edg[cnt].x=i;
				edg[cnt].y=j;
				edg[cnt].z=getdis(d[i].first,d[j].first,d[i].second,d[j].second);
			}
		}
		
		kruskal();
		
		int t=V.size()-1;
		for(int i=t;i>=0;i--)
		{
			int x=edg[V[i]].x,y=edg[V[i]].y;
			if(!s) break;
			if(vis[x]&&vis[y]) continue;
			else if(vis[x]||vis[y])
			{
				s--;
				vis[x]=vis[y]=true;
				V.pop_back();
			}
			else if(s>=2)
			{
				s-=2;
				vis[x]=vis[y]=true;
				V.pop_back();
			}
			else break;
		}
		printf("%.2lf\n",edg[V[V.size()-1]].z);
	}
	return 0;
}

谢谢能够提出指导意见的各位大佬，这是我第一次发提问，还请大家包涵不好的地方