@[George_qwe](/user/1068756) dfs 一遍，或者判断 kruskal 结束后加入的边数是否位 n-1
by OldDriverTree @ 2024-03-31 17:13:23
并查集
by meng_cen @ 2024-03-31 17:19:41
@[OldDriverTree](/user/681036) 用Prim+链式前向星就只能用dfs吗？
by George_qwe @ 2024-03-31 17:43:06
@[George_qwe](/user/1068756) 不是，判断选择的点 dis 是否为正无穷
by OldDriverTree @ 2024-03-31 17:44:19
@[OldDriverTree](/user/681036) 是Prim结束后判断吗？
by George_qwe @ 2024-03-31 17:47:45
```cpp
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int M=2e5+5;
const int N=5e3+5;
const int inf=0x7fffffff;
ll n,m,cnt,ans=0,tot,now=1;
ll size[M],head[M];
ll dis[N],vis[N];
struct Edge{
ll w,to,next;
}edge[2*M];//边集
inline int read()
{
int x=0,k=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
void add(int x,int y,int z){
cnt++;//边的编号, 1~n
edge[cnt].to=y;
edge[cnt].next=head[x];//next 存上一条边的编号
edge[cnt].w=z;
head[x]=cnt;
}
void init()
{
n=read(),m=read();
for(int i=1,u,v,w;i<=m;++i)
{
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);//双向边
}
}
void print(){
for(int i=1;i<=n;i++){
cout<<i<<endl;
for(int j=head[i];j!=-1;j=edge[j].next){
cout<<i<<" "<<j<<" "<<edge[j].to<<" "<<edge[j].w<<endl;
}
cout<<endl;
}
for(int i=1;i<=n;i++){
cout<<head[i]<<" ";
}
}
int prim(){
for(int i=2;i<=n;i++){dis[i]=inf; }
for(int j=head[1];j!=-1;j=edge[j].next){
dis[edge[j].to]=min(dis[edge[j].to] , edge[j].w);
}
while(tot<n-1){
++tot;
int minn=inf;
vis[now]=1;
for(int i=1;i<=n;i++){
if(!vis[i]&&minn>dis[i]){//找出连上的边的最小边
minn=dis[i];
now=i;
}
}
ans+=minn;
for(int j=head[now];j!=-1;j=edge[j].next){
int to=edge[j].to;
if(dis[to]>edge[j].w && !vis[to])
dis[to]=edge[j].w;
}
}
return ans;
}
int main(){
for(int i=1;i<=M;i++){set[i]=i; }
memset(head,-1,sizeof(head));
init();
//print();
printf("%d",prim());
return 0;
}
```
by George_qwe @ 2024-03-31 17:48:23
可以在prim之后判断所有点的dis是不是inf
@[George_qwe](/user/1068756)
by huangyige123 @ 2024-04-01 21:43:57
如果有一个点的dis是，就输出“orz”
by huangyige123 @ 2024-04-01 21:45:18
谢谢各位，已A
此贴结。
附dfs代码,供后人理解
```
void dfs(int x){
if(cot[x]==0){
cot[x]=1;
for(int j=head[x];j!=-1;j=edge[j].next){
dfs(edge[j].to);
}
}
}
int main(){
memset(head,-1,sizeof(head));
init();
//print();
dfs(1);
for(int i=1;i<=n;i++){
//cout<<cot[i];
if(cot[i]==0){
printf("orz");
return 0;
}
}
printf("%d",prim());
return 0;
}
```
勿直接抄代码
by George_qwe @ 2024-04-02 19:01:01