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; // 边数,加边前赋值为0void 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-1for (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++){// updatefor (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 resultfor (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;
}