POJ 1639 Picnic Planning minimum spanning tree

2010-05-21  来源:本站原创  分类:Tech  人气:218 

/ *
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;
}
相关文章
  • POJ 1639 Picnic Planning minimum spanning tree 2010-05-21

    / * 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

  • POJ 1679 The Unique MST [Uniqueness of the minimum spanning tree determination] 2010-05-21

    / * <1> requirement: requirement of solving the problem is given a free map to the interchange to determine the minimum spanning tree MST of this graph is not the only, if only print the minimum, if not only to the tips <2> Analysis: The Krusk

  • Pliem algorithm to solve the minimum spanning tree graph 2010-06-29

    /*************************************** title: Pliem algorithm for graphs minimum spanning tree author: jay chang date: 2009.7.12 ****************************************/ #include<iostream> using namespace std; #define MAX 9999 #define MAXSIZE 99

  • Classical algorithm for minimum spanning tree Kruscal 2010-08-29

    Of the article: ktyanny Source: ktyanny reproduced please specify, thank you. Fled yesterday saying ktyanny day course, catching up and check set of knowledge, is to write a very, very classic of Kruscal minimum spanning tree. Get up at 9 o'clock thi

  • The Prim minimum spanning tree algorithm 2010-10-16

    Prim algorithm for the simple version of Java //Prim Algorithm for minimum spanning tree, use the Java A simple implementation of language // Figure adjacency matrix storage import java.util.*; public class PrimMST { private static int MAX = Integer.

  • Minimum Spanning Tree - Prim and Kruskal (greedy) 2011-01-07

    Between n cities in the laying of fiber optic cable, the high cost of laying fiber optic cable and fiber optic cable in various cities the cost of laying different. If the design goal is to make it n between any two cities, the city can be direct or

  • Prim and kruskal classical minimum spanning tree algorithm analysis - Comparison - Summary 2010-10-02

    Example Farmer John was elected mayor of their town! One of his campaign promises was to bring internet connectivity to all of the farm. Of course, he needs your help. John has been arranged to his farm a high speed connection, he wanted to share thi

  • Dtree + Jquery dynamic spanning tree node. 2009-05-23

    1. Let's introduce. Dtree usage. (I am quoting a previous article I have collected. Still relatively detailed provenance can not remember La. ). The article the following examples of usage will be included dtree. Dtree directory tree summary 1: Funct

  • Example spanning tree without recursive 2010-05-27

    It is used for Spanning Tree class, suitable for CLC Cai Yong's is a self-growth approach, and List of the elements is the An from small to large for Guo Shun Xu sort of (Zhege O'clock in the query is very easy to implement, Jiashang order by [id] ca

  • Java spanning tree root to a leaf node from all paths 2010-06-28

    /** * The algorithm uses a recursive manner, using depth-first traversal of the tree node , Record has been saved in traversing the node stack . * When it comes to leaf nodes, the output at this point all of the elements in the stack , That is, to th

  • Data spanning tree json extjs loading 2010-10-18

    Use ExtJS2, to JSON (JavaScript Object Notation) TreeLoader asynchronous read data, construct an asynchronous load of the tree. 1. Download ExtJS2, Address: http://www.extjs.com/ Download the Ext JS 2.1 SDK: ext-2.1.zip. examples folder is the ExtJS

  • dtree and jquery dynamic spanning tree 2010-10-19

    http://www.cnblogs.com/skyme/archive/2010/10/19/1855909.html

  • PKU Online Judge POJ classification of the most widely circulated, and hope will cut the (transfer) 2010-12-16

    Transfer from http://bbs.pediy.com/showthread.php?t=123253 Classification of multiple versions of the POJ The most widely circulated a Category: Early: One. Basic algorithm: (1) enumeration. (Poj1753, poj2965) (2) greedy (poj1328, poj2109, poj2586) (

  • [Change] poj title order 2010-07-18

    OJ on some of the water problem (can be used to train hand and increased self-confidence) (Poj3299, poj2159, poj2739, poj1083, poj2262, poj1503, poj3006, poj2255, poj3094) Early: 1. The basic algorithm: (1) enumeration. (Poj1753, poj2965) (2) greedy

  • POJ 題目分類 2012-09-26

    简单题 1000A+B Problem 1001Exponentiation 1003 Hangover 1004 Financial Management 1005 I Think I Need a Houseboat 1005 Biorhythms 1007 DNA Sorting 1013 Counterfeit Dollar 1014 Dividing 1032 Parliament 1045 Bode Plot 1119 Start Up the Startup 1131 Octal

  • The basis of software testing 2010-05-26

    <br /> Based software testing software testing foundation (basic skills test required) Software development and testing processes (RUP, MSF) Beta test process management division of planning, design, implementation, reporting, document preparation s

  • Algorithm review reprint 2010-06-03

    Phase I: the classical training algorithm used, each of the following algorithm to me marked from 10 to 20 times, while streamlining their own code, Too common, so do not think when I got to write 10-15 minutes, slapping, or even turn off the monitor

  • [Change] How should master data structure. Commonly used algorithm 2010-07-05

    How should master data structure, commonly used algorithm Can not fully remember so many algorithms. Commonly used algorithms, can be written to take over is not commonly used, picked up the book, and looked for 10 minutes, you can understand the alg

  • And check collection 2010-10-02

    Author of the article: Slyar Source: Slyar Home ( www.slyar.com ) reprint please specify, thank you. Equivalence relations and equivalence classes From the mathematical point of view, equivalence class is an object (or members) of the collection, in

  • [Transfer] learning algorithm of the Road 2010-10-08

    Learning algorithm of the Road Phase I: the classical training algorithm used, each of the following algorithm to me marked with ten to twenty times, while streamlining their own code, Too often, so when you do not want to be trained to write ,10-15