社区讨论
改了一小时了,心都凉了 , dalao ballball你们救我一下
P3366【模板】最小生成树参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi7clo6q
- 此快照首次捕获于
- 2025/11/20 19:28 4 个月前
- 此快照最后确认于
- 2025/11/20 19:28 4 个月前
CPP
#include<iostream> // 链式前向星 + prim求最小生成树
using namespace std;
const int M=200007;
const int N=5007;
const int INF=99999999;
struct node
{
int to;
int next;
int w;
}edge[M<<1];
bool u[N];
int dis[N];
int cnt=1;
int head[N];
void add(int u,int v,int w) //加边
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int main()
{
int n,m,sum=0;
cin>>n>>m;
int x,y,z;
/*for(int i=1;i<=N;i++)
{
head[i]=-1;
}*/
for(int i=1;i<=m;i++) //双向边读入
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
for(int i=1;i<=n;i++)
{
dis[i]=INF;
}
for(int i=head[1];i;i=edge[i].next) //重边取边权最小的
{
dis[edge[i].to]=min(dis[edge[i].to],edge[i].w);
}
int num=0;
dis[1]=0;
int k=1;
while(++num<n) //朴素的prim算法
{
//cout<<"1"<<" ";
//int k=0;
int mint=INF;
u[k]=1;
for(int j=1;j<=n;++j)
{
if(!u[j]&&dis[j]<mint)
{
k=j;
mint=dis[j];
}
}
//if(k==0) break;
// u[k]=1;
//if(num==n-1) break;
//else num++;
sum+=mint;
for(int j=head[k];j;j=edge[j].next)
{
//cout<<head[1]<<" ";
if(!u[edge[j].next]&&dis[edge[j].to]>edge[j].w)
{
dis[edge[j].to]=edge[j].w;
//sum+=dis[edge[j].w] ;
}
}
}
/*for(int i=1;i<=n;i++)
{
sum+=dis[i]; 自闭输出???
}*/
cout<<sum;
}
只拿了40分 WA了3个点 RE了3个点
实在不知道哪里错了 dalao帮忙看一下,谢谢!
实在不知道哪里错了 dalao帮忙看一下,谢谢!
回复
共 4 条回复,欢迎继续交流。
正在加载回复...