萌新疑惑,PrimT了3个点

P3366 【模板】最小生成树

P31pr @ 2020-10-23 21:28:36

```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; struct Edge { int to; int w; int next; }; struct Edge e[200005]; int p,topv[5001]; void insert(int to,int from,int w) { p++; e[p].to=to; e[p].w=w; e[p].next=topv[from]; topv[from]=p; } int min(int x,int y) { return x<y?x:y; } inline int read() { register int x=0,sign=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') sign=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*sign; } int main() { int n=read(),m=read(); int u,v,w; for(int i=1;i<=m;i++) { u=read(); v=read(); w=read(); insert(u,v,w); insert(v,u,w); } //prim int dis[n+1]; memset(dis,0x3f,sizeof(dis)); dis[1]=0; bool vis[n+1]={0}; vis[1]=1; int minw=0x7fffffff,cur=1,ans=0; for(int i=topv[1];i!=0;i=e[i].next) dis[e[i].to]=min(dis[e[i].to],e[i].w); for(int i=1;i<n;i++) { for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]<minw) { cur=j; minw=dis[j]; } ans+=minw; minw=0x7fffffff; vis[cur]=1; for(int j=topv[cur];j!=0;j=e[j].next) { int tv=e[j].to;//cout<<e[j].w<<" "; if( dis[tv]<minw && (!vis[tv]) ) dis[tv]=min(e[j].w,dis[tv]); } //cout<<minw<<" "<<cur<<endl; } printf("%d",ans); return 0; } ``` 人都傻了

by zhanghzqwq @ 2020-10-23 21:38:14

az,链式前向星的确开小了


by P31pr @ 2020-10-23 21:39:09

@Zephyr_ 草还真是,改一下就过了(没报RE就有点离谱)


by P31pr @ 2020-10-23 21:39:30

@Zephyr_ 蟹蟹!!


by konjacq @ 2020-10-23 21:39:52

orz卡常带师


by Prean @ 2020-10-23 21:41:16

@konjacq lz说了是手贱打错了,就别鞭尸了。。。


上一页 |