社区讨论
玄学错误
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 条回复,欢迎继续交流。
正在加载回复...