昨晚f题
  • 板块学术版
  • 楼主fengzhaoyu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/28 08:24
  • 上次更新2024/7/28 10:18:44
查看原帖
昨晚f题
983555
fengzhaoyu楼主2024/7/28 08:24

为什么会城出现一些奇怪的错误?求助

#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int MAXN=6e7+10;
int fa[MAXN];
int a,b,w,n,q,cnt=0,ans=0,idx;
int rqead()
{
	int t=1,x=0;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
			t=-1;
		ch=getchar();	
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*t;
}
void print(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
		print(x/10);
	putchar(x%10+'0');
}
struct edge{
	int a,b,w;
}e[MAXN];
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int find(int x)
{
	if(fa[x]==x)
	return x;
	else
	return fa[x]=find(fa[x]);
}
void join(int x,int y)
{
	int f1=find(x),f2=find(y);
	if(fa[f1]!=fa[f2])
	fa[f1]=f2;
}
int kruskal()
{
	for(int i=1;i<=idx;++i)
	{
		if(find(e[i].a)!=find(e[i].b))
		{
			join(e[i].a,e[i].b);
			cnt++;
			ans+=e[i].w;
		}
		if(cnt==n+q-1)
		break;
	}
	return cnt;
}
signed main()
{
	n=rqead(),q=rqead();
	for(int i=1;i<=n+q;++i) fa[i]=i;
	for(int i=1;i<=q;++i) 
	{
        int l,r,w;
		l=rqead();r=rqead();w=rqead();
		for(int j=l;j<=r;j++)
		{
			e[++idx].a=j;
			e[idx].b=i+n;
			e[idx].w=w;
			e[++idx].a=i+n;
			e[idx].b=j;
			e[idx].w=w;
		}
	}
	sort(e+1,e+1+idx,cmp);
	int k=kruskal();
	if(k!=n+q-1)
	print(-1);
	else
	print(ans);
	return 0;
}
2024/7/28 08:24
加载中...