社区讨论
prim算法,过了,有一点不理解
P3366【模板】最小生成树参与者 2已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mhjhyw2g
- 此快照首次捕获于
- 2025/11/04 02:52 4 个月前
- 此快照最后确认于
- 2025/11/04 02:52 4 个月前
我的WA 16pts 代码:
CPP#include <iostream>
using namespace std;
const int N=5000+10,M=2e5+10;
const int inf=0x7fffffff;
int e[N][N];
int vis[N];
int d[N];
int n,m,x,y,z,ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
e[i][j]=inf;
}
}
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
e[x][y]=min(e[x][y],z);
e[y][x]=e[x][y];
}
vis[1]=1;
for(int i=1;i<=n;i++)
{
d[i]=e[1][i];
}
for(int i=1;i<n;i++)
{
int tmp=-1,mi=inf;
for(int j=1;j<=n;j++)
{
if(vis[j]==1) continue;
if(d[j]<mi)
{
mi=d[j];
tmp=j;
}
}
if(mi==inf)
{
cout<<"orz\n";
return 0;
}
ans+=mi;
vis[tmp]=1;
for(int j=1;j<=n;j++)
{
d[j]=e[tmp][j];// #### 这一行有问题
}
}
cout<<ans<<'\n';
return 0;
}
调了很久,才发现有注释的那一行应改为
d[j]=min(d[j],e[tmp][j]);。但是我不理解这是为什么,求解答
回复
共 7 条回复,欢迎继续交流。
正在加载回复...