Uva 10765 - Doves and bombs

  1  /*
  2  Problem link
  3  Type: Graph - Find articulation points
  4  Algorithm:

UVA 10092 - The Problem with the Problem Setter

  1  /*
  2  Problem link
  3  Type: Graph - Maximum Flow
  4  Algorithm:

UVa 11747 - Heavy Cycle Edges

  1  /*
  2  Problem type: Graph - MST
  3  Algorithm: Find the Minimum Spanning Tree (MST) (using Kruskal,
  4      Prim) and print out all the edges which are not included in the MST.
  5  */

uva 10171 - Meeting Prof. Miguel...

  1  /*
  2  Problem link
  3  Type: Graph - Floyd
  4  Algorithm:

uva 572 - Oil Deposits

 1  /*
 2  Problem link
 3  Type: Graph
 4  Algorithm: DFS
 5  */

uva 11733 - Airports

 1 /*
 2  Problem link
 3  Type: Graph
 4  Algorithm:
 5      Kruskal, stop when the number of edge selected is equal to n-1 or the price of the edge
 6      equal to the cost to build an airport.
 7  */

uva 216 - Getting in Line

  1 /*
  2  Problem link
  3  Type: DP - TSP
  4  Algorithm: Brute force, back-tracking
  5  */

uva 469 - Wetlands of Florida

/*
Problem link
Type: Graph
Algorithm: BFS/DFS
*/

uva 571 - Jugs

  1  /*
  2  Problem link
  3  Type: Graph - DP
  4  Algorithm: BFS
  5  */

uva 186 - Trip Routing

  1  /*
  2  Problem link
  3  Type: Graph
  4  Algorithm: Floyd
  5  */

uva 10009 - All Roads Lead Where?

  1 /*
  2  Problem link
  3  Type: Graph
  4  Algorithm: BFS
  5  */

uva 10278 - Fire Station

  1 /*
  2  Problem link
  3  Type: Graph - Single source shortest path
  4  Algorithm:
  5      First run Floyd (or Dijkstra to every vertex n), for each vertex
  6      find the distance to the nearest station, get the max of those nearest station.
  7  
  8      For the vertex which is not a station, place a station there and run Dijkstra
  9      for that vertex. Recalculate the distance to the nearest station for each vertex
 10      by the distance array from the Dijkstra and update the for the "better max".
 11  */

uva 1208 - Oreon

  1  /*
  2  Problem link
  3  Type: Graph
  4  Algorithm: MST
  5  */

uva 908 - Re-connecting Computer Sites

 1  /*
 2  Problem link
 3  Type: Graph
 4  Algorithm: MST
 5  */

uva 11710 - Expensive subway

/*

Problem link

Type: Graph

Algorithm: Minimum spanning tree

uva 821 - Page Hopping

 1 /*
 2  Problem link
 3  Type: Graph
 4  Algorithm:
 5      Use floyd to find all pair shortest path, sum them up, divide to the number of pair
 6      I use the map to mark for the vertex in the input.
 7  */

uva 423 - MPI Maelstrom

 1 /*
 2  Problem link
 3  Type: Graph
 4  Algorithm:
 5      Use Floyd or Dijkstra to find the shortest path from 1 to n-1 others nodes.
 6      Find the max of the shortest path from 1 to n-1 others nodes.
 7  */

uva 352 - The Seasonal War

/*

Problem link

Type: Graph, flood fill

*/

 1  #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <cstdlib>
 6  using namespace std;

uva 11631 - Dark roads

/*
Problem link
Type: Graph
Algorithm: Kruskal, minimum spanning tree, using priority queue
*/
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <fstream>
using namespace std;
const int maxn = 200010;

uva 247 - Calling Circles

/*

Problem link
Type: Graph, DFS, Strongly connected components
Algorithm: Tarjan
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 50;