Prim算法、Kruskal算法
前言
之前把Prim和Dijkstra给混了就没发，晚上花了十多分钟搞明白刷了几道题然后发哈哈哈哈（算是复习的其实）
一些注意点
- Prim和Dijkstra的区别
区别在于，Prim是算该点到已加入的点的集合的距离最小值（即cost[u][v]），而Dijkstra是算该点到源点的最小值（即cost[u][v] + d[u]） - 最小生成树的表述
最小生成树是使得图能连通，加边权值之和最小 的方案
由Kruskal算法可知，每次加边都选择尽量小的边加上去，因此最后得到的图也是 最大边尽量小的图
Constructing Roads - HDU - 1102
题意
给定邻接矩阵，矩阵中的数值代表边的权值，再给定q条已连接的边，现求使整幅图能连通所需的边权值之和最小值
思路
MST模板题
只需把q条已连接边的权值设为0再跑最小生成树即可
Prim做法：
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
typedef long long ll;
struct node{
int cost, u;
node(int pc, int pu): cost(pc), u(pu) {}
bool operator < (const node& b) const { return cost > b.cost; }
};
int G[N][N];
int mincost[N];
int used[N];
priority_queue<node> que;
inline void init(){
memset(mincost, 0x3f, sizeof(mincost));
memset(used, false, sizeof(used));
}
int prim(int n){
int ans = 0;
mincost[1] = 0;
que.push(node(0, 1));
while(!que.empty()){
int u = que.top().u;
int cost = que.top().cost;
que.pop();
if(used[u] || mincost[u] < cost) continue;
used[u] = true;
mincost[u] = cost;
ans += cost;
for(int v = 1; v <= n; v++){
if(u == v) continue;
if(!used[v] && mincost[v] > G[u][v]){
mincost[v] = G[u][v];
que.push(node(G[u][v], v));
}
}
}
return ans;
}
int main(){
int n;
while(~scanf("%d", &n)){
init();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &G[i][j]);
}
}
int q;
scanf("%d", &q);
while(q--){
int u, v;
scanf("%d%d", &u, &v);
G[u][v] = G[v][u] = 0;
}
printf("%d\n", prim(n));
}
}
Kruskal做法：
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
typedef long long ll;
struct edge{
int u, v, val;
edge() {}
edge(int pu, int pv, int pval): u(pu), v(pv), val(pval) {}
bool operator < (const edge& b) const{
return val < b.val;
}
};
int G[N][N];
int ft[N];
edge e[N*N*2];
int m;
inline void init(int n){
m = 0;
for(int i = 1; i <= n; i++) ft[i] = i;
}
int uffind(int x) { return x == ft[x] ? x : ft[x] = uffind(ft[x]); }
void ufuni(int x, int y){
int p = uffind(x), q = uffind(y);
if(p != q) ft[q] = p;
}
int Kruskal(int m){
int ans = 0;
sort(e, e + m);
for(int i = 0; i < m; i++){
int p = uffind(e[i].u), q = uffind(e[i].v);
if(p != q){
ans += e[i].val;
ufuni(p, q);
}
}
return ans;
}
int main(){
int n;
while(~scanf("%d", &n)){
init(n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &G[i][j]);
}
}
int q;
scanf("%d", &q);
while(q--){
int u, v;
scanf("%d%d", &u, &v);
G[u][v] = G[v][u] = 0;
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
e[m++] = edge(i, j, G[i][j]);
}
}
printf("%d\n", Kruskal(m));
}
}
Networking - POJ - 1287
题意
给定u,v,val，求MST
思路
MST模板题，只是这次用的是邻接链表
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
typedef long long ll;
struct node{
int cost, u;
node(int pc, int pu): cost(pc), u(pu) {}
bool operator < (const node& b) const { return cost > b.cost; }
};
struct edge{
int to, next, val;
};
edge e[N*N];
int tot;
int head[N];
int mincost[N];
int used[N];
priority_queue<node> que;
inline void init(){
tot = 0;
memset(head, -1, sizeof(head));
memset(mincost, 0x3f, sizeof(mincost));
memset(used, false, sizeof(used));
}
inline void addEdge(int u, int v, int val){
e[tot].to = v;
e[tot].val = val;
e[tot].next = head[u];
head[u] = tot++;
}
int prim(){
int ans = 0;
mincost[1] = 0;
que.push(node(0, 1));
while(!que.empty()){
int u = que.top().u;
int cost = que.top().cost;
que.pop();
if(used[u] || mincost[u] < cost) continue;
used[u] = true;
mincost[u] = cost;
ans += cost;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if(u == v) continue;
if(!used[v] && mincost[v] > e[i].val){
mincost[v] = e[i].val;
que.push(node(e[i].val, v));
}
}
}
return ans;
}
int main(){
int n, m;
while(scanf("%d", &n) && n){
init();
scanf("%d", &m);
while(m--){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
addEdge(u, v, val);
addEdge(v, u, val);
}
printf("%d\n", prim());
}
}
畅通工程再续 - HDU - 1875
思路
先算距离，然后把距离<10或者>1000的边权值设为inf再跑MST，最终如果有点的used = false那就说明整幅图没有连通，无法完成
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 505;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct node{
double cost;
int u;
node(double pc, int pu): cost(pc), u(pu) {}
bool operator < (const node& b) const { return cost > b.cost; }
};
double G[N][N];
double mincost[N];
int used[N];
int d[N][2];
priority_queue<node> que;
inline void init(){
for(int i = 0; i < N; i++) mincost[i] = inf;
memset(used, false, sizeof(used));
}
double prim(int n){
double ans = 0;
mincost[0] = 0;
que.push(node(0, 0));
while(!que.empty()){
int u = que.top().u;
double cost = que.top().cost;
que.pop();
if(used[u] || mincost[u] < cost) continue;
used[u] = true;
mincost[u] = cost;
ans += cost*100;
for(int v = 0; v < n; v++){
if(u == v || G[u][v] == inf) continue;
if(!used[v] && mincost[v] > G[u][v]){
mincost[v] = G[u][v];
que.push(node(G[u][v], v));
}
}
}
return ans;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
init();
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d%d", &d[i][0], &d[i][1]);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j){
G[i][j] = 0;
}else{
double dis = sqrt((d[i][0] - d[j][0])*(d[i][0] - d[j][0]) + (d[i][1] - d[j][1])*(d[i][1] - d[j][1]));
if(dis < 10 || dis > 1000) dis = (double)inf;
G[i][j] = G[j][i] = dis;
}
}
}
double ans = prim(n);
for(int i = 0; i < n; i++){
if(!used[i]){
ans = -1;
break;
}
}
if(ans == -1){
puts("oh!");
}else{
printf("%.1f\n", ans);
}
}
}
Truck History - POJ - 1789
题意
（简化版，英文原题十分难懂T^T）
给定一组7个字符的字符串，字符串两两之间的距离为对应位置上不同字母数之和，最开始只有一个字符串，后来的字符串由其他字符串派生出来，派生的代价为两个字符串的距离，现求得到所有字符串的代价之和最小值
思路
先算距离，然后跑MST
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2005;
typedef long long ll;
struct node{
int cost, u;
node(int pc, int pu): cost(pc), u(pu) {}
bool operator < (const node& b) const { return cost > b.cost; }
};
int G[N][N];
int mincost[N];
bool used[N];
char s[N][10];
priority_queue<node> que;
inline void init(){
memset(G[0], 0, sizeof(G));
memset(mincost, 0x3f, sizeof(mincost));
memset(used, false, sizeof(used));
}
int prim(int n){
int ans = 0;
mincost[0] = 0;
que.push(node(0, 0));
while(!que.empty()){
int u = que.top().u;
int cost = que.top().cost;
que.pop();
if(used[u] || mincost[u] < cost) continue;
used[u] = true;
mincost[u] = cost;
ans += cost;
for(int v = 0; v < n; v++){
if(u == v) continue;
if(!used[v] && mincost[v] > G[u][v]){
mincost[v] = G[u][v];
que.push(node(G[u][v], v));
}
}
}
return ans;
}
int main(){
int n;
while(~scanf("%d", &n) && n){
init();
for(int i = 0; i < n; i++) scanf("%s", s[i]);
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
for(int k = 0; k < 7; k++){
if(s[i][k] != s[j][k]){
G[i][j]++;
}
G[j][i] = G[i][j];
}
}
}
printf("The highest possible quality is 1/%d.\n", prim(n));
}
}
旅行 - SZUCPC 2017 Winter
思路
本题似乎只能用Kruskal，因为需要用并查集，另外询问次数很多因此需要离线打表
首先无疑是MST，因为价值取最大的那条路
然后用并查集动态维护每个连通块点的个数和美丽城市的个数，并动态计算出加入每一条边后答案点对的和
因为使用Kruskal，边值是升序排序的，因此最终可通过二分寻找最后一个不超过承受能力的答案并输出
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5 + 15;
struct edge{
int u, v, val;
bool operator < (const edge& b) const { return val < b.val; }
};
int ft[N];
int f[N];
int s_sum[N], s_beauty[N];
bool beauty[N];
edge e[N];
void mInit(int n){
e[0].val = 0, f[0] = 0;
for(int i = 1; i <= n; i++){
ft[i] = i;
s_sum[i] = 1;
s_beauty[i] = beauty[i];
}
}
int mFind(int x){ return ft[x] == x ? x : ft[x] = mFind(ft[x]); }
void mUnique(int x, int y){
int p = mFind(x), q = mFind(y);
if(p != q){
ft[q] = p;
s_sum[p] += s_sum[q];
s_beauty[p] += s_beauty[q];
}
}
void Kruskal(int n){
sort(e + 1, e + 1 + n);
for(int i = 1; i <= n; i++){
int u = e[i].u, v = e[i].v;
f[i] = f[i - 1];
int p = mFind(u), q = mFind(v);
if(p != q){
f[i] += (s_sum[p] * s_beauty[q] + s_sum[q] * s_beauty[p]);
mUnique(u, v);
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
int m, n, q;
scanf("%d%d%d", &m, &n, &q);
for(int i = 1; i <= m; i++) scanf("%d", &beauty[i]);
for(int i = 1; i <= n; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].val);
mInit(m);
Kruskal(n);
for(int i = 1; i <= q; i++){
edge k;
scanf("%d", &k.val);
int pos = upper_bound(e + 1, e + 1 + n, k) - e - 1;
printf("%d\n", f[pos]);
}
}
}
