UVa 10724

From Algorithmist
Jump to: navigation, search

10724 - Road Construction[edit]

Summary[edit]

Given is an undirected connected graph, which represents a city. Graph's vertices are points on 2D plane, numbered from 1 to n. Weight of an edge (when it exists) is equal to the distance between points.

Find a pair of vertices (u,v), such that:

  • u<v.
  • The edge (u,v) isn't present in the graph.
  • C_{{u,v}}=\sum _{{i=1}}^{n}\sum _{{j=i+1}}^{n}(d_{{i,j}}-d'_{{i,j}}) is maximized. d_{{i,j}} is the shortest distance between vertices i,j in the original graph. d'_{{i,j}} is the shortest distance between them, when the edge (u,v) is added to the graph.
  • C_{{u,v}}>1
  • When there are several pairs, satisfying above conditions, choose the one with smallest straight-line distance between vertices.
  • If there's still a tie, favor a pair with smaller u, and smaller v.

Explanation[edit]

A simple O(n^{4}) algorithm is enough to get accepted. First, use Floyd-Warshall to compute the shortest distances in the original graph, and then check all pairs (u,v). For each pair compute C_{{u,v}} from its definition.

The shortest path between vertices i and j after the edge (u,v) is added is equal to:

min(d_{{i,j}},\ d_{{i,u}}+w_{{u,v}}+d_{{v,j}},\ d_{{i,v}}+w_{{v,u}}+d_{{u,j}})

where w_{{u,v}} is the straight-line distance between vertices u and v.

Input[edit]

4 6
0 0 0 2 2 0 2 2
1 2 1 3 1 4
2 3 2 4
3 4
4 4
0 0 0 2 2 0 2 2
1 2 2 3 3 4 4 1
4 3
0 0 0 2 2 0 2 2
1 2 2 3 3 4
0 0

Output[edit]

No road required
1 3
1 3