Prim算法模板

Prim虽然为最小生成树算法之一却没有kruskal使用广泛(紫书居然还跳过了),但是有个别毒瘤题还是会针对kruskal搞新闻的,比如超级稠密图,这时Prim的优势就出现了,比如这道题

洛谷P1265 公路修建

Prim算法和dijkstra算法十分相似,直接上板子了

typedef std::pair<int, int>PII;
std::set<PII, std::less<PII> >min_heap;
bool vis[MAXN];
int dis[MAXN];
const int INF = 0x3F3F3F3F;
inline int Prim(int n) {
    int ans = 0;
    min_heap.insert(PII(0, 1));
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
    }
    dis[1] = 0;
    for (int i = 1; i <= n; ++i) {
        std::set<PII>::iterator iter = min_heap.begin();
        ans += iter->first;
        int u = iter->second;
        min_heap.erase(*iter);
        vis[u] = 1;
        for (Edge *it = head[u]; it; it = it->nextEdge) {
            int v = it->v, w = it->w;
            if (vis[v]) continue;
            if (dis[v] > w) {
                min_heap.erase(PII(dis[v], v));
                dis[v] = w;
                min_heap.insert(PII(dis[v], v));
            }
        }
    }
    return ans;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注