@[wu13115899522](/user/442963) wbh怎么prim都会了，我都不会
by Xjin @ 2022-09-28 19:27:39
啊这
by wu13115899522 @ 2022-09-28 19:31:50
@[wu13115899522](/user/442963) 你的cost[x][y]=cost[y][x]=z
是不是应该改成cost[x][y]=cost[y][x]=min(z,cost[x][y]);别的未知
by Xjin @ 2022-09-28 21:50:04
@[wu13115899522](/user/442963) 干嘛不打克鲁斯卡尔
by Xjin @ 2022-09-28 21:50:35
@[wu13115899522](/user/442963) 我Kruskal都过了
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[5005],ans,sum;
struct data{
int x,y,z;
bool operator < (const data b) const {
return z<b.z;
}
}eadg[400005];
int read(){
char ch=getchar();
int x=0,f=1;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int getfa(int x){
if(fa[x]==x)return x;
return fa[x]=getfa(fa[x]);
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){eadg[i].x=read();eadg[i].y=read();eadg[i].z=read();}
sort(eadg+1,eadg+m+1);
for(int i=1;i<=m;i++){
int fx=getfa(eadg[i].x);
int fy=getfa(eadg[i].y);
if(fx!=fy){
fa[fx]=fy;
ans+=eadg[i].z;
sum++;
}
if(sum==n-1)break;
}
if(sum!=n-1){
cout<<"orz";
return 0;
}
printf("%d",ans);
return 0;
}
```
不必prim好打？？？
by Xjin @ 2022-09-28 22:43:27
@[wu13115899522](/user/442963)
《prim》
1. `dis[j]=dis[mj]+cost[mj][j];`你认真的？并且更新还判vis您是打算只更新一次是吧。这个prim跟我用rand随机输出一个答案没什么不同。建议重学prim捏
2. 你的写法是以1为起点，但你却没有标记`vis[1]=1`
3. 邻接表的确不用判重边，但是邻接矩阵不需要判重边？？
4. 这个错查了很久。你的 $ans$ 初始值是 $2147483647$，但是 $dis$ 数组初始值是`memset`下的 $63$。前者肯定比后者大，那么即使两个点之间没有连边，也会强制连起来。我的做法是把所有初始化改成了0x3f3f3f3f。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int cost[5005][5005];
int dis[5005];
int n,m;
bool vis[5005];
int ans=0;
void prim(){
dis[1]=0;
vis[1]=1;//4 对1的特殊vis处理
for(int i=2;i<=n;i++){
dis[i]=cost[1][i];
}
for(int i=1;i<n;i++){
int minp=0x3f3f3f3f,mj=-1;//3.0x3f统一
for(int j=2;j<=n;j++){
if(minp>dis[j]&&!vis[j]){
minp=dis[j];
mj=j;
}
}
if(minp==0x3f3f3f3f){
cout<<"orz";
exit(0);
}
// cout<<minp<<endl;
ans+=minp;
vis[mj]=true;
for(int j=2;j<=n;j++){
if(dis[j]>cost[mj][j]){//1.vis不必要，更新过程建议重学prim捏
dis[j]=cost[mj][j];
}
}
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
memset(cost,0x3f3f3f3f,sizeof(cost));
memset(dis,0x3f3f3f3f,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
cost[x][y]=cost[y][x]=min(cost[x][y],z);//2 重边
}
for(int i=1;i<=n;i++){
cost[i][i]=0;
}
prim();
cout<<ans;
return 0;
}
```
by xs_siqi @ 2022-09-28 23:50:45
@[xs_siqi](/user/401088)
1.更新判vis对结果没影响，建议~~您也去重学Prim~~
2.初始的1不需要vis[1]=true也是同理。证明使用构造方式+反证法+贪心解决。
3.~~至少这个算法对于同一输入多次运行只会输出一个答案，这点比rand“好”~~
@[wu13115899522](/user/442963)
1.memset初始化63只有10亿左右，显然小于2147483647，必然更新，下次开到1e9就可以了。（警示后人）
2.最小值一定是最后一次更新的吗？建议打程序前先激活你的大脑。
3.邻接矩阵不用min，题目保证两点只有一条边吗？
4.你wbh，Prim模板都不会打，你怎么学，噢？
@[wzxj](/user/451100)
1.不要五十步笑百步，你也不会打Prim；
2.其实Kruskal的最坏复杂度会比Prim高，所以还是建议去学Prim。
by J2a0m0e8s @ 2022-09-29 17:44:00
az，没认真看
Prim的最小值是到连通块的最小值，不是到起点，这点与Dijkstra不同。@[wu13115899522](/user/442963)
by J2a0m0e8s @ 2022-09-29 19:50:25
@[J2a0m0e8s](/user/437368) 我没有取笑他啊？？？我不是说我也不会吗？？？
by Xjin @ 2022-09-29 21:05:10
@[J2a0m0e8s](/user/437368) vis貌似的确是判不判无所谓。
vis1没标记是因为数据比较水。
by xs_siqi @ 2022-09-29 21:20:22