题目链接：点击打开链接
题目大意：略。
解题思路：最小生成树。
AC 代码1
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1005; int n,m; int dis[maxn], g[maxn][maxn]; void init() { mem(g,INF); mem(dis,0); } int prime() { int rs=0; for(int i=1;i<=n;i++) dis[i]=g[1][i]; // 从哪个点开始都可以 dis[1]=-1; // if(g[v][j]<dis[j]) 在下面比较的时候避免了有环 for(int i=1;i<n;i++) { int mi=INF,v=-1; for(int j=1;j<=n;j++) { if(dis[j]<mi && dis[j]!=-1) mi=dis[j], v=j; } if(v!=-1) { rs+=dis[v]; dis[v]=-1; for(int j=1;j<=n;j++) { if(g[v][j]<dis[j]) dis[j]=g[v][j]; } } } for(int i=1;i<=n;i++) if(dis[i]!=-1) return -1; return rs; } int main() { while(~scanf("%d%d",&n,&m)) { init(); int u,v,w; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); g[u][v]=g[v][u]=w; } printf("%d\n",prime()); } return 0; }
AC 代码2（简约版）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e3+10; int rs, cnt, n, g[maxn][maxn], dis[maxn], vis[maxn]; int prim(int s) { dis[s]=0; while(1) { int mi=INF; s=-1; for(int i=1;i<=n;i++) if(!vis[i] && mi>dis[i]) mi=dis[i], s=i; if(s==-1) return cnt; vis[s]=1, rs+=mi, cnt++; for(int i=1;i<=n;i++) if(!vis[i] && g[s][i]<dis[i]) dis[i]=g[s][i]; } } int main() { mem(dis,INF), mem(g,INF), mem(vis,0); int m,u,v,w; cnt=rs=0; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); g[u][v]=g[v][u]=w; } printf("%d\n",prim(1)==n?rs:-1); return 0; }
