Staonův svět - Odtrhávání vrcholů

Tak a mám tady své řešení dalšího domácího úkolu. Nějak se s nimi poslední dobou roztrh pytel.

Zadání

Zadání je přesně zkopírované z http://atrey.karlin.mff.cuni.cz/~bys­tron/cviceni/index.html

Je dán orientovaný graf. Ke každému vrcholu tohoto grafu je znám čas v sekundách, za jakou dobu trvá odebrání tohoto vrcholu z grafu (včetně incidentních hran). Odebrat z grafu lze jen ten vrchol, z něhož nevede žádná hrana. Na sobě nezávislé vrcholy je možno odebírat paralelně.

Vašim úkolem je napsat program, který pro daný graf a daný vrchol odpoví, za jaký minimální čas lze tento vrchol z grafu odebrat. Pokud daný vrchol z grafu žádným postupem odebrat nelze, vypište číslo –1.

Formát vstupu

Na prvním řádku je počet vrcholů N, mezera, počet hran M, mezera a číslo vrcholu, který chceme odebrat. Vrcholy jsou číslováný přirozenými čísly 1, 2,…, N.

Pak následuje N řádků, na každém jedno přirozené číslo. Na i-tém z těchto N řádků je čas v sekundách, za jaký lze i-tý vrchol z grafu odebrat, pokud by z něj nevedly hrany.

Pak následuje M řádků s popisem orientovaných hran (odkud mezera kam).

Formát výstupu

Na výstup vypište jen jedno číslo udávající minimální čas v sekundách, za jaký lze zvolený vrchol odebrat, případně –1, pokud tento vrchol odebrat po konečném počtu kroků nelze.

  1. #include <stdio.h>
  2.  
  3. class ONode;
  4.  
  5. class OEdge {
  6.   private:
  7.     /* -- datove polozlky hrany */
  8.     int weight;                /* -- vaha hrany */
  9.  
  10.     /* -- informace o spojeni grafu */
  11.     ONode * parent, * child;   /* -- ukazatele na pocatecni a koncovy uzel
  12.                                      hrany */
  13.   public:
  14.     OEdge(ONode * parent, ONode * child, int weight = 0);
  15.     int getWeight();
  16.  
  17.     int getTime();
  18. };
  19.  
  20. class ONode {
  21.   private:
  22.     /* -- datove polozky vrcholu */
  23.     int id;     /* -- cislo uzlu */
  24.     int weight;   /* -- doba potrebna pro odtrzeni */
  25.  
  26.     /* -- seznam hran vedoucich z tohoto uzlu */
  27.     struct OEdgeItem {
  28.       OEdge * edge;
  29.       OEdgeItem * next;
  30.     };
  31.     OEdgeItem * items;
  32.  
  33.     /* -- pomocna data pro prochazeni do hloubky */
  34.     int cumulative_w;       /* -- doba potrebna na odtrzeni vcetne potomku */
  35.     /* -- stav uzlu pri prochazeni */
  36.     enum {OFRESH, OOPEN, OCLOSED} dfs_state;
  37.   public:
  38.     ONode(int id, int weight = 0);
  39.     ~ONode();
  40.  
  41.     int getWeight();
  42.     /* -- prida novou hranu z tohoto uzlu do zadaneho */
  43.     void addEdge(ONode * child, int e_weight = 0);
  44.  
  45.     /* -- vrati cas potrebny pro odtrzeni tohoto uzlu.
  46.           Vrati -1, pokud jsem se vratil ve smycce. */
  47.     int getTime();
  48. };
  49.  
  50. /*
  51. =====================================================
  52.       Hrana grafu
  53. =====================================================
  54. */
  55. OEdge::OEdge(ONode * parent, ONode * child, int weight) {
  56.   this -> parent = parent;
  57.   this -> child = child;
  58.   this -> weight = weight;
  59. }
  60.  
  61. int OEdge::getWeight() {
  62.   return this -> weight;
  63. }
  64.  
  65. int OEdge::getTime() {
  66.   return child -> getTime();
  67. }
  68.  
  69. /*
  70. =====================================================
  71.       Vrchol grafu
  72. =====================================================
  73. */
  74. ONode::ONode(int id, int weight) {
  75.   this -> id = id;
  76.   this -> weight = weight;
  77.  
  78.   items = 0;
  79.   cumulative_w = 0;
  80.   dfs_state = OFRESH;
  81. }
  82.  
  83. ONode::~ONode() {
  84.   OEdgeItem * item;
  85.  
  86.   while(items) {
  87.     item = items;
  88.     items = items -> next;
  89.     delete item -> edge;
  90.     delete item;
  91.   }
  92. }
  93.  
  94. int ONode::getWeight() {
  95.   return this -> weight;
  96. }
  97.  
  98. void ONode::addEdge(ONode * child, int e_weight) {
  99.   OEdge * edge;
  100.   OEdgeItem * item;
  101.  
  102.   /* -- vyrobim hranu */
  103.   edge = new OEdge(this, child, e_weight);
  104.   /* -- zaradim ji do seznamu */
  105.   item = new OEdgeItem();
  106.   item -> edge = edge;
  107.   item -> next = items;
  108.   items = item;
  109. }
  110.  
  111. int ONode::getTime() {
  112.   int max_time, child_time;
  113.   OEdgeItem * item;
  114.  
  115.   /* -- pokud je uzel otevreny, tak vratim chybu (prosel
  116.         jsem cyklem) */
  117.   if(dfs_state == OOPEN) return -1;
  118.  
  119.   if(dfs_state == OFRESH) {
  120.     /* -- uzel je neotevreny, zpracuji ho */
  121.     dfs_state = OOPEN;
  122.  
  123.     /* -- od vsech potomku ziskam jejich cas odtrzeni a najdu max */
  124.     max_time = 0;
  125.     item = items;
  126.     while(item) {
  127.       child_time = item -> edge -> getTime();
  128.       if(child_time < 0) return -1;    /* -- nasel jsem cyklus, hned koncim */
  129.       if(child_time > max_time) max_time = child_time;
  130.  
  131.       item = item -> next;
  132.     }
  133.     cumulative_w = max_time + weight;
  134.  
  135.     /* -- uzel uzavru */
  136.     dfs_state = OCLOSED;
  137.   }
  138.   return cumulative_w;
  139. }
  140.  
  141. /*
  142. =====================================================
  143.       Cely graf
  144. =====================================================
  145. */
  146. class OGraph {
  147.   private:
  148.     ONode ** nodes;     /* -- pole uzlu */
  149.     int node_count;     /* -- pocet uzlu */
  150.     int edge_count;     /* -- pocet hran */
  151.     int start_node;     /* -- pocatecni uzel */
  152.  
  153.     /* -- pomocna. Slouzi k uchovani skuteneho poctu
  154.           nactenych hran - pri chybe se pak v destruktoru uvolni
  155.           opravdu jen to, co se nacetlo */
  156.     int read_edges;
  157.   public:
  158.     OGraph();
  159.     ~OGraph();
  160.     /* -- nacte graf ze zadaneho souboru Vraci false, pokus se
  161.           nepovedlo. */
  162.     bool readGraph(FILE * file);
  163.     bool readGraph(const char * filename);
  164.  
  165.     /* -- pro zadany uzel najde cas potrebny pro jeho odtrzeni.
  166.           Pokud neni mozne uzel odtrhnout, vraci -1 */
  167.     int getTime();
  168. };
  169.  
  170. OGraph::OGraph() {
  171.   nodes = 0;
  172.   node_count = 0;
  173.   edge_count = 0;
  174.   start_node = 0;
  175.  
  176.   read_edges = 0;
  177. }
  178.  
  179. OGraph::~OGraph() {
  180.   int i;
  181.  
  182.   if(node_count > 0 && nodes) {
  183.     for(i = 0; i < read_edges; ++ i)
  184.       delete nodes[i];
  185.     delete [] nodes;
  186.   }
  187. }
  188.  
  189. bool OGraph::readGraph(FILE * file) {
  190.   int info;
  191.   int i;
  192.   int n1, n2;
  193.   int weight;
  194.  
  195.   /* -- prectu si pocet uzlu, hran a pocatecni uzel */
  196.   info = fscanf(file, "%d %d %d\n", & node_count, & edge_count, & start_node);
  197.   if(info == EOF) return false;
  198.  
  199.   /* -- test, zda cisla davaj smysl */
  200.   if(node_count < 0) return false;
  201.   if(node_count == 0) return true;   /* -- prazdny graf */
  202.   if(start_node <= 0 || start_node > node_count) return false;
  203.   -- start_node;
  204.  
  205.   /* -- naalokuji si pamet */
  206.   nodes = new (ONode *)[node_count];
  207.  
  208.   /* -- pro kazdy uzel si prectu jeho vahu a vyrobim uzel */
  209.   for(i = 0; i < node_count; ++ i) {
  210.     info = fscanf(file, "%d\n", & weight);
  211.     if(info == EOF) return false;
  212.  
  213.     nodes[i] = new ONode(i, weight);
  214.     ++ read_edges;
  215.   }
  216.  
  217.   /* -- prectu seznam hran */
  218.   for(i = 0; i < edge_count; ++ i) {
  219.     info = fscanf(file, "%d %d\n", & n1, & n2);
  220.     if(info == EOF || n1 <= 0 || n2 <= 0 || n1 > node_count || n2 > node_count)
  221.       return false;
  222.  
  223.     nodes[n1 - 1] -> addEdge(nodes[n2 - 1]);
  224.   }
  225.  
  226.   return true;
  227. }
  228.  
  229. bool OGraph::readGraph(const char * filename) {
  230.   FILE * file;
  231.   bool retval;
  232.  
  233.   file = fopen(filename, "r");
  234.   if(file == NULL) return false;
  235.  
  236.   retval = readGraph(file);
  237.  
  238.   fclose(file);
  239.  
  240.   return retval;
  241. }
  242.  
  243. /* -- pro zadany uzel najde cas potrebny pro jeho odtrzeni.
  244.       Pokud neni mozne uzel odtrhnout, vraci -1 */
  245. int OGraph::getTime() {
  246.   if(node_count <= 0) return 0;   /* -- prazdny graf */
  247.   return nodes[start_node] -> getTime();
  248. }
  249.  
  250. /*
  251. =====================================================
  252.       MAIN
  253. =====================================================
  254. */
  255. int main(int argc, char * argv[]) {
  256.   OGraph * graph;
  257.   int time;
  258.  
  259.   graph = new OGraph();
  260.  
  261.   /* -- nactu data */
  262.   if(graph -> readGraph("data2.dta")) {
  263.     time = graph -> getTime();
  264.     printf("Cas je: %d\n", time);
  265.   }
  266.   else {
  267.     printf("Chyba pri cteni grafu\n");
  268.   }
  269.  
  270.   delete graph;
  271.  
  272.   return 0;
  273. }

V principu pro tuto úlohu je potřeba najít topologické uspořádání grafu. Na to jsou dva algoritmy:

  1. seřadit uzly v pořadí, v jakém byly uzavírány při prohledávání do hloubky,
  2. postupně odtrhávat kořeny nebo listy (jedno, druhé, nebo oboje).

Zvolil jsem algoritmus prohledávání do hloubky, kdy při uzavírání uzlu dávám dohromady výsledky z potomků.

Staon | 9.4.2006 Ne 16:39 | <<< trvalý odkaz >>> | tisk | 3 komentáře

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
IQ koně
dejwy 9.4.2006 Ne 19:48

Tak to už je peklo, tady nerozumím vůbec ani tomu zadání. Ještě, že mám už vejšku (nikoliv MFF) za sebou.

[2] reaguj
Staon mejl web 9.4.2006 Ne 19:58

[1] dejwy : to je tím, že v tom hledáš něco složitého ;) Všichni mají pocit, že Matfy implikuje nějaké naprosté šílenosti, ale nezapomeň, že jsem ve druhém semestru.

V principu jde úlohu typu „potřebuji něco vyrobit, ale pro to potřebuji n dalších věcí, ale pro výrobu těch n věcí potřebuji dalších m věcí atd.“ A ty se snažíš zjistit, za jak dlouho jsi schopný danou věc vyrobit se všemi závislostmi.

[3] reaguj
Pekné
Peter Piják mejl web 9.4.2006 Ne 23:31

Tak som potešil, keď som uvidel uvidel, že si tu dal článok o úlohe, ktorú musím aj ja do 2 týždňov dáko zmáknuť, veriac, že nájdem dáku dobrú inšpiráciu. Bohužial po kliknutí prišlo malé vytriezvenie v podobe céčka. Keby som tam nevidel pre mňa zatiaľ v céčku neznáme neviem-čo ako „class, public“, tak by som si to aj prečítal. Tak si aspoň zas raz popointrujem v pascale. Ale inak to vyzerá byť fakt pekné.

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Autor stránek Staonův svět se jmenuje?
Odpověd: Staon Cornelius Latipus

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).