拆地毯

 这个就是套用最小生成树的模板，只不过要将sort函数改成从大到小进行排序。然后这个退出条件是只要大于k就退出。
代码如下
 

#include<iostream>
#include<cmath>
#include<algorithm>
#define N 1009000
using namespace std;
int n,m,k;
struct node
{
	int x, y;
	int z;
}q[N];
int fa[N];
int cha(int x)
{
	return fa[x] == x ? x : fa[x] = cha(fa[x]);
}
void Union(int x, int y)
{
	x = cha(x);
	y = cha(y);
	if (x == y) return;
	if(x!=y)
	{
		fa[x] = y;
	}
}
bool cmp(node x, node y)
{
	return x.z > y.z;
}
int main()
{
	
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].x>>q[i].y>>q[i].z;
	}
	for (int i = 1; i <= N - 10; i++)
	{
		fa[i] = i;
	}
	sort(q + 1, q + 1 + m, cmp);
	int ans=0;
	int tmp=0;
	for (int i = 1; i <= m; i++)
	{
		if(cha(q[i].x)!=cha(q[i].y))
		{
			Union(q[i].x,q[i].y);
			ans+=q[i].z;
			tmp++;
			if(tmp>=k)
			{
				printf("%d\n",ans);
				return 0;
			}
		}
	}

	return 0;
}

营救

这题也是最小生成树的模板，只需要将设置一个打擂台的模板，将每一次比较的最大值记录下来就可以了
代码如下

#include<iostream>
#include<algorithm>
#define N 1000000
using namespace std;
int fa[N];
struct node
{
	int x,y,z;
}q[N];
bool cmp(node x,node y)
{
	return x.z<y.z;
}
int cha(int x){
	return fa[x]==x?x:fa[x]=cha(fa[x]);
}
void Union(int x,int y)
{
	x=cha(x);
	y=cha(y);
	if(x==y)return ;
	else
	{
		fa[x]=y;
	}
}
int n,m,s,t;
int main()
{
	int ans=0;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=N-10;i++)
	fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].x>>q[i].y>>q[i].z;
	}
	sort(q+1,q+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		if(cha(q[i].x)!=cha(q[i].y))
		{
			Union(q[i].x,q[i].y);
			ans=max(ans,q[i].z);
			if(cha(s)==cha(t))
			{
				cout<<ans<<endl;
				return 0;
			}
		}
	}
	return 0;
}