本文共 3298 字，大约阅读时间需要 10 分钟。
#include #include #include #include #include #include using namespace std;int const oo = 100000000;int cost[103][103]; // 花费=边 int used[103][103]; // 表示这条边是否在生成树中 int father[103]; // 生成树中点的 int maxlen[103]; // 表示i点到根的路径上除了与根直接相连的边外，边权最大的边的边权。int vis[103]; // 标记 int d[103]; // 求最小生成树时的离最小生成树的代价 int AnsMst; // 当前m度生成树的代价 int N, degree, lim; // degree表示最小限度，lim表示限度值 int g[103][103]; // 生成树中的儿子关系，正向表。 map mat; void MST(int S) { // 求从S点开始的最小生成树 while (1) { int K = -1; for (int i = 1; i <= N; i++) { if (!vis[i] && d[i] != oo && (K == -1 || d[K] > d[i])) K = i; } if (K == -1) break; vis[K] = 1; AnsMst += d[K]; g[father[K]][++g[father[K]][0]] = K; // 记录儿子 if (d[K] != 0) maxlen[K] = max(maxlen[father[K]], d[K]); // 算边权最大的边 used[K][father[K]] = used[father[K]][K] = 1; // 标记边在生成树中 for (int i = 1; i <= N; i++) { if (!vis[i] && cost[K][i] < d[i]) { father[i] = K; d[i] = cost[K][i]; } } }}void Build() { for (int i = 1; i <= N; i++) father[i] = i; for (int i = 1; i <= N; i++) d[i] = oo; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) used[i][j] = 0; // 所有的边都在生成树外 for (int i = 1; i <= N; i++) g[i][0] = 0; // 儿子树全为0 for (int i = 1; i <= N; i++) vis[i] = 0; // 标记清空 vis[1] = 1; degree = 0; maxlen[1] = -oo; // 根的maxlen为-oo AnsMst = 0; // 开始时生成树的代价为0 while (1) { int K = -1; for (int i = 1; i <= N; i++) { if (!vis[i] && (K == -1 || cost[1][i] < cost[1][K])) K = i; // 找一条边权最小的和跟相连的点开始做最小生成树 } if (K == -1) break; father[K] = 1; // father 为 1 maxlen[K] = -oo; // maxlen[k]=-oo d[K] = 0; degree++; // 联通分支个数加1 AnsMst += cost[1][K]; // 生成树代价增加 MST(K); }}void Init(){ // 开始的输入处理 mat.clear(); mat["Park"] = 1; N = 1; int M; scanf("%d", &M); for (int i = 1; i <= 30; i++) { for (int j = 1; j <= 30; j++) cost[i][j] = oo; } while (M--) { string a, b; int c; cin >> a >> b >> c; int ida, idb; if (mat.find(a) == mat.end()) mat[a] = ++N, ida = N; else ida = mat[a]; if (mat.find(b) == mat.end()) mat[b] = ++N, idb = N; else idb = mat[b]; cost[ida][idb] = cost[idb][ida] = c; } scanf("%d", &lim);}void Dfs(int nod, int fa) { // 更新维护maxlen和生成树中的父子关系 father[nod] = fa; vis[nod]=1; if (fa == 1) maxlen[nod] = -oo; else maxlen[nod] = max(maxlen[fa], cost[nod][fa]); for (int i = 1; i <= g[nod][0]; i++) if (used[nod][g[nod][i]] && !vis[g[nod][i]]) Dfs(g[nod][i], nod);}void Solve() { if (degree > lim) cout << "Error" << endl; int ans = AnsMst; while (degree < lim) { degree++; int id = -1; int delta = oo; for (int i = 1; i <= N; i++) { // 找代价最小的进行扩张 if (cost[1][i] != oo && !used[1][i]) { if (id == -1) { id = i; delta = cost[1][i] - maxlen[i]; continue; } if (cost[1][i] - maxlen[i] < delta) { id = i; delta = cost[1][i] - maxlen[i]; } } } if (id == -1) break; AnsMst += delta; // 加上delta值 ans = min(ans, AnsMst); int Len = maxlen[id]; used[1][id] = used[id][1] = 1; // 表示边被加入到当前的生成树中 g[1][++g[1][0]] = id; // 表示根多了一个儿子 while (cost[id][father[id]] != Len) { // 找最大的边，并顺路维护儿子关系 int fa = father[id]; g[id][++g[id][0]] = fa; id = fa; } used[id][father[id]] = used[father[id]][id] = 0; // 标记边被删去 for (int i = 1; i <= N; i++) vis[i]=0; Dfs(1, 1); // 维护 } printf("Total miles driven: %d\n", ans);}int main() { Init(); Build(); Solve(); return 0;}
转载于:https://www.cnblogs.com/LUO257316/p/3257663.html