求助,不考虑输出方案
查看原帖
求助,不考虑输出方案
649095
幻想繁星NM 猫猫可爱楼主2024/10/7 13:09

这份代码为什么错了:



#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T> inline void read(T &t) {
	t=0;char c=getchar();long long f=1;
	while(!isdigit(c)) {if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)) t=(t<<3)+(t<<1)+(c^'0'),c=getchar();
	t*=f;
}
template <typename T, typename ... Args> inline void read(T &t,Args&... args){read(t);read(args...);}
template <typename T> inline void write(T x,char c='\0'){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
	if(c!='\0') putchar(c);
}
inline long long read()
{
	long long t=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)) t=(t<<3)+(t<<1)+(c^'0'),c=getchar();
	return t*f;
}
int n,m,k,ans,sum;
vector<tuple<int,int,int,int> >e(20004);
vector<int>fa(10004),siz(10004);
int find(int x)
{
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
bool check(int x)
{
	sum=0;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		siz[i]=1;
	}
	for(int i=1;i<m;i++)
	{
		if(x>=get<3>(e[i])&&find(get<1>(e[i]))!=find(get<0>(e[i])))
		{
			if(siz[find(get<0>(e[i]))]>siz[find(get<1>(e[i]))])
			{
				siz[find(get<0>(e[i]))]+=siz[find(get<1>(e[i]))];
				fa[find(get<1>(e[i]))]=find(get<0>(e[i]));
			}
			else
			{
				siz[find(get<1>(e[i]))]+=siz[find(get<0>(e[i]))];
				fa[find(get<0>(e[i]))]=find(get<1>(e[i]));
			}
		}
		if(x>=get<2>(e[i]))
			sum++;
	}
	if(sum<k) 
		return 0;
	for(int i=2;i<=n;i++)
		if(find(1)!=find(i))
			return 0;
	return 1;
}
int main()
{
	read(n,k,m);
	for(int i=1,u,v,c1,c2;i<m;i++)
	{
		read(u,v,c1,c2);
		e[i]=make_tuple(u,v,c1,c2);
	}
	int l=1,r=30000,mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	write(ans);
	return 0;
}
2024/10/7 13:09
加载中...