我认为这个模板好记。。。。。。
模板代码:
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;
}