首先因为这题是连通性问题求最值，考虑最小生成树是否可做，这题一个比较不同的地方是它每一个点有权值，我们考虑能否将点的权值转化成边权，因为如果能够转化成功，我们就可以很轻松的用最小生成树求解，我们可以建立一个新的虚拟节点，并将所有的点与这个点连一条边权为那些点点权的边，然后在新图中求最小生成树即可
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 100005 struct edge { int fr,to,cost; }e[maxn]; int n,tot,cnt,father[maxn],ans; bool cmp(edge a,edge b) { return a.cost<b.cost; } int getfather(int x) { if (x!=father[x]) x=getfather(father[x]); return father[x]; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { e[++tot].fr=0; e[tot].to=i; scanf("%d",&e[tot].cost); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { int a; scanf("%d",&a); if (a==0) continue; e[++tot].fr=i; e[tot].to=j; e[tot].cost=a; } sort(e+1,e+tot+1,cmp); for (int i=1;i<=n;i++) father[i]=i; for (int i=1;i<=tot;i++) { int x=e[i].fr; int y=e[i].to; x=getfather(x); y=getfather(y); if (x==y) continue; father[x]=y; ans+=e[i].cost; cnt++; if (cnt==n) break; } printf("%d\n",ans); return 0; }
