Prim算法
/*
* Prim求MST
* 耗费矩阵cost[][]，初始化为INF，标号从0开始，0 ~ n－1
* 返回最小生成树的权值，返回-1表示原图不连通
*/
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];
// 修正cost（添加边）
void updata(int x, int y, int v)
{
cost[x - 1][y - 1] = v;
cost[y - 1][x - 1] = v;
return ;
}
int Prim(int cost[][MAXN], int n) // 0 ~ n - 1
{
int ans = 0;
memset(vis, false, sizeof(vis));
vis[0] = true;
for (int i = 1; i < n; i++)
{
lowc[i] = cost[0][i];
}
for (int i = 1; i < n; i++)
{
int minc = INF;
int p = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && minc > lowc[j])
{
minc = lowc[j];
p = j;
}
}
if (minc == INF)
{
return -1; // 原图不连通
}
ans += minc;
vis[p] = true;
for (int j = 0; j < n; j++)
{
if (!vis[j] && lowc[j] > cost[p][j])
{
lowc[j] = cost[p][j];
}
}
}
return ans;
}Kruskal算法
/*
* Kruskal算法求MST
* 对边操作，并排序
* 切记：初始化赋值问题（tol）
*/
const int MAXN = 110; // 最大点数
const int MAXM = 10000; // 最大边数
int F[MAXN]; // 并查集使用
struct Edge
{
int u; // 起点
int v; // 终点
int w; // 权值
} edge[MAXM]; // 存储边的信息
int tol; // 边数，加边前赋值为0
void addEdge(int u, int v, int w)
{
edge[tol].u = u;
edge[tol].v = v;
edge[tol++].w = w;
return ;
}
bool cmp(Edge a, Edge b)
{
// 排序函数，将边按照权值从小到大排序
return a.w < b.w;
}
int find(int x)
{
if (F[x] == x)
{
return x;
}
else
{
return F[x] = find(F[x]);
}
}
int Kruskal(int n) // 传入点数，返回最小生成树的权值，如果不连通则返回-1
{
for (int i = 0; i <= n; i++)
{
F[i] = i;
}
sort(edge, edge + tol, cmp);
int cnt = 0; // 计算加入的边数
int ans = 0;
for (int i = 0; i < tol; i++)
{
int u = edge[i].u;
int v = edge[i].v;
int w = edge[i].w;
int tOne = find(u);
int tTwo = find(v);
if (tOne != tTwo)
{
ans += w;
F[tOne] = tTwo;
cnt++;
}
if (cnt == n - 1)
{
break;
}
}
if (cnt < n - 1)
{
return -1; // 不连通
}
else
{
return ans;
}
}MST
/*
* Minimal Steiner Tree
* G(V, E), A是V的一个子集, 求至少包含A中所有点的最小子树.
* 时间复杂度:O(N^3+N*2^A*(2^A+N))
* INIT: d[][]距离矩阵; id[]置为集合A中点的标号;
* CALL: steiner(int n, int a);
* 给4个点对(a1,b1)...(a4,b4),
* 求min(sigma(dist[ai][bi])),其中重复的路段只能算一次.
* 这题要找出一个Steiner森林, 最后要对森林中树的个数进行枚举
*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
const typec V = 10010;
const typec A = 10;
int vis[V], id[A]; // id[]: A中点的标号
typec d[V][V], dp[1 << A][V]; // dp[i][v]: 点v到点集i的最短距离
void steiner(int n, int a)
{
int i, j, k, mx, mk = 0, top = (1 << a);
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (d[i][j] > d[i][k] + d[k][j])
{
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
for (i = 0; i < a; i++)
{
// vertex: 0 ~ n-1
for (j = 0; j < n; j++)
{
dp[1 << i][j] = d[j][id[i]];
}
}
for (i = 1; i < top; i++)
{
if (0 == (i & (i - 1)))
{
continue;
}
memset(vis, 0, sizeof(vis));
for (k = 0; k < n; k++) // init
{
for (dp[i][k] = inf, j = 1; j < i; j++)
{
if ((i | j) == i && dp[i][k] > dp[j][k] + dp[i - j][k])
{
dp[i][k] = dp[j][k] + dp[i - j][k];
}
}
}
for (j = 0; mx = inf, j < n; j++)
{
// update
for (k = 0; k < n; k++)
{
if (dp[i][k] <= mx && 0 == vis[k])
{
mx = dp[i][mk = k];
}
}
for (k = 0, vis[mk] = 1; k < n; k++)
{
if (dp[i][mk] > dp[i][k] + d[k][mk])
{
dp[i][mk] = dp[i][k] + d[k][mk];
}
}
}
}
return ;
}
int main(int argc, const char * argv[])
{
int n, a = 8;
int b, z, i, j, k, x = 0, y;
// TODO: read data;
steiner(n, a);
// enum to find the result
for (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++)
{
for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
{
for (k = 0; k < 8; k += 2)
{
if ((i >> k & 3) == j)
{
y += 3 << k, x = id[k];
}
}
}
}
// TODO: cout << b << endl;
return 0;
}最小生成森林问题（K颗树）
数据结构：并查集 算法：改进Kruskal 复杂度：O(mlongm)
根据Kruskal算法思想，图中的生成树在连接完第n - 1条边前，都是一个最小生成森林，每次贪心的选择两个不属于同一连通分量的树（如果连接一个连通分量，因为不会减少块数，那么就是不合算的）且用最“便宜”的边连起来，连接n - 1次后就形成了一棵MST，n - 2次就形成了一个两棵树的最小生成森林，n - 3、……、n - k次后，就形成了k棵树的最小生成森林，也就是题目要求的解。