社区讨论

改了一小时了,心都凉了 , 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帮忙看一下,谢谢!

回复

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

正在加载回复...