道路建设（prim算法）

在上一篇文章中我们用 kruskal算法 解决了这个问题 在这篇题解中 我们将用 prim算法来解决这一问题
首先我们写贴上从毛毛雨学姐那 贴来的 模板代码

再贴上本题的AC代码：

#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
#define pr pair<int,int>
const int maxn = 1e4 + 7;
typedef long long ll;
int head[105], to[maxn << 1], nex[maxn << 1], edge[maxn << 1], tot;
int C, n, m;
void add(int x, int y, int z) {
    to[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot++;
}
bool vis[maxn];
int prim() {
    priority_queue<pr, vector<pr>, greater<pr> > que;
    memset(vis, 0, sizeof(vis));
    for (int i = head[1]; i!=-1; i = nex[i])
        que.push(make_pair(edge[i], to[i]));
    vis[1] = true;
    int ans = 0;
    while (!que.empty() ) {
        int u = que.top().second, w = que.top().first;
        que.pop();
        if (vis[u]) continue;
        ans += w;
        vis[u] = true;
        for (int i = head[u]; i!=-1; i = nex[i]) {
            int v = to[i];
            if (vis[v]) continue;
            que.push(make_pair(edge[i], v));
        }
    }
    return ans;
}
int main()
{
    while (scanf("%d%d%d", &C, &m, &n) != EOF) {
        memset(head, -1, sizeof(head));
        tot = 0;
        for (int i = 1, u, v, w; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w); add(v, u, w);
        }
        int cost = prim();
        if ((cost > C)) printf("No\n");
        else printf("Yes\n");
    }
}

谢谢浏览