leetcode 1584.连接所有点的最小费用

  “任意两点之间 有且仅有一条简单路径时,返回将所有点连接的最小总费用”,即求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;
    }
};

 

上一篇:1007-3_4计算无限序列


下一篇:1007 素数对猜想 (20分) Java