【POJ】Frogger

Problem here

Description

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. 
Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. 
To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence. 
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.

Input

The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.

Output

For each test case, print a line saying “Scenario #x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.

Sample Input

2 
0 0 
3 4

3 
17 4 
19 4 
18 5

0

Sample Output

Scenario #1 
Frog Distance = 5.000

Scenario #2 
Frog Distance = 1.414

Solution

#include <iostream>
#include <memory.h>
#include <math.h>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
#define INF 999999
using namespace std;

float map[201][201];
bool visit[201];
int n;
vector<pair<int, int> > coor;

float alg(pair<int, int> p1, pair<int, int> p2){
    float a = p1.first - p2.first;
    float b = p1.second - p2.second;
    float u = sqrt(pow(a, 2) + pow(b, 2));
    //cout << "\\\\" << u << endl;
    float ans = abs(u);
    return ans;
}

int main(){
    int cnt = 0;
    while(cin >> n){
        memset(map, INF, sizeof(map));
        memset(visit, false, sizeof(visit));
        if(n == 0)
            break;
        cnt++;
        for(int i = 1; i <= n; i++){
            int x, y;
            cin >> x >> y;
            coor.push_back(make_pair(x, y));
        }
        for(int i = 0; i < coor.size(); i++){
            for(int j = 0; j < coor.size(); j++){
                map[i+1][j+1] = map[j+1][i+1] = alg(coor[i], coor[j]);
            }
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                    map[j][k] = min(map[j][k], max(map[j][i], map[i][k]));

        float min = INF;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(map[i][j] < min && map[i][j] != 0)
                    min = map[i][j];

        cout << "Scenario #" << cnt << endl;
        cout << fixed << setprecision(3) << "Frog Distance = " << map[1][2] << endl;

        /////////////////////////
        coor.clear();
        cout << endl;
    }
    return 0;
}

【POJ】Stockbroker Grapevine

Problem here

Description

Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way. Unfortunately for you, stockbrokers only trust information coming from their "Trusted sources" This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.

Input

Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a '1' means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules. Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people.

Output

For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes. It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message "disjoint". Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.

Sample Input

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

Sample Output

3 2
3 10

Solution

Floyd

#include <iostream>
#include <memory.h>
#define INF_NUM 99999999
using namespace std;

int n;
int dis[200][200];

int main(){
    while(cin >> n){
        if(n == 0)
            break;
        for(int i = 1; i <= n; i++){
            for(int j= 1; j <= n; j++)
                dis[i][j] = INF_NUM;
            dis[i][i] = 0;
        }
        for(int i = 1; i <= n; i++){
            int t, x, w;
            cin >> t;
            for(int j = 0; j < t; j++){
                cin >> x >> w;
                dis[i][x] = w;
            }
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                    if(dis[j][i] + dis[i][k] < dis[j][k])
                        dis[j][k] = dis[j][i] + dis[i][k];

        int ans = INF_NUM;
        int ans_pos;
        bool ok = false;
        for(int i = 1; i <= n; i++){
            int maxlen = 0;
            bool check = true;
            for(int j = 1; j <= n; j++){
                if(dis[i][j] == INF_NUM){
                    check = false;
                    break;
                }else if(dis[i][j] > maxlen){
                    maxlen = dis[i][j];
                }
            }
            if(check){
                ok = true;
                if(ans > maxlen){
                    ans = maxlen;
                    ans_pos = i;
                }
            }
        }
            if(ok){
                cout << ans_pos << " " << ans << endl;
            }else{
                cout <<"disjoint" << endl;
            }

        }

    return 0;
}

【POJ】Jungle Roads

Problem here

Description

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

Input

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

Output

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

Sample Input

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

Sample Output

216
30

Solution

Kruskal

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <utility>
#include <queue>
#define INF_NUM 0xfffffff
using namespace std;

vector<pair<pair<int, int>, int > >adj;    //((頂點1, 頂點2), cost)
vector<pair<int, int> >ans;
int pre[100];
int n;

void init(){
    adj.clear();
    ans.clear();
    memset(pre, INF_NUM, sizeof(pre));
}

bool cmp(pair<pair<int, int>, int > &a, pair<pair<int, int>, int >&b){
    return a.second < b.second;
}

int find(int x){
    int r = x;
    while(pre[r] != r){
        r = pre[r];
    }
    int i = x;
    int j;
    while(pre[i] != r){
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void join(int x, int y){
    int p1 = find(x);
    int p2 = find(y);
    if(p1 != p2){
        pre[p1] = p2;
    }
}

int kruskal(){
    int ret = 0;
    sort(adj.begin(), adj.end(), cmp);
    for(int i = 0; i < n; i++)
        pre[i] = i;

    for(int i = 0; i < adj.size(); ++i){
        int cost = adj[i].second;
        int u = adj[i].first.first;
        int v = adj[i].first.second;
        if(find(u) == find(v))
            continue;

        join(u, v);
        ans.push_back(make_pair(u,v));
        ret += cost;
    }
    return ret;
}

int main(){
    while(cin >> n){
        if(n == 0)
            break;

        init();
        for(int cnt = 1; cnt <= n-1; cnt++){
            char c;
            int k;
            cin >> c >> k;
            if(k > 0){
                for(int i = 0; i < k; i++){
                    char cc;
                    int kk;
                    cin >> cc >> kk;
                    int x = c - 'A';
                    int y = cc - 'A';
                    adj.push_back(make_pair(make_pair(x, y), kk));
                }
            }
        }

        cout << kruskal() << endl;

    }
    return 0;
}

【POJ】Highways

Problem here

Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.

Input

The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

Output

For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

Sample Input

1

3
0 990 692
990 0 179
692 179 0

Sample Output

692

Hint

Huge input,scanf is recommended.

Source

POJ Contest,Author:Mathematica@ZSU

Solution

#include <string>
#include <cstdio>
#include <stdio.h>
#define MAX_NUM 0x3f3f3f3f
using namespace std;
int map[501][501];
int dis[501];
bool visit[501];
int n, cnt, min_num, j, sum;
void prim(){
    while(cnt < n){
        min_num = MAX_NUM;
        for(int i = 1; i <=  n; i++){
            if(visit[i] == false && dis[i] < min_num){
                min_num = dis[i];
                j = i;
            }
        }
        visit[j] = true;
        cnt++;
        sum = max(sum, dis[j]);
        for(int i = 1; i <= n; i++){
            if(visit[i] == false && dis[i] > map[j][i]){
                dis[i] = map[j][i];
            }
        }
    }
}

int main(){

    int kase;
    scanf("%d", &kase);
    while(kase--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d", &map[i][j]);
            }
        }
        for(int i = 2; i <= n; i++){
            dis[i] = map[1][i];
            visit[i] = false;
        }

        sum = 0;
        visit[1] = true;
        dis[1] = 0;
        cnt = 1;
        prim();
        printf("%d\n", sum);
    }

    return 0;
}

【HDU】Red and Black

Problem here

Problem Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.'.' - a black tile '#' - a red tile '@' - a man on a black tile(appears exactly once in a data set)

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

Sample Output
45

Source

Asia 2004, Ehime (Japan), Japan Domestic

Solution

#include <iostream>
#include <memory.h>
using namespace std;
int w, h;
int map[100][100];
int cnt;

void dfs(int x, int y){
    if(x < 0 || y < 0 || x >= h || y >= w || map[x][y] == 1)
        return;

    cnt++;
    map[x][y] = 1;
    dfs(x+1, y);
    dfs(x, y+1);
    dfs(x-1, y);
    dfs(x, y-1);
}

int main(){
    while(cin >> w >> h){
        if(w == 0 && h == 0)
            break;

        int p, q;
        cnt = 0;
        memset(map, 0, sizeof(map));
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                char input;
                cin >> input;
                if(input == '@'){
                    p = i; 
                    q = j;
                }
                if(input == '#')
                    map[i][j] = 1;

            }
        }

        dfs(p, q);
        cout << cnt << endl;
    }

    return 0;
}

【POJ】A Knight's Journey

Problem here

Description

Background

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? *Problem** Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p q <= 26. This represents a p q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number. If no such path exist, you should output impossible on a single line.

Sample Input

31 12 34 3

Sample Output

Scenario #1:A
1Scenario #2:impossible
Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4

Source

TUD Programming Contest 2005, Darmstadt, Germany

Solution

#include <iostream>
#include <memory.h>
using namespace std;

int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

int allStep;
char ans[100];
bool visit[100][100];
bool ok;
int p, q;

void dfs(int cnt, int x, int y){
    if(cnt == allStep){
        for(int i = 0; i < 2*cnt; i++){
            cout << ans[i];
        }
        cout << endl;
        ok = true;
        return ;
    }

    for(int i = 0; i < 8; i++){
        if(ok == false){
            int new_x = x+dx[i];
            int new_y = y+dy[i];
            if(new_x > 0 && new_y > 0 && new_x <= q && new_y <= p){
                if(visit[new_x][new_y] == false){
                    visit[new_x][new_y] = true;
                    ans[2*cnt] = 'A' + new_x-1;
                    ans[2*cnt+1] = '1' + new_y-1;
                    dfs(cnt+1, new_x, new_y);
                    visit[new_x][new_y] = false;
                }
            }
        }
    }
}

int main(){

    int kase;
    cin >> kase;
    for(int ks = 1; ks <= kase; ks++){
        cin >> p >> q;
        allStep = p*q;
        memset(visit, false, sizeof(visit));
        ok = false;
        visit[1][1] = true;
        ans[0] = 'A';
        ans[1] = '1';
        cout << "Scenario #" << ks << ":" << endl;
        dfs(1, 1, 1);
        if(ok == false){
            cout << "impossible" << endl;
        }
        cout << endl; 
    }

    return 0;
}

【UVa】208 - Firetruck

Problem here

Problem

The Center City fire department collaborates with the transportation department to maintain maps
of the city which reflects the current status of the city streets. On any given day, several streets are
closed for repairs or construction. Firefighters need to be able to select routes from the firestations to
fires that do not use closed streets.
Central City is divided into non-overlapping fire districts, each containing a single firestation. When
a fire is reported, a central dispatcher alerts the firestation of the district where the fire is located and
gives a list of possible routes from the firestation to the fire. You must write a program that the central
dispatcher can use to generate routes from the district firestations to the fires.

INPUT

The city has a separate map for each fire district. Streetcorners of each map are identified by positive
integers less than 21, with the firestation always on corner #1. The input file contains several test cases
representing different fires in different districts.
• The first line of a test case consists of a single integer which is the number of the streetcorner
closest to the fire.
• The next several lines consist of pairs of positive integers separated by blanks which are the
adjacent streetcorners of open streets. (For example, if the pair 4 7 is on a line in the file, then
the street between streetcorners 4 and 7 is open. There are no other streetcorners between 4 and
7 on that section of the street.)
• The final line of each test case consists of a pair of 0’s.

OUTPUT

For each test case, your output must identify the case by number (‘CASE 1:’, ‘CASE 2:’, etc). It must
list each route on a separate line, with the streetcorners written in the order in which they appear on
the route. And it must give the total number routes from firestation to the fire. Include only routes
which do not pass through any streetcorner more than once. (For obvious reasons, the fire
department doesn’t want its trucks driving around in circles.)
Output from separate cases must appear on separate lines.

Sample

input

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

output

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

Solution

Floyd 判斷b能否到達終點
再判斷a 能否到達b

#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int a[30][30], b[30][30];
int visit[30], ans[30];
int m, cas, cnt, n;

void dfs(int c, int p){
    if(p == n){
        cnt++;
        for(int i = 0; i < c; i++){
            if(i > 0)   
                cout << " ";
            cout << ans[i];
        }
        cout << endl;
        return ;
    }

    for(int i = 1; i <= m; i++){
        if(visit[i])
            continue;
        if(!a[p][i])
            continue;
        if(!b[i][n])
            continue;
        visit[i] = 1;
        ans[c] = i;
        dfs(c+1,i);
        visit[i] = 0;
    }
}

int main(){
    cas = 0;
    while(cin >> n){
        int x, y;
        cas++;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(visit, 0, sizeof(visit));
        memset(ans, 0, sizeof(ans));
        while(cin >> x >> y){
            if(x == 0 && y == 0)
                break;

            a[x][y] = a[y][x] = 1;
            b[x][y] = b[y][x] = 1;
            m = max(m, max(x, y));
        }

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= m; j++)
                for(int k = 1; k <= m; k++)
                    if(b[j][i] && b[i][k])
                        b[j][k] = 1;

        cnt = 0;
        visit[1] = 1;
        ans[0] = 1;
        cout << "CASE " << cas << ":" << endl;
        dfs(1, 1);
        cout << "There are " << cnt << " routes from the firestation to streetcorner " << n << "." << endl;

    }

    return 0;
}