SHARE
TWEET

Untitled

a guest Sep 20th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/php
  2.  
  3. <?php
  4.  
  5. // Usage: cat [input file] | php [this file]
  6.  
  7. $networkSize = fscanf(STDIN, '%d')[0];
  8. $network = array_pad([], $networkSize, []);
  9. // At this point, the network is an array where keys are computers' ID and
  10. // values are empty arrays, which will be used to store the list of computers
  11. // the key is wired to
  12.  
  13. // Wiring the network
  14. for ($readLines = 0; $readLines < $networkSize - 1; $readLines++) {
  15.     $line = fscanf(STDIN, '%d %d');
  16.     array_push($network[$line[0]], $line[1]);
  17.     array_push($network[$line[1]], $line[0]);
  18. }
  19. // $network = array( [2],  [2],  [0 1 3],  [2 4 6],  [3 5],  [4],  [3] )
  20.  
  21. // foreach ($network as $index => $reach) {
  22. //     echo 'C' . $index . ' --> [ ' . implode('  ', $reach) . '  ]' . PHP_EOL;
  23. // } die();
  24.  
  25. $prof = array_pad([], $networkSize, 0);
  26.  
  27. // By butting the wire between $from and $to, returns the importance of $from
  28. // in its sub-network (found by recursively cutting more wires)
  29. // Also the importance of each computer in this sub-network is sored in $prof
  30. function find(int $from, int $to)
  31. {
  32.     global $network, $prof;
  33.     $importance = 1;
  34.     foreach ($network[$from] as $computerWithInternet) {
  35.         if ($computerWithInternet !== $to) {
  36.             $importance += find($computerWithInternet, $from);
  37.         }
  38.     }
  39.     $prof[$from] = $importance;
  40.     return $importance;
  41. };
  42.  
  43. // echo find(3, 2) . PHP_EOL;
  44. // foreach ($prof as $i => $x) {
  45. //     echo 'C' . $i . ' -> ' . $x . PHP_EOL;
  46. // } die();
  47.  
  48. // find(2, 3);
  49. // find(2, 5);
  50. // echo '[' . implode(', ', $prof) . ']' . PHP_EOL;
  51.  
  52.  
  53.  
  54. $mini = 1000000000;
  55.  
  56. function find2(int $from, int $to, int $wS)
  57. {
  58.     global $mini, $network, $prof;
  59.     $v = $w;
  60.     foreach ($network[$from] as $computer) {
  61.         if ($computer != $to) {
  62.             $v = max([$v, $prof[$computer]]);
  63.             find2($computer, $from, $w + $prof[$from] - $prof[$computer]);
  64.         }
  65.     }
  66.     $mini = min($mini, $v);
  67. }
  68.  
  69. find(0, -1);
  70. find2(0, -1, 0);
  71. // foreach ($prof as $i => $x) {
  72. //     echo 'C' . $i . ' -> ' . $x . PHP_EOL;
  73. // } die();
  74. echo $mini . PHP_EOL;
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90. // -------- DEBUG ------------------
  91.  
  92. function printNetwork(array $net)
  93. {
  94.     foreach ($net as $sub) {
  95.         echo implode(' - ', $sub) . PHP_EOL;
  96.     }
  97. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top