~~Kruskal它不香吗~~
by Toclhu @ 2020-04-21 15:24:29
**~~**在下蒟蒻**~~ **
**~~不会~~**
by shuitl @ 2020-04-21 15:26:27
~~Kruskal它不香吗~~
by liqingyang @ 2020-04-21 15:28:44
~~prim让我想起某最短路算法~~
by 童年如作业 @ 2020-04-21 15:48:25
呼叫大佬
by 只狼 @ 2020-04-21 15:51:14
@[hxl23333](/user/272531) 我的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int Max=5e3+5,INF=2e9;
struct edge
{
int to,w,next;
}e[400005];
int head[Max],cnt;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
return;
}
struct node
{
int root,w;
bool operator <(const node &a) const
{
return w>a.w;
}
};
int n,m,ans;
bool vis[Max];
priority_queue<node>que;
void prim(int s)
{
que.push((node){s,0});
while(!que.empty())
{
node a=que.top();
que.pop();
if(vis[a.root]) continue;
vis[a.root]=1;
ans+=a.w;
for(int i=head[a.root];i;i=e[i].next)
{
if(!vis[e[i].to]) que.push((node){e[i].to,e[i].w});
}
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
prim(1);
for(int i=1;i<=n;i++) if(!vis[i]) {printf("orz");return 0;}
printf("%d",ans);
return 0;
}
```
by 童年如作业 @ 2020-04-21 16:02:53
@[hxl23333](/user/272531) 您没有判断重边
修改后：
```cpp
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int vis[5009],a[5002][5002],parent[5002];
int main(){
int i,j,n,m,k,l,cnt=1,sum=0;
pair<int,int> pii;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
cin>>n>>m;
for(l=0;l<m;l++){
cin>>i>>j>>k;
if (a[i][j] == 0 || a[i][j] > k) a[i][j] = k;
if (a[j][i] == 0 || a[j][i] > k) a[j][i] = k;
}
vis[2]=1;//选择一个入点
for(i=1;i<=n;i++){
if(a[i][2]!=0){
q.push(make_pair(a[i][2],i));
}
}
//开始 prim
while(cnt!=n){
pii=q.top();
q.pop();
k=pii.second;
sum+=pii.first;
cnt++;
vis[k]=1;//该点进入树
for(i=1;i<=n;i++){
if(vis[i]!=1&&a[i][k]!=0)//不会出现重复点
q.push(make_pair(a[i][k],i));
}
}
cout<<sum;
return 0;
}
```
by szTom @ 2020-04-21 16:09:07
对了，不止这一个问题，改完20分，建议您先被着急提交
by szTom @ 2020-04-21 16:10:44
@[hxl23333](/user/272531)
您每次都要重新判断是否访问过了：
```cpp
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int vis[5009],a[5002][5002],parent[5002];
int main(){
int i,j,n,m,k,l,cnt=1,sum=0;
pair<int,int> pii;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
cin>>n>>m;
for(l=0;l<m;l++){
cin>>i>>j>>k;
if (a[i][j] == 0 || a[i][j] > k) a[i][j] = k;
if (a[j][i] == 0 || a[j][i] > k) a[j][i] = k;
}
vis[2]=1;//选择一个入点
for(i=1;i<=n;i++){
if(a[i][2]!=0){
q.push(make_pair(a[i][2],i));
}
}
//开始 prim
while(cnt!=n){
pii=q.top();
q.pop();
k=pii.second;
if (vis[k]) continue; //这里
sum+=pii.first;
cnt++;
vis[k]=1;//该点进入树
for(i=1;i<=n;i++){
if(vis[i]!=1&&a[i][k]!=0)//不会出现重复点
q.push(make_pair(a[i][k],i));
}
}
cout<<sum;
return 0;
}
```
by szTom @ 2020-04-21 16:16:10
非常感谢大佬@szTom！！！！！！！
by 只狼 @ 2020-04-21 18:42:02