最小生成樹Prime算法（模闆）

我認為這個模闆好記。。。。。。

模闆代碼：

const int maxn = +;
const int INF = +;

struct gg{
    int first;
    int second;
};

vector<gg> g[maxn];
bool v[maxn];
int dis[maxn],N;

int prim() {
    memset(v, , sizeof(v));
    for(int i = ; i < N; i++) dis[i] = INF;
    dis[] = ;
    int ans = ;
    for(int i = ; i <= N; i++) {
        int mark = -;
        for(int j = ; j <= N; j++) if(!v[j])
            if(mark == -) mark = j;
        if(mark == -) break;
        v[mark] = ;
        ans += dis[mark];
        for(int j = ; j < g[mark].size(); j++) if(!v[g[mark][j].first]) {
            int x = g[mark][j].first;
            dis[x] = min(dis[x], g[mark][j].second);
        }
    }
    return ans;
}