ACM模版

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棵树的最小生成森林，也就是题目要求的解。