24h購物| | PChome| 登入
2012-06-05 07:31:47| 人氣719| 回應0 | 上一篇 | 下一篇

[ACM-ICPC] 5865 - Finding Bottleneck Shorstet Paths

推薦 0 收藏 0 轉貼0 訂閱站台

A sensor network consists of a set of n sensors s1, s2,..., sn. All the sensors are placed in a two dimensional plane and will never be moved again. Thus, each sensor si has a fixed coordinates (xi, yi).

A pair of sensors si and sj can communicate by sending messages. Suppose that si wants to send a message directly to sj, a fixed amount of electrical power pi, j is required at si. In real world situation, the value of pi, j depends on many factors. For simplicity we assume that the value of pi, j depends only on the distance between the communicating sensors. In this problem, we assume that

pi, j = (xi - xj)2 + (yi - yj)2.
Furthermore, we assume that only the sender needs to consume this amount of power in the communication.

Since the power stored in each sensor is a precious resource, sending message directly to the destination sensor may consume too much electrical power for a sensor. In this problem, we want to find an optimal path to send a message from si to sj such that the maximum power required by the sensors on the path is minimized.

More formally, let P be a valid path from si to sj. Let k1 = i, k2,..., kr = j be the sequence of the indexes of the sensors along the path P. Define the weight of P by

w(P) = $displaystyle max_{{1le i<r}}^{}${pki, ki+1}.
A path P is an optimal path from si to sj if its weight w(P) is minimized among all paths from si to sj.

Given a sensor network G, the sender si and the receiver sj, write a program to compute an optimal path from si to sj for sending a message.

Input 

An instance of the problem consists of

  1. the number of sensors n,
  2. the coordinates of the sensors (xi, yi), 1$ le$i$ le$n, and
  3. the source and the destination sensors si and ti.
These data are stored in $ lceil$n/20$ rceil$ + 2 lines in the input file.
  1. The first line is the integer n.
  2. The following $ lceil$n/20$ rceil$ lines are the n coordinates (xi, yi), 1$ le$i$ le$n. Each line contains at most 20 coordinates. Each coordinates is written in two numbers xi and yi, without the parentheses.
  3. The last line of an instance contains two integer i and j, indicating si is the sender and sj is the receiver.
In this problem, we assume that 1 < n < 1000, xi and yi are integers and 0$ le$xi, yi < 215.

Note that the test data file may contain more than one instances. The last instance is followed by a line containing a single `0'.

Output 

The output for each test case is an integer w which is the maximum power required along the optimal path from si to sj.

Sample Input 

4
0 0  1 9  8 2  10 10
1 4
5
0 0  8 2  3 4  8 7  10 10
1 5
0

Sample Output 

68
29

在一個 n*n 的連通圖, 求 st 到 ed 上的其中一條路徑, 路徑上的最大值最小
可以用 Dijkstra 或者是最小生成樹的想法去做, 這裡使用 Dijkstra

#include <iostream>
#include <cstdio>
#define oo 2147483647
using namespace std;

int Map[1000][1000];
int Max(int x, int y) {
    return x > y ? x : y;
}
int Min(int x, int y) {
    return x < y ? x : y;
}
int solve(int st, int ed, int n) {
    int i, j;
    int V[1000], Used[1000];
    for(i = 0; i < n; i++)
        V[i] = -oo, Used[i] = 0;
    V[st] = 0, Used[st] = 1;
    for(i = 0; i < n; i++) {
        int tn = st, next = oo;
        for(j = 0; j < n; j++)
            if(next > V[j] && V[j] != -oo && Used[j] == 0)
                next = V[j], tn = j;
        Used[tn] = 1;
        for(j = 0; j < n; j++) {
            if(V[j] != -oo)
                V[j] = Min(Max(V[tn], Map[tn][j]), V[j]);
            else
                V[j] = Max(V[tn], Map[tn][j]);
        }
    }
    return V[ed];
}
int main() {
    int n, X[1000], Y[1000], i, j;
    while(scanf("%d", &n) == 1 && n) {
        int st, ed;
        for(i = 0; i < n; i++)
            scanf("%d %d", &X[i], &Y[i]);
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                Map[i][j] = (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]);
        scanf("%d %d", &st, &ed);
        printf("%d\n", solve(st-1, ed-1, n));
    }
    return 0;
}

台長: Morris
人氣(719) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[ACM-ICPC] 5861 - Hidden Terminal Problem
此分類上一篇:[ACM-ICPC][模擬] 5867 - Finding Feasible Paths

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文