/ *

This title tune faster vomiting blood, and done really hard

This problem is mainly seeking minimum spanning tree, that is, given a tree, a node in the node with the maximum degree, then seek to meet such a condition the right of the tree and the final value and the minimum. This question is to do root Park limited degree, and then seek minimum spanning tree method for finding minimum spanning tree and the MST (minimum spanning tree closely related to) the main ideas in the following steps

1) to remove the root node from the graph

2) seek to remove the root node of the graph MST, pay attention to where the plan after the removal of the root may not be connected, so when the MST calculation should be calculated for each connected graph is where I chose to Kruscal algorithm + and inspection requirements set MST . After demand on each node connected in accordance with their respective component for coloring, and statistics the number of connected components

3) For each connected component, choose from the root node to the connected components in the node with the smallest weight edge to join the figure, assume that conn a connected component of the total need to add conn edges

4) from 1) 2) 3) steps that are a minimum spanning tree conn

5) Assume that subject qualified parking median kdeg, then the need to find kdeg - conn section starting from the root side, so cycle kdeg - conn times do the following:

a) Suppose the node k, edges [root, k, w] is not present in the tree (the right value of w), then by adding edges, if this tree will form a ring

b) assume that the ring is not directly connected with the root with the largest weight edge for the [from, to, weight]

Traverse all the tree nodes to find a maximum weight - w value of the edge, if the difference is greater than 0, will be this side [root, k] by adding trees and removal of side [from, to], if the difference value less than or equal 0 exit

This question is more frustrating feeling, ah, the code is mainly written in too many and too error prone to error two places

1) Calculate the MST when the calculation is wrong, the connected components of the color of different calculation confuse

2) the beginning edges of the array subscript set into 25, the result Runtime Error, then suddenly realized, 20 the maximum number of edges in the node is c (20, 2) far more than 25

It seems they still have to carefully point

6099743 bobten2008 1639 Accepted 252K 16MS C + + 5170B 2009-11-07 19:12:34

Over!

* /

#include <iostream> #include <algorithm> #include <string> #define MAX_N 25 using namespace std; // Record all node name struct node { string name; int con[MAX_N + 1]; // Records the original point of the current point and the other side of the right values between }nodes[MAX_N + 1]; int nodesn; // The number of nodes int kdeg; // Minimal number of struct edge // Used to record all the edges { int from, to, w; edge() { from = to = w = 0; } }edges[MAX_N * MAX_N + 1]; int edgen; int graph[MAX_N + 1][MAX_N + 1]; int color[MAX_N + 1]; int bfsq[MAX_N + 1][4], head, tail; bool v[MAX_N + 1]; void init() { memset(nodes, 0, sizeof(nodes)); memset(graph, 0, sizeof(graph)); nodesn = 0; edgen = 0; } int getIndex(const string &str) { for(int i = 0; i < nodesn; i++) if(nodes[i].name == str) return i; return -1; } // Insert the side [str1, str2, w] void processNodes(const string &str1, const string &str2, int w) { int index1 = getIndex(str1); if(index1 == -1) { index1 = nodesn++; nodes[index1].name = str1; } int index2 = getIndex(str2); if(index2 == -1) { index2 = nodesn++; nodes[index2].name = str2; } nodes[index1].con[index2] = w; nodes[index2].con[index1] = w; if(str1 != "Park" && str2 != "Park") { edges[edgen].from = index1; edges[edgen].to = index2; edges[edgen].w = w; edgen++; } } bool compare(const edge &e1, const edge &e2) { return e1.w <= e2.w; } // Find sets of related int sets[MAX_N + 1]; int find(int id) { if(sets[id] == id) return id; else return sets[id] = find(sets[id]); } void joint(int id1, int id2) { int sid1 = find(id1), sid2 = find(id2); if(sid1 == sid2) return; else sets[sid1] = sid2; } //Kruskal Algorithm,//return the number of Unicom component int solveMST(int root) { int e = 0, t, colorseq = 0; for(e = 0; e < nodesn; e++) { color[e] = 0; sets[e] = e; } for(e = 0; e < edgen; e++) { int from = edges[e].from; int to = edges[e].to; int w = edges[e].w; if(find(from) == find(to)) continue; else { joint(from, to); graph[from][to] = graph[to][from] = w; } } // Coloring for(e = 0; e < nodesn; e++) { if(color[e] || e == root) continue; int sid = find(e); color[e] = ++colorseq; for(t = e + 1; t < nodesn; t++) { if(t == root) continue; if(!color[t] && find(t) == sid) color[t] = color[e]; } } return colorseq; } // Statistical records from the root to the All points in the current tree path removed and root Direct-attached to the edge of the right to the top edge of the from to weight void getMaxEdgeInPath(int root, int maxarray[][3]) { head = tail = 1; memset(bfsq, 0, sizeof(bfsq)); memset(v, 0, sizeof(v)); bfsq[tail][0] = root; bfsq[tail][3] = 0; tail = tail % MAX_N + 1; v[root] = true; while(head != tail) { int curId = bfsq[head][0]; int from = bfsq[head][1]; int to = bfsq[head][2]; int curMax = bfsq[head][3]; head = head % MAX_N + 1; if(curId != root && from != root) { maxarray[curId][0] = from; maxarray[curId][1] = to; maxarray[curId][2] = curMax; } for(int toid = 0; toid < nodesn; toid++) { int curW; if(v[toid] || (curW = graph[curId][toid]) == 0) continue; v[toid] = true; int fromm = from, too = to, curMaxx = curMax; if(curW > curMax && curId != root) { fromm = curId; too = toid; curMaxx = curW; } bfsq[tail][0] = toid; bfsq[tail][1] = fromm; bfsq[tail][2] = too; bfsq[tail][3] = curMaxx; tail = tail % MAX_N + 1; } } } void solveKDegreeContraintTree() { // Records from the root to the All points in the current tree path removed and root Direct-attached to the edge of the right to the top edge of the from to weight int maxEdgeInPath[MAX_N + 1][3]; // Record point and root direct-attached bool conDirectToRoot[MAX_N + 1]; // Record root and each connected component of weight between the smallest and weights int minVal[MAX_N + 1][2]; memset(maxEdgeInPath, 0, sizeof(maxEdgeInPath)); memset(conDirectToRoot, 0, sizeof(conDirectToRoot)); memset(minVal, 0, sizeof(minVal)); int root = getIndex("Park"); int conn = solveMST(root); int i, c; // Select root and each connected component of weight between the smallest and weights for(i = 0; i < nodesn; i++) { int w; if(i == root || (w = nodes[root].con[i]) == 0) continue; int c = color[i]; if(minVal[c][1] == 0 || w < minVal[c][1]) { minVal[c][0] = i; minVal[c][1] = w; } } // Root and link conn A connected component of the rooms has a minimum weight of the edge for(c = 1; c <= conn; c++) { int to = minVal[c][0]; int w = minVal[c][1]; conDirectToRoot[to] = true; // Mark direct-attached graph[root][to] = graph[to][root] = w; // Even the edge } // Add extra kdeg-conn edges int time = kdeg - conn; while(time--) { memset(maxEdgeInPath, 0, sizeof(maxEdgeInPath)); getMaxEdgeInPath(root, maxEdgeInPath); int minVal, minNode, maxsubval = 0; // It loops through all of the nodes, look for the most weighted points difference minNode for(int k = 0; k < nodesn; k++) { int w; if((w = nodes[root].con[k]) == 0 || conDirectToRoot[k]) continue; if((maxEdgeInPath[k][2] - w) > maxsubval) { maxsubval = maxEdgeInPath[k][2] - w; minVal = w; minNode = k; } } // No longer able to optimize, then exit if(maxsubval == 0) break; // Replace the edge int f = maxEdgeInPath[minNode][0], t = maxEdgeInPath[minNode][1]; graph[f][t] = graph[t][f] = 0; graph[root][minNode] = graph[minNode][root] = minVal; } } int main() { int in, i, j, w; string from, to; init(); cin>>in; for(i = 0; i < in; i++) { cin>>from>>to>>w; processNodes(from, to, w); } cin>>kdeg; sort(edges, edges + edgen, compare); solveKDegreeContraintTree(); int res = 0; for(i = 0; i < nodesn; i++) for(j = i + 1; j < nodesn; j++) res += graph[i][j]; printf("Total miles driven: %d\n", res); return 0; }