zoj1298

maksyuki 发表于 oj 分类，标签: 图论-最短路

11 9月 2015

Domino Effect

Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase domino effect'' comes from).

While this is somewhat pointless with only a few dominoes, some people went to the opposite extreme in the early Eighties. Using millions of dominoes of different colors and materials to fill whole halls with elaborate patterns of falling dominoes, they created (short-lived) pieces of art. In these constructions, usually not only one but several rows of dominoes were falling at the same time. As you can imagine, timing is an essential factor here.

It is now your task to write a program that, given such a system of rows formed by dominoes, computes when and where the last domino falls. The system consists of several key dominoes'' connected by rows of simple dominoes. When a key domino falls, all rows connected to the domino will also start falling (except for the ones that have already fallen). When the falling rows reach other key dominoes that have not fallen yet, these other key dominoes will fall as well and set off the rows connected to them. Domino rows may start collapsing at either end. It is even possible that a row is collapsing on both ends, in which case the last domino falling in that row is somewhere between its key dominoes. You can assume that rows fall at a uniform rate.
Input

The input contains descriptions of several domino systems. The first line of each description contains two integers: the number n of key dominoes (1 <= n < 500) and the number m of rows between them. The key dominoes are numbered from 1 to n. There is at most one row between any pair of key dominoes and the domino graph is connected, i.e. there is at least one way to get from a domino to any other domino by following a series of domino rows.

The following m lines each contain three integers a, b, and l, stating that there is a row between key dominoes a and b that takes l seconds to fall down from end to end.

Each system is started by tipping over key domino number 1.

The input ends with an empty system (with n = m = 0), which should not be processed.
Output

For each case output a line stating the number of the case (System #1', System #2', etc.). Then output a line containing the time when the last domino falls, exact to one digit to the right of the decimal point, and the location of the last domino falling, which is either at a key domino or between two key dominoes. Adhere to the format shown in the output sample. If you find several solutions, output only one of them. Output a blank line after each system.
Sample Input

2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
0 0

Sample Output

System #1
The last domino falls after 27.0 seconds, at key domino 2.

System #2
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.

题目类型：单源最短路

算法分析：题目所求的最后倒下的牌分两种情况：1最后倒下的牌是关键牌，所用时间是从源点1开始求得的最短路径中最大值。2最后倒下的牌是普通牌，所用时间是某一边邻接的两个节点的最短路径值和该边权之和的一半。推导过程：假设有dis[i]、dis[j]和edge[i][j] < INF。其中存在dis[i] < dis[j]，则该边倒下的时间是dis[j] + [edge[i][j] – (dis[j] – dis[i])] / 2。化简为(dis[i] + dis[j] + edge[i][j]) / 2。最后求得上述的两个时间，比较大小并输出相应情况的解

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 666 + 66;
const int INF = 66666666;
const int EPS = 1e-6;

int edge[maxn][maxn];
int dis[maxn];
bool is_visited[maxn];

int n, m, flag = 1;

void Dijkstra ()
{
    int i;
    for (i = 1; i <= n; i++)
        dis[i] = edge[1][i];

    memset (is_visited, false, sizeof (is_visited));

    is_visited[1] = true;//important!!!!!!
    dis[1] = 0;         //important!!!!!!

    for (i = 2; i <= n; i++)
    {
        int minval = INF, minval_index;

        int j;
        for (j = 2; j <= n; j++)
        {
            if (!is_visited[j] && dis[j] < minval)
            {
                minval = dis[j];
                minval_index = j;
            }
        }

        is_visited[minval_index] = true;

        for (j = 2; j <= n; j++)
        {
            if (!is_visited[j] && edge[minval_index][j] != INF && dis[j] >
                dis[minval_index] + edge[minval_index][j])
            {
                dis[j] = dis[minval_index] + edge[minval_index][j];
            }
        }
    }

    double maxtime1 = -INF;
    int index1;
    for (i = 1; i <= n; i++)
    {
        if (maxtime1 < dis[i])
        {
            maxtime1 = dis[i];
            index1 = i;
        }
    }

    double maxtime2 = -INF;
    int index_x, index_y;
    for (i = 1; i <= n; i++)
    {
        int j;
        for (j = 1; j <= n; j++)
        {
            double temp = (dis[i] + dis[j] + edge[i][j]) / 2.0;

            if (edge[i][j] < INF && maxtime2 < temp)
            {
                maxtime2 = temp;
                index_x = i;
                index_y = j;
            }
        }
    }

    if (maxtime2 > maxtime1)
        cout << "The last domino falls after " << fixed << setprecision (1) << maxtime2
        << " seconds, between key dominoes " << index_x << " and " << index_y << "." << endl;

    else
        cout << "The last domino falls after " << fixed << setprecision (1) << maxtime1
        << " seconds, at key domino " << index1 << "." << endl;
}
int main()
{
//    ifstream cin ("aaa.txt");

    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
            break;

        int i, j;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                edge[i][j] = INF;

        for (i = 0; i < m; i++)
        {
            int temp_a, temp_b, temp_val;
            cin >> temp_a >> temp_b >> temp_val;

            edge[temp_a][temp_b] = edge[temp_b][temp_a] = temp_val;
        }

        cout << "System #" << flag++ << endl;

        Dijkstra ();

        cout << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 666 + 66;

const int INF = 66666666;

const int EPS = 1e-6;

int edge[maxn][maxn];

int dis[maxn];

bool is_visited[maxn];

int n, m, flag = 1;

void Dijkstra ()

{

int i;

for (i = 1; i <= n; i++)

dis[i] = edge[1][i];

memset (is_visited, false, sizeof (is_visited));

is_visited[1] = true;//important!!!!!!

dis[1] = 0; //important!!!!!!

for (i = 2; i <= n; i++)

{

int minval = INF, minval_index;

int j;

for (j = 2; j <= n; j++)

{

if (!is_visited[j] && dis[j] < minval)

{

minval = dis[j];

minval_index = j;

}

is_visited[minval_index] = true;

for (j = 2; j <= n; j++)

{

if (!is_visited[j] && edge[minval_index][j] != INF && dis[j] >

dis[minval_index] + edge[minval_index][j])

{

dis[j] = dis[minval_index] + edge[minval_index][j];

}

double maxtime1 = -INF;

int index1;

for (i = 1; i <= n; i++)

{

if (maxtime1 < dis[i])

{

maxtime1 = dis[i];

index1 = i;

}

double maxtime2 = -INF;

int index_x, index_y;

for (i = 1; i <= n; i++)

{

int j;

for (j = 1; j <= n; j++)

{

double temp = (dis[i] + dis[j] + edge[i][j]) / 2.0;

if (edge[i][j] < INF && maxtime2 < temp)

{

maxtime2 = temp;

index_x = i;

index_y = j;

}

if (maxtime2 > maxtime1)

cout << "The last domino falls after " << fixed << setprecision (1) << maxtime2

<< " seconds, between key dominoes " << index_x << " and " << index_y << "." << endl;

else

cout << "The last domino falls after " << fixed << setprecision (1) << maxtime1

<< " seconds, at key domino " << index1 << "." << endl;

}

int main()

{

// ifstream cin ("aaa.txt");

while (cin >> n >> m)

{

if (n == 0 && m == 0)

break;

int i, j;

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

edge[i][j] = INF;

for (i = 0; i < m; i++)

{

int temp_a, temp_b, temp_val;

cin >> temp_a >> temp_b >> temp_val;

edge[temp_a][temp_b] = edge[temp_b][temp_a] = temp_val;

}

cout << "System #" << flag++ << endl;

Dijkstra ();

cout << endl;

}

return 0;

}

zoj1221

maksyuki 发表于 oj 分类，标签: 图论-最短路

11 9月 2015

Risk

Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the armies may move into the newly conquered country.

During the course of play, a player often engages in a sequence of conquests with the goal of transferring a large mass of armies from some starting country to a destination country. Typically, one chooses the intervening countries so as to minimize the total number of countries that need to be conquered. Given a description of the gameboard with 20 countries each with between 1 and 19 connections to other countries, your task is to write a function that takes a starting country and a destination country and computes the minimum number of countries that must be conquered to reach the destination. You do not need to output the sequence of countries, just the number of countries to be conquered including the destination. For example, if starting and destination countries are neighbors, then your program should return one.

The following connection diagram illustrates the sample input.
Input

Input to your program will consist of a series of country configuration test sets. Each test set will consist of a board description on lines 1 through 19. The representation avoids listing every national boundary twice by only listing the fact that country I borders country J when I < J. Thus, the Ith line, where I is less than 20, contains an integer X indicating how many "higher-numbered" countries share borders with country I, then X distinct integers J greater than I and not exceeding 20, each describing a boundary between countries I and J. Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow. The next N lines each contain exactly two integers (1 <= A,B <= 20; A!=B) indicating the starting and ending countries for a possible conquest.

There can be multiple test sets in the input; your program should continue reading and processing until reaching the end of file. There will be at least one path between any two given countries in every country configuration.
Output

For each input set, your program should print the following message "Test Set #T" where T is the number of the test set starting with 1. The next NT lines each will contain the result for the corresponding test in the test set - that is, the minimum number of countries to conquer. The test result line should contain the start country code A the string " to " the destination country code B ; the string ": " and a single integer indicating the minimum number of moves required to traverse from country A to country B in the test set. Following all result lines of each input set, your program should print a single blank line.
Sample Input

1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
Sample Output

Test Set #1
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2

题目类型：全源最短路(Floyd)

算法分析：直接将读入的数据建成一个无向图，每个边的权值为1，然后调用一次Floyd算法计算全源最短路，然后对于每一个查询，直接输出edge数组中相应的值即可。本题中要求的征服城市的数量(包括目标城市)其实等于求路径中边的数量，也就是求边权为1的最短路，当然本题也可以使用BFS求解，只不过对于每一个查询都要调用一次BFS

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 66;
const int INF = 0x7FFFFFFF;

long long edge[maxn][maxn];

void floyd ()
{
    int i, j, k;
    for (k = 1; k <= 20; k++)
    {
        for (i = 1; i <= 20; i++)
        {
            for (j = 1; j <= 20; j++)
                edge[i][j] = min (edge[i][j], edge[i][k] + edge[k][j]);
        }
    }
}


int main()
{
//    ifstream cin ("aaa.txt");

    int num, val, flag = 1;

    while (cin >> num)
    {
        int i, j;
        for (i = 1; i <= 20; i++)
        {
            for (j = 1; j <= 20; j++)
            {
                if (i == j)
                    edge[i][j] = 0;

                else
                    edge[i][j] = INF;
            }
        }

        for (i = 0; i < num; i++)
        {
            cin >> val;
            edge[1][val] = edge[val][1] = 1;
        }

        for (i = 2; i <= 19; i++)
        {
            cin >> num;
            int j;
            for (j = 0; j < num; j++)
            {
                cin >> val;
                edge[i][val] = edge[val][i] = 1;
            }
        }

        floyd ();

        cout << "Test Set #" << flag++ << endl;
        int q;
        cin >> q;
        for (i = 0; i < q; i++)
        {
            int s, e;
            cin >> s >> e;
            cout << s << " to " << e << ": " << edge[s][e] << endl;
        }
        cout << endl;
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 66;

const int INF = 0x7FFFFFFF;

long long edge[maxn][maxn];

void floyd ()

{

int i, j, k;

for (k = 1; k <= 20; k++)

{

for (i = 1; i <= 20; i++)

{

for (j = 1; j <= 20; j++)

edge[i][j] = min (edge[i][j], edge[i][k] + edge[k][j]);

}

int main()

{

// ifstream cin ("aaa.txt");

int num, val, flag = 1;

while (cin >> num)

{

int i, j;

for (i = 1; i <= 20; i++)

{

for (j = 1; j <= 20; j++)

{

if (i == j)

edge[i][j] = 0;

else

edge[i][j] = INF;

}

for (i = 0; i < num; i++)

{

cin >> val;

edge[1][val] = edge[val][1] = 1;

}

for (i = 2; i <= 19; i++)

{

cin >> num;

int j;

for (j = 0; j < num; j++)

{

cin >> val;

edge[i][val] = edge[val][i] = 1;

}

floyd ();

cout << "Test Set #" << flag++ << endl;

int q;

cin >> q;

for (i = 0; i < q; i++)

{

int s, e;

cin >> s >> e;

cout << s << " to " << e << ": " << edge[s][e] << endl;

}

cout << endl;

}

return 0;

}

zoj1203

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

11 9月 2015

Swordfish

There exists a world within our world
A world beneath what we call cyberspace.
A world protected by firewalls,

passwords and the most advanced
security systems. 阅读全文 »

zoj1092

maksyuki 发表于 oj 分类，标签: 图论-最短路

11 9月 2015

Arbitrage

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

Input Specification

The input file will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name c_i of a source currency, a real number r_ij which represents the exchange rate from c_ito c_j and a name c_j of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output Specification

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

Sample Input

3USDollarBritishPoundFrenchFranc3USDollar 0.5 BritishPoundBritishPound 10.0 FrenchFrancFrenchFranc 0.21 USDollar 3USDollarBritishPoundFrenchFranc6USDollar 0.5 BritishPoundUSDollar 4.9 FrenchFrancBritishPound 10.0 FrenchFrancBritishPound 1.99 USDollarFrenchFranc 0.09 BritishPoundFrenchFranc 0.19 USDollar 0

Sample Output

Case 1: YesCase 2: No

题目类型：最长回路

算法分析：调用n次bellman-ford算法计算每一点为源点的最长回路(乘积)，对于长度大于1.0的情况直接可以判断出出现套汇

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 36 + 6;
const double EPS = 1e-6;


struct Node
{
    int u, v;
    double w;
};

Node edge[maxn*maxn];

char input[maxn][maxn];
double dis[maxn];

bool is_valid;
int n, flag = 1, m;

void bellman_ford (int s)
{
    memset (dis, 0, sizeof (dis));
    dis[s] = 1;

    int i;
    for (i = 1; i <= n; i++)
    {
        int j;
        for (j = 0; j < m; j++)
        {
            if (dis[edge[j].u] * edge[j].w > dis[edge[j].v] + EPS)
                dis[edge[j].v] = dis[edge[j].u] * edge[j].w;
        }
    }

    if (dis[s] > 1.0 + EPS)
        is_valid = true;

}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    while (scanf ("%d", &n) != EOF)
    {
        if (n == 0)
            break;

        int i;
        for (i = 0; i < n; i++)
            scanf ("%s", input[i]);

        scanf ("%d", &m);

        for (i = 0; i < m; i++)
        {
            char temp_a[maxn], temp_b[maxn];
            double temp_w;
            scanf ("%s %lf %s", temp_a, &temp_w, temp_b);

            int j;
            for (j = 0; strcmp (temp_a, input[j]); j++) ;
            edge[i].u = j;

            for (j = 0; strcmp (temp_b, input[j]); j++) ;
            edge[i].v = j;

            edge[i].w = temp_w;
        }

        is_valid = false;

        for (i = 0; i < n; i++)
        {
            bellman_ford (i);

            if (is_valid)
                break;
        }

        cout << "Case " << flag++ << ": ";

        if (is_valid)
            cout << "Yes" << endl;

        else
            cout << "No" << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 36 + 6;

const double EPS = 1e-6;

struct Node

{

int u, v;

double w;

};

Node edge[maxn*maxn];

char input[maxn][maxn];

double dis[maxn];

bool is_valid;

int n, flag = 1, m;

void bellman_ford (int s)

{

memset (dis, 0, sizeof (dis));

dis[s] = 1;

int i;

for (i = 1; i <= n; i++)

{

int j;

for (j = 0; j < m; j++)

{

if (dis[edge[j].u] * edge[j].w > dis[edge[j].v] + EPS)

dis[edge[j].v] = dis[edge[j].u] * edge[j].w;

}

if (dis[s] > 1.0 + EPS)

is_valid = true;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

while (scanf ("%d", &n) != EOF)

{

if (n == 0)

break;

int i;

for (i = 0; i < n; i++)

scanf ("%s", input[i]);

scanf ("%d", &m);

for (i = 0; i < m; i++)

{

char temp_a[maxn], temp_b[maxn];

double temp_w;

scanf ("%s %lf %s", temp_a, &temp_w, temp_b);

int j;

for (j = 0; strcmp (temp_a, input[j]); j++) ;

edge[i].u = j;

for (j = 0; strcmp (temp_b, input[j]); j++) ;

edge[i].v = j;

edge[i].w = temp_w;

}

is_valid = false;

for (i = 0; i < n; i++)

{

bellman_ford (i);

if (is_valid)

break;

}

cout << "Case " << flag++ << ": ";

if (is_valid)

cout << "Yes" << endl;

else

cout << "No" << endl;

}

return 0;

}

zoj1091

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

11 9月 2015

Knight Moves

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input Specification

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output Specification

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input

e2 e4a1 b2b2 c3a1 h8a1 h7h8 a1b1 c3f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.To get from a1 to b2 takes 4 knight moves.To get from b2 to c3 takes 2 knight moves.To get from a1 to h8 takes 6 knight moves.To get from a1 to h7 takes 5 knight moves.To get from h8 to a1 takes 6 knight moves.To get from b1 to c3 takes 1 knight moves.To get from f6 to f6 takes 0 knight moves.

题目类型：简单BFS

算法分析：直接从起点使用一次BFS并记录到终点时所走过的路径长度即可

#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

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

int start_x, start_y, end_x, end_y;
int ans[36][36];
bool visited[36][36];

struct point
{
	int x;
	int y;
	int steps;
	point (int xx, int yy, int ss) : x (xx), y (yy), steps (ss) {}

};

queue <point> q;

bool okjump (int x, int y)
{
	if (x >= 0 && x <= 7 && y >= 0 && y <= 7 && !visited[x][y])
		return true;

return false;

}

int BFS (int x, int y, int steps)
{
	while (!q.empty ())						//important!!!!!1
		q.pop ();

	memset (visited, false, sizeof (visited));
	q.push (point (x, y, steps));
	visited[x][y] = true;

	while (!q.empty ())
	{
		point temp = q.front ();
		if (temp.x == end_x && temp.y == end_y)
			return temp.steps;

		int i;
		for (i = 0; i < 8; i++)
			if (okjump (temp.x + dx[i], temp.y + dy[i]))
			{
				q.push (point (temp.x + dx[i], temp.y + dy[i], temp.steps + 1));
				visited[temp.x+dx[i]][temp.y+dy[i]] = true;
			}
		
		q.pop ();
	}

return 0;
}

int main()
{
	//ifstream cin ("aaa.txt");

	char start_ch[6];
	char end_ch[6];

	while (cin >> start_ch >> end_ch)
	{
		start_x = start_ch[1] - '0';
		start_y = start_ch[0] - 'a';
		end_x = end_ch[1] - '0';
		end_y = end_ch[0] - 'a';
		
		start_x--;
		end_x--;
		int sum = BFS (start_x, start_y, 0);

		cout << "To get from " << start_ch << " to " << end_ch << " takes " << sum << " knight moves." << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

#include <queue>

using namespace std;

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

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

int start_x, start_y, end_x, end_y;

int ans[36][36];

bool visited[36][36];

struct point

{

int x;

int y;

int steps;

point (int xx, int yy, int ss) : x (xx), y (yy), steps (ss) {}

};

queue <point> q;

bool okjump (int x, int y)

{

if (x >= 0 && x <= 7 && y >= 0 && y <= 7 && !visited[x][y])

return true;

return false;

}

int BFS (int x, int y, int steps)

{

while (!q.empty ()) //important!!!!!1

q.pop ();

memset (visited, false, sizeof (visited));

q.push (point (x, y, steps));

visited[x][y] = true;

while (!q.empty ())

{

point temp = q.front ();

if (temp.x == end_x && temp.y == end_y)

return temp.steps;

int i;

for (i = 0; i < 8; i++)

if (okjump (temp.x + dx[i], temp.y + dy[i]))

{

q.push (point (temp.x + dx[i], temp.y + dy[i], temp.steps + 1));

visited[temp.x+dx[i]][temp.y+dy[i]] = true;

}

q.pop ();

}

return 0;

}

int main()

{

//ifstream cin ("aaa.txt");

char start_ch[6];

char end_ch[6];

while (cin >> start_ch >> end_ch)

{

start_x = start_ch[1] - '0';

start_y = start_ch[0] - 'a';

end_x = end_ch[1] - '0';

end_y = end_ch[0] - 'a';

start_x--;

end_x--;

int sum = BFS (start_x, start_y, 0);

cout << "To get from " << start_ch << " to " << end_ch << " takes " << sum << " knight moves." << endl;

}

return 0;

}

zoj1082

maksyuki 发表于 oj 分类，标签: 图论-最短路

11 9月 2015

Stockbroker Grapevine

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.

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. 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.

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 file is terminated by a set of stockbrokers containing 0 (zero) people.

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

题目类型：全源最短路(Floyd)

算法分析：使用Floyd算法计算一次全源最短路，然后对于每一个节点求得该节点到其他所有节点(可达)的最大距离，然后直接输出所有最大距离中的最小值和该节点的编号。判断有向图中存在不可达节点的方法是判断edge[i][j]和edge[j][i]是否同时为INF，如果是则说明图中存在不可达的节点。注意不要使用程序定义的INF常变量进行加法运算，因为容易溢出而导致WA！！！

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 666;
const int INF = 0x7FFFFFFF;

long long edge[maxn][maxn];
int n;

void floyd ()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
    {
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
                edge[i][j] = min (edge[i][j], edge[i][k] + edge[k][j]);
        }
    }
}


int main()
{
//    ifstream cin ("aaa.txt");

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

        int i, j;
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (i == j)
                    edge[i][j] = 0;

                else
                    edge[i][j] = INF;
            }
        }

        for (i = 1; i <= n; i++)
        {
            int num;
            cin >> num;

            int j;
            for (j = 0; j < num; j++)
            {
                int v, w;
                cin >> v >> w;
                edge[i][v] = w;
            }
        }

        floyd ();

        int minval = INF, index;
        bool is_valid = true;

        for (i = 1; i <= n; i++)
        {
            int j, maxval = -INF;

            for (j = 1; j <= n; j++)
            {
                if (i == j)
                    continue;

                if (edge[i][j] == INF && edge[j][j] == INF)
                    is_valid = false;

                if (edge[i][j] > maxval)
                {
                    maxval = edge[i][j];
                }
            }

            if (minval > maxval)
            {
                minval = maxval;
                index = i;
            }
        }

        if (is_valid)
            cout << index << " " << minval << endl;

        else
            cout << "disjoint" << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 666;

const int INF = 0x7FFFFFFF;

long long edge[maxn][maxn];

int n;

void floyd ()

{

int i, j, k;

for (k = 1; k <= n; k++)

{

for (i = 1; i <= n; i++)

{

for (j = 1; j <= n; j++)

edge[i][j] = min (edge[i][j], edge[i][k] + edge[k][j]);

}

int main()

{

// ifstream cin ("aaa.txt");

while (cin >> n)

{

if (n == 0)

break;

int i, j;

for (i = 1; i <= n; i++)

{

for (j = 1; j <= n; j++)

{

if (i == j)

edge[i][j] = 0;

else

edge[i][j] = INF;

}

for (i = 1; i <= n; i++)

{

int num;

cin >> num;

int j;

for (j = 0; j < num; j++)

{

int v, w;

cin >> v >> w;

edge[i][v] = w;

}

floyd ();

int minval = INF, index;

bool is_valid = true;

for (i = 1; i <= n; i++)

{

int j, maxval = -INF;

for (j = 1; j <= n; j++)

{

if (i == j)

continue;

if (edge[i][j] == INF && edge[j][j] == INF)

is_valid = false;

if (edge[i][j] > maxval)

{

maxval = edge[i][j];

}

if (minval > maxval)

{

minval = maxval;

index = i;

}

if (is_valid)

cout << index << " " << minval << endl;

else

cout << "disjoint" << endl;

}

return 0;

}

zoj1076

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

11 9月 2015

Gene Assembly

Statement of the Problem

With the large amount of genomic DNA sequence data being made available, it is becoming more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more complicated, because of the presence of junk DNA that interrupts the coding region of genes in the genomic sequence. That is, a gene is composed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and their lengths can be arbitrary.

Most gene finding algorithms have two steps: in the first they search for possible exons; in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in the genomic sequence. We say that exon i appears before exon j if the end of i precedes the beginning of j.

The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that cound be assembled to generate a gene.

Input Format

Several input instances are given. Each instance begins with the number 0 < n < 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most 50000 basis. The input ends with a line with a single 0.

Output Format

For each input instance your program should print in one line the chain with the largest possible number of exons, by enumerating the exons in the chain. If there is more than one chain with the same number of exons, your program can print anyone of them.

Sample Input

6
340 500
220 470
100 300
880 943
525 556
612 776
3
705 773
124 337
453 665
0

Sample Output

3 1 5 6 4
2 3 1

题目类型：贪心

算法分析：这是一道经典的任务调度问题，先按任务的结束时间递减排序，再逐个选择，选择活动的起始时间大于已选择活动的结束时间，最后输出选择的活动的id即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

struct Node
{
    int x, y, flag;
};

bool Cmp (Node a, Node b)
{
    return a.y < b.y;
}

Node ans[1666];
int output[1666];

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

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

        int i;
        for (i = 0; i < n; i++)
        {
            cin >> ans[i].x >> ans[i].y;
            ans[i].flag = i + 1;
        }

        sort (ans, ans + n, Cmp);

        int len = 0;

        output[len++] = ans[0].flag;
        int ps = ans[0].y;

        for (i = 1; i < n; i++)
        {
            if (ps <= ans[i].x)
            {
                ps = ans[i].y;
                output[len++] = ans[i].flag;
            }
        }

        for (i = 0; i < len - 1; i++)
            cout << output[i] << " ";
        cout << output[i] << endl;
    }


return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

struct Node

{

int x, y, flag;

};

bool Cmp (Node a, Node b)

{

return a.y < b.y;

}

Node ans[1666];

int output[1666];

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int n;

while (cin >> n)

{

if (n == 0)

break;

int i;

for (i = 0; i < n; i++)

{

cin >> ans[i].x >> ans[i].y;

ans[i].flag = i + 1;

}

sort (ans, ans + n, Cmp);

int len = 0;

output[len++] = ans[0].flag;

int ps = ans[0].y;

for (i = 1; i < n; i++)

{

if (ps <= ans[i].x)

{

ps = ans[i].y;

output[len++] = ans[i].flag;

}

for (i = 0; i < len - 1; i++)

cout << output[i] << " ";

cout << output[i] << endl;

}

return 0;

}

zoj1061

maksyuki 发表于 oj 分类，标签: 数据结构-栈/单调

11 9月 2015

Web Navigation

Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. In this problem, you are asked to implement this.

The following commands need to be supported:

BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored.

FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored.

VISIT <url>: Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.

QUIT: Quit the browser.

Assume that the browser initially loads the web page at the URL http://www.acm.org/
This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.
Input

Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem instance requires more than 100 elements in each stack at any time. The end of input is indicated by the QUIT command.

Output

For each command other than QUIT, print the URL of the current page after the command is executed if the command is not ignored. Otherwise, print "Ignored". The output for each command should be printed on its own line. No output is produced for the QUIT command.

Sample Input

VISIT http://acm.ashland.edu/
VISIT http://acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

Sample Output

http://acm.ashland.edu/
http://acm.baylor.edu/acmicpc/
http://acm.ashland.edu/
http://www.acm.org/
Ignored
http://acm.ashland.edu/
http://www.ibm.com/
http://acm.ashland.edu/
http://www.acm.org/
http://acm.ashland.edu/
http://www.ibm.com/
Ignored

题目类型：简单栈模拟

算法分析：直接按照题目所说的方式进行栈模拟即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

int main()
{
//    ifstream cin ("aaa.txt");

        int t;
        cin >> t;

        while (t--)
        {

            string cmd, cur = "http://www.acm.org/";
            stack <string> fs, bs;

            while (cin >> cmd)
            {
                bool is_valid = true;

                if (cmd == "QUIT")
                    break;

                else if (cmd == "VISIT")
                {
                    string temp;
                    cin >> temp;
                    bs.push (cur);
                    cur = temp;

                    while (!fs.empty ())
                        fs.pop ();
                }

                else if (cmd == "BACK")
                {
                    if (!bs.empty ())
                    {
                        fs.push (cur);
                        string temp = bs.top ();
                        bs.pop ();
                        cur = temp;
                    }

                    else
                        is_valid = false;
                }

                else if (cmd == "FORWARD")
                {
                    if (!fs.empty ())
                    {
                        bs.push (cur);
                        string temp = fs.top ();
                        fs.pop ();
                        cur = temp;
                    }

                    else
                        is_valid = false;
                }

                if (is_valid)
                    cout << cur << endl;

                else
                    cout << "Ignored" << endl;
            }

            if (t)
                cout << endl;
        }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

int main()

{

// ifstream cin ("aaa.txt");

int t;

cin >> t;

while (t--)

{

string cmd, cur = "http://www.acm.org/";

stack <string> fs, bs;

while (cin >> cmd)

{

bool is_valid = true;

if (cmd == "QUIT")

break;

else if (cmd == "VISIT")

{

string temp;

cin >> temp;

bs.push (cur);

cur = temp;

while (!fs.empty ())

fs.pop ();

}

else if (cmd == "BACK")

{

if (!bs.empty ())

{

fs.push (cur);

string temp = bs.top ();

bs.pop ();

cur = temp;

}

else

is_valid = false;

}

else if (cmd == "FORWARD")

{

if (!fs.empty ())

{

bs.push (cur);

string temp = fs.top ();

fs.pop ();

cur = temp;

}

else

is_valid = false;

}

if (is_valid)

cout << cur << endl;

else

cout << "Ignored" << endl;

}

if (t)

cout << endl;

}

return 0;

}

xdu1076

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

11 9月 2015

1076: 小W喜欢的数字

题目描述

大家都知道，小W是一名大帅哥，当然比起Light还是有点儿差距的！帅气的小W认为0-9这些数字，只有1,3,5是完美的。

欲问小W为什么，小W总是说“帅哥，是不需要解释的”.所以在帅哥小W的世界里，阅读全文 »

BestCoder Round #54(Div.2) (4/4) (Div.1) (3/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

05 9月 2015

A problem of sorting

Problem Description

There are many people's name and birth in a list.Your task is to print the name from young to old.(There is no pair of 阅读全文 »

返回首页上一页 13 14 15 16 17

超客的水墨烟雨

zoj1298

zoj1221

zoj1203

zoj1092

Input Specification

Output Specification

Sample Input

Sample Output

zoj1091

Input Specification

Output Specification

Sample Input

Sample Output

zoj1082

zoj1076

zoj1061

xdu1076

1076: 小W喜欢的数字

题目描述

BestCoder Round #54(Div.2) (4/4) (Div.1) (3/4)

A problem of sorting

分类目录

标签云

书签

近期评论

2015年9月
一	二	三	四	五	六	日
« 8月				10月 »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30