社区讨论

玄学错误

P8287「DAOI R1」Flame参与者 3已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mhizlb40
此快照首次捕获于
2025/11/03 18:18
4 个月前
此快照最后确认于
2025/11/03 18:18
4 个月前
查看原帖
码风极丑,不喜勿喷 下面这份代码 WA on test1 ?!
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,h[1000005],a[1000005],H,T,f[1000005],u[1000005],c[1000005],zd;
struct bian{long long n,d;}b[4000005];
struct bibb{long long x,y,z;}bb[2000005];
struct node{long long x,y;}q[1000005];
long long find(long long x)
{
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)f[i]=i,u[i]=-1;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		b[i]={h[x],y},h[x]=i;
		b[i+m]={h[y],x},h[y]=i+m;
		bb[i]={x,y};
	}
	H=1;
	for(int i=1;i<=k;i++)
	{
		cin>>a[i];
		q[++T]={a[i],0};
		u[a[i]]=0;
	}
	while(H<=T)
	{
		for(int i=h[q[H].x];i;i=b[i].n)
		{
			if(u[b[i].d]==-1)
			{
				q[++T]={b[i].d,q[H].y+1},u[b[i].d]=u[q[H].x]+1;
			}
		}
		H++;
	}
	for(int i=1;i<=m;i++)
	{
		bb[i].z=max(u[bb[i].x],u[bb[i].y]);
	}
	sort(bb+1,bb+m+1,[](bibb x,bibb y){return x.z<y.z;});
	for(int i=1;i<=m;i++)
	{
		if(find(bb[i].x)!=find(bb[i].y))f[find(bb[i].x)]=find(bb[i].y);
		else
		{
			cout<<bb[i].z;
			return 0;
		}
	}
	cout<<"Poor D!";
    return 0;
}
将q数组开大就过了? 可是test1是m<n啊!!! 为什么宽搜的数组要开大啊!!!
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,h[1000005],a[1000005],H,T,f[1000005],u[1000005],c[1000005],zd;
struct bian{long long n,d;}b[4000005];
struct bibb{long long x,y,z;}bb[2000005];
struct node{long long x,y;}q[1000005];
long long find(long long x)
{
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)f[i]=i,u[i]=-1;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y;
		b[i]={h[x],y},h[x]=i;
		b[i+m]={h[y],x},h[y]=i+m;
		bb[i]={x,y};
	}
	H=1;
	for(int i=1;i<=k;i++)
	{
		cin>>a[i];
		q[++T]={a[i],0};
		u[a[i]]=0;
	}
	while(H<=T)
	{
		for(int i=h[q[H].x];i;i=b[i].n)
		{
			if(u[b[i].d]==-1)
			{
				q[++T]={b[i].d,q[H].y+1},u[b[i].d]=u[q[H].x]+1;
			}
		}
		H++;
	}
	for(int i=1;i<=m;i++)
	{
		bb[i].z=max(u[bb[i].x],u[bb[i].y]);
	}
	sort(bb+1,bb+m+1,[](bibb x,bibb y){return x.z<y.z;});
	for(int i=1;i<=m;i++)
	{
		if(find(bb[i].x)!=find(bb[i].y))f[find(bb[i].x)]=find(bb[i].y);
		else
		{
			cout<<bb[i].z;
			return 0;
		}
	}
	cout<<"Poor D!";
    return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...