“任意两点之间 有且仅有一条简单路径时,返回将所有点连接的最小总费用”,即求MST(最小生成树)。
发现数据规模不超过1000,所以可以考虑到$O(n^2)$的算法。
$O(n^2)$算出任意两点的距离。然后用prim算最小生成树,同样$O(n^2)$。(这张图是稠密图,点数$n$远小于边数$n^2$,所以不用Kruskal)
const int inf=2100000000; int n; int fa[1007],mincost[1007]; int d[1007][1007]; int abs(int temp){ return temp>0?temp:(0-temp); } int find(int a){ return fa[a]==a?a:fa[a]=find(fa[a]); } class Solution { public: int minCostConnectPoints(vector<vector<int>>& points) { n=points.size(); for (int i=1;i<=n;i++) fa[i]=i,mincost[i]=inf; for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (i!=j) d[i+1][j+1]=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]),d[j+1][i+1]=d[i+1][j+1]; mincost[1]=0; int now=1,result=0,task=1; while (task<n){ int temp=inf,p=0; for (int i=1;i<=n;i++) if (now!=i&&mincost[i]){ if (d[now][i]<mincost[i]) mincost[i]=d[now][i]; if (temp>mincost[i]) temp=mincost[i],p=i; } task++,result+=temp,now=p,mincost[p]=0; } return result; } };