[UVA] 10724 - Road Construction
Problem G |
Road Construction |
Time Limit |
5 Seconds |
Bangladesh Government is seriously thinking about decreasing the intolerable traffic jam in Dhaka. They have tried lots of things to solve this problem. But all of you know while traveling in Dhaka, it is almost impossible to escape it L. The higher authority of Government has now realized the situation that they need different view and doings for this Herculean task. They come to you and as an expertise in computer science you give them a solution. The idea is simple, to construct new roads. But the problem is to ensure that the newly constructed road is properly utilized. And that will happen only if traveling cost is reduced for some routes. In that case traffic in those routes will automatically use the current road and thus will be distributed better in the network.
In this problem you will be given a map of Dhaka in terms of an undirected graph. Each node will denote a station and edge will represent a road. Nodes will be simple 2-D geometric points and the cost to travel a road is proportional to the Euclidian distance between two nodes. Now, you will suggest to construct one road temporarily. You have fixed the criterion to select the two nodes between which new road will be constructed.
· If there is a road between (u, v) then this pair will not be considered.
· Otherwise Cuv = Sum (PreCostij -CurCostij) where CurCostij is the shortest cost path from i to j if the road between (u, v) exists. And PreCostij is the shortest cost route before constructing the road between u and v.
· The (u, v) pair with maximum Cuv will be selected.
Input
Each test case starts with two positive integers N (≤ 50) and M (≤ 1225). In next few lines the coordinates (x, y)
of the nodes will be given. The value of each coordinate will be in the
range of -1000 to 1000. In next few lines the road description will be
given. Each road consists of two positive integers (u, v) where 1 ≤ u, v ≤ N. It means that there is a bidirectional road between u and v. It is guaranteed that the graph will be connected.
Input is terminated by N = M = 0. This case should not be processed.
Output
If new road construction helps the traffic condition then output will be a pair of nodes (u, v)
between which the new road will be constructed. If there are several
candidates then the shortest distant nodes will be eligible. If again
draw occurs then node pair whose indices are small will be the answer.
On the other hand if the road network is balanced (New road will not improve the traffic situation), print “No road required”. Note that, if Cuv is less or equal to 1.0 then the network will be considered balanced.
Sample Input |
Output for Sample Input |
4 6 |
No road required |
Member of Elite Problemsetters' Panel
Special thanks to Tahseen Mohammad
題目描述：
給定一個 2-D 平面圖，把點當作城市，用歐幾理得距離計算路程，而告訴你已經建造了哪幾條道路。
問如果再加增一條道路，能縮短點與點之間的距離，最大值為何？
題目解法：
首先，找到 all-pair 的最短路 O(n^3)，再來考慮要加入的那個道路。
因此窮舉加入的道路 O(n^2)，檢查該道路能縮短多少距離(加總)需要 O(n^2)
加入的道路為 (i, j), 點 i->j
檢查的思路(st, ed)：要不走這一條，或者走這一條，
走這一條的話，可能是由 st->i->j->ed or st->j->i->ed。
三者去最小的，看有沒有縮短。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
double g[55][55];
int used[55][55], x[55], y[55];
int main() {
int n, m;
int i, j, k, u, v, p, q;
while(scanf("%d %d", &n, &m) == 2 && n) {
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++)
g[i][j] = 1e+10, used[i][j] = 0;
g[i][i] = 0;
}
for(i = 0; i < n; i++)
scanf("%d %d", &x[i], &y[i]);
for(i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
u--, v--;
g[u][v] = g[v][u] = hypot(x[u]-x[v], y[u]-y[v]);
used[u][v] = used[v][u] = 1;
}
for(k = 0; k < n; k++)//Floyd-Warshall
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
double ret = 0;
int rx = -1, ry = -1;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(used[i][j]) continue;
double d = hypot(x[i]-x[j], y[i]-y[j]), Cuv = 0;
for(p = 0; p < n; p++)
for(q = p+1; q < n; q++)
Cuv += g[p][q] - min(g[p][q], min(g[p][i]+g[j][q]+d, g[p][j]+g[i][q]+d));
if(Cuv > 0 && Cuv > ret + 1e-10)
ret = Cuv, rx = i, ry = j;
}
}
if(ret > 1e-8)
printf("%d %d\n", rx+1, ry+1);
else
puts("No road required");
}
return 0;
}