11 | 9月 | 2015 | 超客的水墨烟雨

zoj3609

maksyuki 发表于 oj 分类，标签: 数论-乘法逆元

11 9月 2015

Modular Inverse

The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a^-1≡x (mod m). This is equivalent to ax≡1 (mod m).

Input

There are multiple test cases. The first line of input is an integer T ≈ 2000 indicating the number of test cases.

Each test case contains two integers 0 < a ≤ 1000 and 0 < m ≤ 1000.

Output

For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist".

Sample Input

33 114 125 13

Sample Output

4Not Exist8

Author: WU, Zejun
Contest: The 9th Zhejiang Provincial Collegiate Programming Contest

题目类型：乘法逆元

算法分析：直接使用乘法逆元求解即可，注意本题要求求解的是最小正值，而不是最小非负值！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

long long gcd_ex (long long a, long long b, long long &x, long long &y)
{
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = gcd_ex (b, a % b, y, x);
    y = y - a / b * x;
    return d;
}

long long mod_equ (long long a, long long b, long long c)
{
    long long x, y;
    long long d = gcd_ex (a, b, x, y);

    if (c % d)
        return -1;

    x = (x * c / d) % (b / d);
    if (x <= 0)
        x += b / d;

    return x;
}

int main()
{
//    CPPFF;
    LL aa, mm, tt;
    cin >> tt;

    while(tt--)
    {
        cin >> aa >> mm;
        LL tt = mod_equ (aa, mm, 1);

        if (tt == -1)
            cout << "Not Exist" << endl;

        else
            cout << tt << endl;
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

long long gcd_ex (long long a, long long b, long long &x, long long &y)

{

if (b == 0) { x = 1; y = 0; return a; }

long long d = gcd_ex (b, a % b, y, x);

y = y - a / b * x;

return d;

}

long long mod_equ (long long a, long long b, long long c)

{

long long x, y;

long long d = gcd_ex (a, b, x, y);

if (c % d)

return -1;

x = (x * c / d) % (b / d);

if (x <= 0)

x += b / d;

return x;

}

int main()

{

// CPPFF;

LL aa, mm, tt;

cin >> tt;

while(tt--)

{

cin >> aa >> mm;

LL tt = mod_equ (aa, mm, 1);

if (tt == -1)

cout << "Not Exist" << endl;

else

cout << tt << endl;

}

return 0;

}

zoj3203

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

11 9月 2015

Light Bulb

Compared to wildleopard's wealthiness, his brother mildleopard is rather poor. His house is narrow and he has only one light bulb in his house. Every night, he is wandering in his incommodious house, thinking of how to earn more money. One day, he found that the length of his shadow was changing from time to time while walking between the light bulb and the wall of his house. A sudden thought ran through his mind and he wanted to know the maximum length of his shadow.

Input

The first line of the input contains an integer T (T <= 100), indicating the number of cases.

Each test case contains three real numbers H, h and D in one line. H is the height of the light bulb while h is the height of mildleopard. D is distance between the light bulb and the wall. All numbers are in range from 10^-2 to 10³, both inclusive, and H - h >= 10^-2.

Output

For each test case, output the maximum length of mildleopard's shadow in one line, accurate up to three decimal places..

Sample Input

2 1 0.5

2 0.5 3

4 3 4

Sample Output

1.000

0.750

4.000

题目类型：三分法

算法分析：手算得出计算影子长度的函数，然后使用三分法求凸形函数的极值点，然后计算函数在极值点处的值即可

#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 double EPS = 1e-6;

double H, h, d;

double Calc (double x)
{
    return (h - x) * d / (H - x) + x;
}


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

    int t;
    cin >> t;

    while (t--)
    {
        cin >> H >> h >> d;

        double low = 0, high = h, mid, midmid;

        while (low + EPS < high)
        {
            mid = low + (high - low) / 2;
            midmid = mid + (high - mid) / 2;

            double midval = Calc (mid);
            double midmidval = Calc (midmid);

            if (midval < midmidval)
                low = mid;

            else
                high = midmid;
        }

        cout << fixed << setprecision (3) << Calc (low) << 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 double EPS = 1e-6;

double H, h, d;

double Calc (double x)

{

return (h - x) * d / (H - x) + x;

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

cin >> H >> h >> d;

double low = 0, high = h, mid, midmid;

while (low + EPS < high)

{

mid = low + (high - low) / 2;

midmid = mid + (high - mid) / 2;

double midval = Calc (mid);

double midmidval = Calc (midmid);

if (midval < midmidval)

low = mid;

else

high = midmid;

}

cout << fixed << setprecision (3) << Calc (low) << endl;

}

return 0;

}

zoj2913

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

11 9月 2015

Bus Pass

You travel a lot by bus and the costs of all the seperate tickets are starting to add up.

Therefore you want to see if it might be advantageous for you to buy a bus pass.

The way the bus system works in your country (and also in the Netherlands) is as follows:

when you buy a bus pass, you have to indicate a center zone and a star value. You are allowed to travel freely in any zone which has a distance to your center zone which is less than your star value. For example, if you have a star value of one, you can only travel in your center zone. If you have a star value of two, you can also travel in all adjacent zones, et cetera.

You have a list of all bus trips you frequently make, and would like to determine the minimum star value you need to make all these trips using your buss pass. But this is not always an easy task. For example look at the following figure:

Here you want to be able to travel from A to B and from B to D. The best center zone is 7400, for which you only need a star value of 4. Note that you do not even visit this zone on your trips!

Input

On the first line an integert(1 <=t<= 100): the number of test cases. Then for each test case:

One line with two integersnz(2 <=nz<= 9 999) andnr(1 <=nr<= 10): the number of zones and the number of bus trips, respectively.

nz lines starting with two integers id_i (1 <= id_i <= 9 999) and mz_i (1 <= mz_i <= 10), a number identifying the i-th zone and the number of zones adjacent to it, followed by mz_i integers: the numbers of the adjacent zones.

nr lines starting with one integer mr_i (1 <= mr_i <= 20), indicating the number of zones the ith bus trip visits, followed by mr_i integers: the numbers of the zones through which the bus passes in the order in which they are visited.

All zones are connected, either directly or via other zones.

Output

For each test case:

One line with two integers, the minimum star value and the id of a center zone which achieves this minimum star value. If there are multiple possibilities, choose the zone with the lowest number.

Sample Input

1
17 2
7400 6 7401 7402 7403 7404 7405 7406
7401 6 7412 7402 7400 7406 7410 7411
7402 5 7412 7403 7400 7401 7411
7403 6 7413 7414 7404 7400 7402 7412
7404 5 7403 7414 7415 7405 7400
7405 6 7404 7415 7407 7408 7406 7400
7406 7 7400 7405 7407 7408 7409 7410 7401
7407 4 7408 7406 7405 7415
7408 4 7409 7406 7405 7407
7409 3 7410 7406 7408
7410 4 7411 7401 7406 7409
7411 5 7416 7412 7402 7401 7410
7412 6 7416 7411 7401 7402 7403 7413
7413 3 7412 7403 7414
7414 3 7413 7403 7404
7415 3 7404 7405 7407
7416 2 7411 7412
5 7409 7408 7407 7405 7415
6 7415 7404 7414 7413 7412 7416

Sample Output

4 7400

题目类型：经典BFS

算法分析：使用dis[i]数组表示标号为i的地区到所有其他地区的最大星形阀值，以每一个公交车站所在的地区为起点进行一次BFS并更新dis数组。注意每一个起点的阀值也要更新。最后输出dis数组中最大的值的下标和值即可

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

const int maxn = 10000 + 66;
const int INF = 66666666;

int dis[maxn];
bool visited[maxn];
vector <int> ans[maxn];

struct Node
{
	int v, d;
	Node (int vv, int dd) : v (vv), d (dd) {}
	Node () {}
};


void BFS (int v, int d)
{
	queue <Node> q;
	q.push(Node (v, d));
	visited[v] = true;
	
	if (dis[v] < d)
		dis[v] = d;

	while (!q.empty ())
	{
		Node temp = q.front ();
		q.pop ();

		int i;
		for (i = 0; i < ans[temp.v].size (); i++)
		{
			if (!visited[ans[temp.v][i]])
			{
				visited[ans[temp.v][i]] = true;
				Node val (ans[temp.v][i], temp.d + 1);
				
				if (dis[val.v] < val.d)
					dis[val.v] = val.d;

				q.push (val);
			}
		}

	}
}


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

	int t;
	
	cin >> t;

	while (t--)
	{
		
		int nz, nr;

		cin >> nz >> nr;

		int i;
		for (i = 0; i < maxn; i++)
			ans[i].clear ();

		for (i = 0; i < nz; i++)
		{
			int id, mz;
			cin >> id >> mz;
			
			int j, temp;
			for (j = 0; j < mz; j++)
			{
				cin >> temp;
				ans[id].push_back (temp);
			}
				
		}

		for (i = 0; i < maxn; i++)
			dis[i] = -1;

		for (i = 0; i < nr; i++)
		{
			int mr;
			cin >> mr;
			
			int j;
			for (j = 0; j < mr; j++)
			{
				int temp;
				cin >> temp;
				
				memset (visited, false, sizeof (visited));

				BFS (temp, 1);
			}
		}
		
		int minval = INF, minflag = INF;

		for (i = 0; i < maxn; i++)
			if (dis[i] != -1)
			{
				if (minval > dis[i] || (minval == dis[i] && minflag > i))
				{
					minval = dis[i];
					minflag = i;
				}
			}

		cout << minval << " " << minflag << 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

#include <iostream>

#include <fstream>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

const int maxn = 10000 + 66;

const int INF = 66666666;

int dis[maxn];

bool visited[maxn];

vector <int> ans[maxn];

struct Node

{

int v, d;

Node (int vv, int dd) : v (vv), d (dd) {}

Node () {}

};

void BFS (int v, int d)

{

queue <Node> q;

q.push(Node (v, d));

visited[v] = true;

if (dis[v] < d)

dis[v] = d;

while (!q.empty ())

{

Node temp = q.front ();

q.pop ();

int i;

for (i = 0; i < ans[temp.v].size (); i++)

{

if (!visited[ans[temp.v][i]])

{

visited[ans[temp.v][i]] = true;

Node val (ans[temp.v][i], temp.d + 1);

if (dis[val.v] < val.d)

dis[val.v] = val.d;

q.push (val);

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

int nz, nr;

cin >> nz >> nr;

int i;

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

ans[i].clear ();

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

{

int id, mz;

cin >> id >> mz;

int j, temp;

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

{

cin >> temp;

ans[id].push_back (temp);

}

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

dis[i] = -1;

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

{

int mr;

cin >> mr;

int j;

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

{

int temp;

cin >> temp;

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

BFS (temp, 1);

}

int minval = INF, minflag = INF;

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

if (dis[i] != -1)

{

if (minval > dis[i] || (minval == dis[i] && minflag > i))

{

minval = dis[i];

minflag = i;

}

cout << minval << " " << minflag << endl;

}

return 0;

}

zoj2797

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

11 9月 2015

106 miles to Chicago

In the movie "Blues Brothers", the orphanage where Elwood and Jack were raised may be sold to the Board of Education if they do not pay 5000 dollars in taxes at the Cook Country Assessor's Office in Chicago. After playing a gig in the Palace Hotel ballroom to earn these 5000 dollars, they have to find a way to Chicago. However, this is not so easy as it sounds, since they are chased by the Police, a country band and a group of Nazis. Moreover, it is 106 miles to Chicago, it is dark and they are wearing sunglasses.
As they are on a mission from God, you should help them find the safest way to Chicago. In this problem, the safest way is considered to be the route which maximises the probability that they are not caught.

Input Specification

The input file contains several test cases.
Each test case starts with two integers n and m (2 ≤ n ≤ 100 , 1 ≤ m ≤ n*(n-1)/2). n is the number of intersections, m is the number of streets to be considered.
The next m lines contain the description of the streets. Each street is described by a line containing 3 integers a, b and p (1 ≤ a, b ≤ n , a ≠ b, 1 ≤ p ≤ 100): aand b are the two end points of the street and p is the probability in percent that the Blues Brothers will manage to use this street without being caught. Each street can be used in both directions. You may assume that there is at most one street between two end points.
The last test case is followed by a zero.

Output Specification

For each test case, calculate the probability of the safest path from intersection 1 (the Palace Hotel) to intersection n (the Honorable Richard J. Daley Plaza in Chicago). You can assume that there is at least one path between intersection 1 and n.
Print the probability as a percentage with exactly 6 digits after the decimal point. The percentage value is considered correct if it differs by at most 10^-6 from the judge output. Adhere to the format shown below and print one line for each test case.

Sample Input

5 7

5 2 100

3 5 80

2 3 70

2 1 50

3 4 90

4 1 85

3 1 70

Sample Output

61.200000 percent

The safest path for the sample input is 1 -> 4 -> 3 -> 5

题目类型：单源最长路径(Floyd)

算法分析：Floyd算法的递推方程为：edge[i][j] = max (edge[i][j], edge[i][k] * edge[k][j])，本题也可以使用Bellman-ford算法计算，并且效率更高。注意邻接阵edge初始化应全为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 = 266;
const int INF = 0x7FFFFFFF;

double edge[maxn][maxn];
int n, m;

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] = max (edge[i][j], edge[i][k] * edge[k][j]);
        }
    }
}


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


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

        cin >> m;

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

        for (i = 0; i < m; i++)
        {
            int val_a, val_b, val_w;
            cin >> val_a >> val_b >> val_w;
            edge[val_a][val_b] = val_w / 100.0;
            edge[val_b][val_a] = val_w / 100.0;
        }

        floyd ();


        cout << fixed << setprecision (6) << edge[1][n] * 100 << " percent" << 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 = 266;

const int INF = 0x7FFFFFFF;

double edge[maxn][maxn];

int n, m;

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] = max (edge[i][j], edge[i][k] * edge[k][j]);

}

int main()

{

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

while (cin >> n)

{

if (n == 0)

break;

cin >> m;

int i, j;

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

{

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

{

edge[i][j] = 0;

}

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

{

int val_a, val_b, val_w;

cin >> val_a >> val_b >> val_w;

edge[val_a][val_b] = val_w / 100.0;

edge[val_b][val_a] = val_w / 100.0;

}

floyd ();

cout << fixed << setprecision (6) << edge[1][n] * 100 << " percent" << endl;

}

return 0;

}

zoj2750

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

11 9月 2015

Idiomatic Phrases Game

Tom is playing a game called Idiomatic Phrases Game. An idiom consists of several Chinese characters and has a certain meaning. This game will give Tom two idioms. He should build a list of idioms and the list starts and ends with the two given idioms. For every two adjacent idioms, the last Chinese character of the former idiom should be the same as the first character of the latter one. For each time, Tom has a dictionary that he must pick idioms from and each idiom in the dictionary has a value indicates how long Tom will take to find the next proper idiom in the final list. Now you are asked to write a program to compute the shortest time Tom will take by giving you the idiom dictionary.

Input

The input consists of several test cases. Each test case contains an idiom dictionary. The dictionary is started by an integer N (0 < N < 1000) in one line. The following is N lines. Each line contains an integer T (the time Tom will take to work out) and an idiom. One idiom consists of several Chinese characters (at least 3) and one Chinese character consists of four hex digit (i.e., 0 to 9 and A to F). Note that the first and last idioms in the dictionary are the source and target idioms in the game. The input ends up with a case that N = 0. Do not process this case.

Output

One line for each case. Output an integer indicating the shortest time Tome will take. If the list can not be built, please output -1.

Sample Input

5 12345978ABCD2341

5 23415608ACBD3412

7 34125678AEFD4123

15 23415673ACC34123

4 41235673FBCD2156

20 12345678ABCD

30 DCBF5432167D

Sample Output

-1

题目类型：单源最短路

算法分析：读入短语并分析得出前4位和后4位的值from和to，然后按照得到的是from和to来建立edge邻接阵，最后调用dijkstra算法判断最后一个节点的最短路径dis[n-1]情况即可。注意对于有向图的邻接阵来说，不能只考虑矩阵上三角中元素的情况！！！！！！

#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 = 1000 + 66;
const int INF = 66666666;


struct Node
{
    int w;
    char from[8], to[8];
};

Node dict[maxn];

int edge[maxn][maxn];
int dis[maxn];
bool is_visited[maxn];
int n;
char input_val[666];

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

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

    is_visited[0] = true;
    dis[0] = 0;

    for (i = 1; i < n; i++)
    {
        int j, minval = INF, index = 0;
        for (j = 1; j < n; j++)
        {

            if (!is_visited[j] && dis[j] < minval)
            {
                minval = dis[j];
                index = j;
            }
        }

        is_visited[index] = true;

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

    if (dis[n-1] == INF)
        cout << "-1" << endl;

    else
        cout << dis[n-1] << endl;
}


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

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

        int i;
        int input_w;


        for (i = 0; i < n; i++)
        {
            cin >> input_w >> input_val;

            int j, k, len = strlen (input_val);
            for (j = 0, k = len - 4; j < 4; j++, k++)
            {
                dict[i].from[j] = input_val[j];
                dict[i].to[j] = input_val[k];
            }

            dict[i].from[4] = dict[i].to[4] = 0;
            dict[i].w = input_w;
        }

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

                if (i == j)
                    continue;

                if (!strcmp (dict[i].to, dict[j].from))
                    edge[i][j] = dict[i].w;
            }
        }

        Dijkstra ();
    }

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

#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 = 1000 + 66;

const int INF = 66666666;

struct Node

{

int w;

char from[8], to[8];

};

Node dict[maxn];

int edge[maxn][maxn];

int dis[maxn];

bool is_visited[maxn];

int n;

char input_val[666];

void Dijkstra ()

{

int i;

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

dis[i] = edge[0][i];

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

is_visited[0] = true;

dis[0] = 0;

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

{

int j, minval = INF, index = 0;

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

{

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

{

minval = dis[j];

index = j;

}

is_visited[index] = true;

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

{

if (!is_visited[j] && edge[index][j] < INF && dis[j] > dis[index] + edge[index][j])

{

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

}

if (dis[n-1] == INF)

cout << "-1" << endl;

else

cout << dis[n-1] << endl;

}

int main()

{

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

while (cin >> n)

{

if (n == 0)

break;

int i;

int input_w;

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

{

cin >> input_w >> input_val;

int j, k, len = strlen (input_val);

for (j = 0, k = len - 4; j < 4; j++, k++)

{

dict[i].from[j] = input_val[j];

dict[i].to[j] = input_val[k];

}

dict[i].from[4] = dict[i].to[4] = 0;

dict[i].w = input_w;

}

int j;

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

{

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

{

edge[i][j] = INF;

if (i == j)

continue;

if (!strcmp (dict[i].to, dict[j].from))

edge[i][j] = dict[i].w;

}

Dijkstra ();

}

return 0;

}

zoj2412

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

11 9月 2015

Farm Irrigation

Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has a different type of pipe. There are 11 types of pipes, which is marked from A to K, as Figure 1 shows.
Figure 1

Benny has a map of his farm, which is an array of marks denoting the distribution of water pipes over the whole farm. For example, if he has a map

ADC

FJK

IHE

then the water pipes are distributed like
Figure 2

Several wellsprings are found in the center of some squares, so water can flow along the pipes from one square to another. If water flow crosses one square, the whole farm land in this square is irrigated and will have a good harvest in autumn.

Now Benny wants to know at least how many wellsprings should be found to have the whole farm land irrigated. Can you help him?

Note: In the above example, at least 3 wellsprings are needed, as those red points in Figure 2 show.

Input

There are several test cases! In each test case, the first line contains 2 integers M and N, then M lines follow. In each of these lines, there are N characters, in the range of 'A' to 'K', denoting the type of water pipe over the corresponding square. A negative M or N denotes the end of input, else you can assume 1 <= M, N <= 50.

Output

For each test case, output in one line the least number of wellsprings needed.

Sample Input

2 2

3 3

ADC

FJK

IHE

-1 -1

Sample Output

题目类型：DFS/BFS

算法分析：统计程序中调用的DFS/BFS的次数即可，搜索中判断转移的过程是当前所在位置存在向周围的4个方向移动的水管，然后再判断移动后的位置的水管是否有与移动前的位置的水管相反的(既保证相邻草坪存在水管路径)。注意可以使用%运算来简化代码

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

const int maxn = 100 + 36;

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

const bool flag[26][6] = {
  {1, 0, 0, 1}
, {1, 1, 0, 0}
, {0, 0, 1, 1}
, {0, 1, 1, 0}
, {1, 0, 1, 0}
, {0, 1, 0, 1}
, {1, 1, 0, 1}
, {1, 0, 1, 1}
, {0, 1, 1, 1}
, {1, 1, 1, 0}
, {1, 1, 1, 1}};

char ans[maxn][maxn];
bool visited[maxn][maxn];
int row, col;

inline bool OkMove (int x, int y, int val)
{
	if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y] 
		&& flag[ans[x-dx[val]][y-dy[val]]-'A'][val] && flag[ans[x][y]-'A'][(val+2)%4])
		return true;

return false;
}


void DFS (int x, int y)
{
	int i;
	for (i = 0; i < 4; i++)
	{
		if (OkMove (x + dx[i], y + dy[i], i))
		{
			int val_x = x + dx[i], val_y = y + dy[i];
			visited[val_x][val_y] = true;
			DFS (val_x, val_y);
		}
	}
}


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

	while (cin >> row >> col)
	{
		if (row < 0 || col < 0)
			break;

		int i;
		for (i = 0; i < row; i++)
			cin >> ans[i];

		int sum = 0, j;
		memset (visited, false, sizeof (visited));

		for (i = 0; i < row; i++)
			for (j = 0; j < col; j++)
				if (!visited[i][j])
				{
					visited[i][j] = true;
					DFS (i, j);
					sum++;
				}

		cout << sum << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 100 + 36;

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

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

const bool flag[26][6] = {

{1, 0, 0, 1}

, {1, 1, 0, 0}

, {0, 0, 1, 1}

, {0, 1, 1, 0}

, {1, 0, 1, 0}

, {0, 1, 0, 1}

, {1, 1, 0, 1}

, {1, 0, 1, 1}

, {0, 1, 1, 1}

, {1, 1, 1, 0}

, {1, 1, 1, 1}};

char ans[maxn][maxn];

bool visited[maxn][maxn];

int row, col;

inline bool OkMove (int x, int y, int val)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && !visited[x][y]

&& flag[ans[x-dx[val]][y-dy[val]]-'A'][val] && flag[ans[x][y]-'A'][(val+2)%4])

return true;

return false;

}

void DFS (int x, int y)

{

int i;

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

{

if (OkMove (x + dx[i], y + dy[i], i))

{

int val_x = x + dx[i], val_y = y + dy[i];

visited[val_x][val_y] = true;

DFS (val_x, val_y);

}

int main()

{

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

while (cin >> row >> col)

{

if (row < 0 || col < 0)

break;

int i;

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

cin >> ans[i];

int sum = 0, j;

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

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

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

if (!visited[i][j])

{

visited[i][j] = true;

DFS (i, j);

sum++;

}

cout << sum << endl;

}

return 0;

}

zoj2193

maksyuki 发表于 oj 分类，标签: 图论-拓扑排序

11 9月 2015

Window Pains

Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows:

1	1	.	.
1	1	.	.
.	.	.	.
.	.	.	.

.	2	2	.
.	2	2	.
.	.	.	.
.	.	.	.

.	.	3	3
.	.	3	3
.	.	.	.
.	.	.	.

.	.	.	.
4	4	.	.
4	4	.	.
.	.	.	.

.	.	.	.
.	5	5	.
.	5	5	.
.	.	.	.

.	.	.	.
.	.	6	6
.	.	6	6
.	.	.	.

.	.	.	.
.	.	.	.
7	7	.	.
7	7	.	.

.	.	.	.
.	.	.	.
.	8	8	.
.	8	8	.

.	.	.	.
.	.	.	.
.	.	9	9
.	.	9	9

When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1 and then window 2 were brought to the foreground, the resulting representation would be:

1	2	2	?
1	2	2	?
?	?	?	?
?	?	?	?

If window 4 were then brought to the foreground:

1	2	2	?
4	4	2	?
4	4	?	?
?	?	?	?

. . . and so on . . .

Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

Start line - A single line:

START

Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
End line - A single line:

After the last data set, there will be a single line:

ENDOFINPUT

Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement:

THESE WINDOWS ARE CLEAN

Otherwise, the output will be a single line with the statement:

THESE WINDOWS ARE BROKEN

Sample Input

START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN

题目类型：拓扑排序

算法分析：由于输入中的窗口是最靠外面的，且题目中说调动了所有的窗口。这就意味着最外面的窗口中的数字覆盖了其他在该位置处的数字，使用这种覆盖关系构造有向图。首先构造9个窗口，然后对于输入的窗口中的每一个位置处的数字a遍历所有的9个窗口在该位置的取值vi，如果在该处存在值vi且不与a相等，则构造一条有向边，起点为a，终点为vi。最后对于构造好的有向图使用拓扑排序即可

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

const int maxn = 16;

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

int ans[maxn][maxn];
int num[maxn][maxn][maxn];
int indegree[maxn];

bool is_valid;

vector <int> vec[maxn];

void Build ()
{
	int i;
	for (i = 0; i < 9; i++)
	{
		int val_x = i / 3, val_y = i % 3, j; // important!!!!!!
		
		for (j = 0; j < 4; j++)
			num[i][val_x+dx[j]][val_y+dy[j]] = i + 1;
	}
}

void Solve ()
{
	int i, j, k;
	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
			for (k = 0; k < 9; k++)
			{
				if (num[k][i][j] && ans[i][j] != num[k][i][j])
				{
					indegree[num[k][i][j]]++;
					vec[ans[i][j]].push_back (num[k][i][j]);
				}
			}
}

void Topo ()
{
	is_valid = true;
	queue <int> q;

	int i;
	for (i = 1; i <= 9; i++)
		if (!indegree[i])
			q.push (i);

	while (!q.empty ())
	{
		int temp = q.front ();
		q.pop ();

		for (i = 0; i < vec[temp].size (); i++)
		{
			indegree[vec[temp][i]]--;
			
			if (!indegree[vec[temp][i]])
				q.push (vec[temp][i]);
		}
	}

	for (i = 1; i <= 9; i++)
		if (indegree[i])
			break;

	if (i <= 9)
		is_valid = false;

}


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

	char input[36];
	
	memset (num, 0, sizeof (num));
	Build ();

	while (cin >> input)
	{
		if (!strcmp (input, "ENDOFINPUT"))
			break;

		int i;
		for (i = 0; i < 4; i++)
		{
			int j;
			for (j = 0; j < 4; j++)
				cin >> ans[i][j];
		}

		cin >> input;
		
		for (i = 0; i < maxn; i++)
			vec[i].clear ();

		memset (indegree, 0, sizeof (indegree));

		Solve ();
		
		Topo ();

		if (is_valid)
			cout << "THESE WINDOWS ARE CLEAN" << endl;

		else
			cout << "THESE WINDOWS ARE BROKEN" << 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

#include <iostream>

#include <fstream>

#include <cstring>

#include <queue>

#include <vector>

using namespace std;

const int maxn = 16;

const int dx[] = {0, 1, 0, 1};

const int dy[] = {0, 1, 1, 0};

int ans[maxn][maxn];

int num[maxn][maxn][maxn];

int indegree[maxn];

bool is_valid;

vector <int> vec[maxn];

void Build ()

{

int i;

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

{

int val_x = i / 3, val_y = i % 3, j; // important!!!!!!

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

num[i][val_x+dx[j]][val_y+dy[j]] = i + 1;

}

void Solve ()

{

int i, j, k;

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

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

for (k = 0; k < 9; k++)

{

if (num[k][i][j] && ans[i][j] != num[k][i][j])

{

indegree[num[k][i][j]]++;

vec[ans[i][j]].push_back (num[k][i][j]);

}

void Topo ()

{

is_valid = true;

queue <int> q;

int i;

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

if (!indegree[i])

q.push (i);

while (!q.empty ())

{

int temp = q.front ();

q.pop ();

for (i = 0; i < vec[temp].size (); i++)

{

indegree[vec[temp][i]]--;

if (!indegree[vec[temp][i]])

q.push (vec[temp][i]);

}

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

if (indegree[i])

break;

if (i <= 9)

is_valid = false;

}

int main()

{

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

char input[36];

memset (num, 0, sizeof (num));

Build ();

while (cin >> input)

{

if (!strcmp (input, "ENDOFINPUT"))

break;

int i;

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

{

int j;

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

cin >> ans[i][j];

}

cin >> input;

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

vec[i].clear ();

memset (indegree, 0, sizeof (indegree));

Solve ();

Topo ();

if (is_valid)

cout << "THESE WINDOWS ARE CLEAN" << endl;

else

cout << "THESE WINDOWS ARE BROKEN" << endl;

}

return 0;

}

zoj2110

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

11 9月 2015

Tempter of the Bone

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.

The input is terminated with three 0's. This test case is not to be processed.
Output

For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

Sample Output

NO
YES

题目类型：DFS +剪枝

算法分析：原本是一道简单的DFS题目，但是需要注意搜索的效率，如果直接使用DFS会超时，所以重点是使用剪枝，剪枝的地方是对于搜索点到目标点的距离所用时间已经大于实际提供的时间，就不再向下搜索。另一个重要的剪枝(只有前一个剪枝仍会TLE)是前两个时间之差必须是偶数，即意味着两个时间必须是同奇偶的才有可能找到结果，事实上第二个剪枝的所剪掉的无用搜索更多，只用第二个剪枝程序仍能AC

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

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

const int maxn = 36 + 6;

char ans[maxn][maxn];
bool visited[maxn][maxn];

int n, m, t;
int s_x, s_y, e_x, e_y;

bool is_valid;

bool OkMove (int x, int y)
{
	if (x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1 && ans[x][y] != 'X' && !visited[x][y])
		return true;

return false;
}


void DFS (int x, int y, int cnt)
{
	if (x == e_x && y == e_y && cnt == t)
	{
		is_valid = true;
		return ;
	}
	
	int temp = (t - cnt) - abs (x - e_x) - abs (y - e_y);
	if (temp < 0 || temp % 2)
		return ;
	
	int i;
	for (i = 0; i < 4; i++)
	{
		if (OkMove (x + dx[i], y + dy[i]))
		{
			int temp_x = x + dx[i], temp_y = y + dy[i];

			visited[temp_x][temp_y] = true;
			DFS (temp_x, temp_y, cnt + 1);
			visited[temp_x][temp_y] = false;
		}
	}
}


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

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

		int i, j;
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++)
			{
				cin >> ans[i][j];
				
				if (ans[i][j] == 'S')
				{
					s_x = i;
					s_y = j;
				}

				if (ans[i][j] == 'D')
				{
					e_x = i;
					e_y = j;
				}
			}
		
		is_valid = false;
		memset (visited, false, sizeof (visited));

		visited[s_x][s_y] = true;

		DFS (s_x, s_y, 0);

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

		else
			cout << "NO" << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

using namespace std;

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

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

const int maxn = 36 + 6;

char ans[maxn][maxn];

bool visited[maxn][maxn];

int n, m, t;

int s_x, s_y, e_x, e_y;

bool is_valid;

bool OkMove (int x, int y)

{

if (x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1 && ans[x][y] != 'X' && !visited[x][y])

return true;

return false;

}

void DFS (int x, int y, int cnt)

{

if (x == e_x && y == e_y && cnt == t)

{

is_valid = true;

return ;

}

int temp = (t - cnt) - abs (x - e_x) - abs (y - e_y);

if (temp < 0 || temp % 2)

return ;

int i;

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

{

if (OkMove (x + dx[i], y + dy[i]))

{

int temp_x = x + dx[i], temp_y = y + dy[i];

visited[temp_x][temp_y] = true;

DFS (temp_x, temp_y, cnt + 1);

visited[temp_x][temp_y] = false;

}

int main()

{

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

while (cin >> n >> m >> t)

{

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

break;

int i, j;

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

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

{

cin >> ans[i][j];

if (ans[i][j] == 'S')

{

s_x = i;

s_y = j;

}

if (ans[i][j] == 'D')

{

e_x = i;

e_y = j;

}

is_valid = false;

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

visited[s_x][s_y] = true;

DFS (s_x, s_y, 0);

if (is_valid)

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

zoj2016

maksyuki 发表于 oj 分类，标签: 图论-欧拉回路

11 9月 2015

Play on Words

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word "acm" can be followed by the word "motorola". Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input

The input consists of T test cases. The number of them (T) is given on the first line of the input. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output

Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.

If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

题目类型：欧拉回路的判定

算法分析：将每个单词的第一个字符和最后一个字符取出来作为节点，构建一个从第一个字符到最后一个字符的有向边，统计初度和入度的大小。然后判断有向图的基图是否连通(使用并查集)，然后再按照定义判断欧拉回路和欧拉路径是否存在

#include <iostream>
#include <fstream>
#include <sstream>
#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 INF = 0x7FFFFFFF;
const int maxn = 1666;

char s[maxn];
int ind[36], oud[36], parent[36];
bool used[36];

int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}


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

    int t;
    scanf ("%d", &t);

    while (t--)
    {
        int n;
        scanf ("%d", &n);

        int i;
        for (i = 0; i < 26; i++)
            parent[i] = i;

        memset (ind, 0, sizeof (ind));
        memset (oud, 0, sizeof (oud));
        memset (used, false, sizeof (used));

        for (i = 0; i < n; i++)
        {
            scanf ("%s", s);
            int len = strlen (s);
            ind[s[len-1]-'a']++;
            oud[s[0]-'a']++;
            used[s[len-1]-'a'] = used[s[0]-'a'] = true;

            if (UnFind (s[len-1] - 'a') != UnFind (s[0] - 'a'))
            {
                parent[UnFind(s[len-1]-'a')] = UnFind (s[0] - 'a');
            }
        }

        bool is_valid = true;
        int temp;

        for (i = 0; i < 26; i++)
            if (used[i])
            {
                temp = UnFind (i);
                break;
            }

        for (i = 0; i < 26; i++)
            if (used[i] && temp != UnFind (i))
            {
                is_valid = false;
                break;
            }


        int dif = 0, val_ind = 0, val_oud = 0;

        for (i = 0; i < 26; i++)
        {
            if (used[i] && ind[i] != oud[i])
            {
                dif++;
                if (ind[i] - oud[i] == 1)
                    val_ind++;

                if (ind[i] - oud[i] == -1)
                    val_oud++;
            }
        }

        if (dif != 0 && dif != 2)
            is_valid = false;

        if (dif == 2)
        {
            if (val_ind != 1 || val_oud != 1)
                is_valid = false;
        }


        if (is_valid)
            printf ("Ordering is possible.\n");

        else
            printf ("The door cannot be opened.\n");

    }
return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <iostream>

#include <fstream>

#include <sstream>

#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 INF = 0x7FFFFFFF;

const int maxn = 1666;

char s[maxn];

int ind[36], oud[36], parent[36];

bool used[36];

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

int main()

{

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

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d", &n);

int i;

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

parent[i] = i;

memset (ind, 0, sizeof (ind));

memset (oud, 0, sizeof (oud));

memset (used, false, sizeof (used));

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

{

scanf ("%s", s);

int len = strlen (s);

ind[s[len-1]-'a']++;

oud[s[0]-'a']++;

used[s[len-1]-'a'] = used[s[0]-'a'] = true;

if (UnFind (s[len-1] - 'a') != UnFind (s[0] - 'a'))

{

parent[UnFind(s[len-1]-'a')] = UnFind (s[0] - 'a');

}

bool is_valid = true;

int temp;

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

if (used[i])

{

temp = UnFind (i);

break;

}

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

if (used[i] && temp != UnFind (i))

{

is_valid = false;

break;

}

int dif = 0, val_ind = 0, val_oud = 0;

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

{

if (used[i] && ind[i] != oud[i])

{

dif++;

if (ind[i] - oud[i] == 1)

val_ind++;

if (ind[i] - oud[i] == -1)

val_oud++;

}

if (dif != 0 && dif != 2)

is_valid = false;

if (dif == 2)

{

if (val_ind != 1 || val_oud != 1)

is_valid = false;

}

if (is_valid)

printf ("Ordering is possible.\n");

else

printf ("The door cannot be opened.\n");

}

return 0;

}

zoj1967

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

11 9月 2015

Fiber Network

Several startup companies have decided to build a better Internet, called the "FiberNet". They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes.

Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.
Input

The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n = 0. Otherwise, 1 <= n <= 200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A = B = 0. Otherwise, 1 <= A, B <= n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.

After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A = B = 0. Otherwise, 1 <= A, B <= n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.
Output

For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output "-" instead. Output a blank line after each test case.
Sample Input

3
1 2 abc
2 3 ad
1 3 b
3 1 de
0 0
1 3
2 1
3 2
0 0
2
1 2 z
0 0
1 2
2 1
0 0
0
Sample Output

ab
d
-

z
-

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

算法分析：使用Floyd算法的迭代思想，矩阵ans[i][j]中存放的是节点i到节点j中存在的公司集合(字符串)。使用位运算的相关技巧，用从低到高的26个二进制位表示两点之间存在的公司(1位)的情况。对于每一次迭代，使用ans[i][j] = 集合或运算(ans[i][j], ans[i][k] 集合与运算ans[k][j])。然后对于每个查询直接输出结果即可

#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;

int ans[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++)
            {
                ans[i][j] |= (ans[i][k] & ans[k][j]);
            }
        }
    }
}


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

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

        int i;
        int val_a, val_b;
        char input[36];

        memset (ans, 0, sizeof (ans));

        while (cin >> val_a >> val_b)
        {
            if (val_a == 0 && val_b == 0)
                break;

            cin >> input;

            int j;
            for (j = 0; input[j]; j++)
                ans[val_a][val_b] |= 1 << (input[j] - 'a');
        }

        floyd ();

        while (cin >> val_a >> val_b)
        {
            if (val_a == 0 && val_b == 0)
                break;

            for (i = 0; i < 26; i++)
            {
                if (ans[val_a][val_b] & (1 << i))
                    cout << (char) (i + 'a');
            }

            if (!ans[val_a][val_b])
                cout << "-" << endl;

            else
                cout << 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 = 666 + 66;

int ans[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++)

{

ans[i][j] |= (ans[i][k] & ans[k][j]);

}

int main()

{

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

while (cin >> n)

{

if (n == 0)

break;

int i;

int val_a, val_b;

char input[36];

memset (ans, 0, sizeof (ans));

while (cin >> val_a >> val_b)

{

if (val_a == 0 && val_b == 0)

break;

cin >> input;

int j;

for (j = 0; input[j]; j++)

ans[val_a][val_b] |= 1 << (input[j] - 'a');

}

floyd ();

while (cin >> val_a >> val_b)

{

if (val_a == 0 && val_b == 0)

break;

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

{

if (ans[val_a][val_b] & (1 << i))

cout << (char) (i + 'a');

}

if (!ans[val_a][val_b])

cout << "-" << endl;

else

cout << endl;

}

cout << endl;

}

return 0;

}

zoj1952

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

11 9月 2015

Heavy Cargo

Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.

Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.
Input

The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2 <= n <= 200) and the number of road segments r (1 <= r <= 19900) making up the street network.

Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.

The last line of the test case contains two city names: start and destination.

Input will be terminated by two values of 0 for n and r.
Output

For each test case, print three lines:

a line saying "Scenario #x" where x is the number of the test case
a line saying "y tons" where y is the maximum possible load
a blank line

Sample Input

4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0
Sample Output

Scenario #1
80 tons

Scenario #2
170 tons

题目类型：Floyd思想

算法分析：以读入的字符串构建图，然后使用Floyd算法思想来迭代求解，迭代公式为：edge[i][j] = max (edge[i][j], min (edge[i][k], edge[k][j]))。注意一定要初始化edge[i][j]数组，其中i == j时，edge[i][j] == INF，表示自己到自己的路径上载重无限制。当i != j时，edge[i][j] == 0，表示i到j的路径上载重限制为无穷

#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;

int edge[maxn][maxn];
int n, r;

vector <string> vec;

int GetVal (string val)
{
    int i;
    for (i = 0; i < vec.size (); i++)
        if (val == vec[i])
            return i;

    vec.push_back (val);

return i;
}


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

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

    int flag = 1;

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

        vec.clear ();

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

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


        string val_a, val_b;
        int val_w;
        for (i = 0; i < r; i++)
        {
            cin >> val_a >> val_b >> val_w;
            int u = GetVal (val_a);
            int v = GetVal (val_b);
            edge[u][v] = val_w;
            edge[v][u] = val_w;
        }

        floyd ();

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

        cin >> val_a >> val_b;
        int u = GetVal (val_a);
        int v = GetVal (val_b);

        cout << edge[u][v] << " tons" << endl << endl;
    }

return 0;
}

100

#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;

int edge[maxn][maxn];

int n, r;

vector <string> vec;

int GetVal (string val)

{

int i;

for (i = 0; i < vec.size (); i++)

if (val == vec[i])

return i;

vec.push_back (val);

return i;

}

void floyd ()

{

int i, j, k;

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

{

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

{

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

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

}

int main()

{

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

int flag = 1;

while (cin >> n >> r)

{

if (n == 0 && r == 0)

break;

vec.clear ();

int i, j;

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

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

{

if (i == j)

edge[i][j] = INF;

else

edge[i][j] = 0;

}

string val_a, val_b;

int val_w;

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

{

cin >> val_a >> val_b >> val_w;

int u = GetVal (val_a);

int v = GetVal (val_b);

edge[u][v] = val_w;

edge[v][u] = val_w;

}

floyd ();

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

cin >> val_a >> val_b;

int u = GetVal (val_a);

int v = GetVal (val_b);

cout << edge[u][v] << " tons" << endl << endl;

}

return 0;

}

zoj1948

maksyuki 发表于 oj 分类，标签: 数据结构-队列\双端\单调\优先

11 9月 2015

Team Queue

Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example.

In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.

Your task is to write a program that simulates such a team queue.
Input

The input will contain one or more test cases. Each test case begins with the number of teams t (1<=t<=1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0 - 999999. A team may consist of up to 1000 elements.

Finally, a list of commands follows. There are three different kinds of commands:

ENQUEUE x - enter element x into the team queue
DEQUEUE - process the first element and remove it from the queue
STOP - end of test case

The input will be terminated by a value of 0 for t.

Output

For each test case, first print a line saying "Scenario #k", where k is the number of the test case. Then, for each DEQUEUE command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one.
Sample Input

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0
Sample Output

Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

题目类型：队列模拟

算法分析：使用map<int, int> team来表示成员的团队标志，使用一个队列表示团队队列，使用一个队列数组表示子团队的队列。先输入所有成员的团队标志，然后分类模拟，如果是”STOP”；则退出模拟；如果是”ENQUEUE”，则将新成员输入并判断其所在的团队是否在团队队列中，如果不在就将所在团队插入到团队队列中，然后将新成员插入到子团队的队列中；如果是”DEQUEUE”，则先输出团队队列队头成员并删除，接着判断被删除成员先前所在的子团队队列是否为空，如果为空，则从团队队列中删除该子队列

#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 = 1000 + 66;

int team[999999+6];


int main()
{
    int flag = 1;

//	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++)
        {
            int num;
            cin >> num;

            int j, temp;
            for (j = 0; j < num; j++)
            {
                cin >> temp;
                team[temp] = i;
            }
        }

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

        string input;
        queue <int> tq, q[maxn];

        while (cin >> input)
        {
            if (input == "STOP")
                break;

            if (input == "ENQUEUE")
            {
                int temp;
                cin >> temp;
                int val = team[temp];
                if (q[val].empty ())
                    tq.push (val);

                q[val].push (temp);
            }

            else if (input == "DEQUEUE")
            {
                if (!tq.empty ())
                {
                    int temp = tq.front ();
                    cout << q[temp].front () << endl;
                    q[temp].pop ();
                    if (q[temp].empty ())
                        tq.pop ();
                }
            }
        }
        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 = 1000 + 66;

int team[999999+6];

int main()

{

int flag = 1;

// 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++)

{

int num;

cin >> num;

int j, temp;

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

{

cin >> temp;

team[temp] = i;

}

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

string input;

queue <int> tq, q[maxn];

while (cin >> input)

{

if (input == "STOP")

break;

if (input == "ENQUEUE")

{

int temp;

cin >> temp;

int val = team[temp];

if (q[val].empty ())

tq.push (val);

q[val].push (temp);

}

else if (input == "DEQUEUE")

{

if (!tq.empty ())

{

int temp = tq.front ();

cout << q[temp].front () << endl;

q[temp].pop ();

if (q[temp].empty ())

tq.pop ();

}

cout << endl;

}

return 0;

}

zoj1942

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

11 9月 2015

Frogger

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

题目类型：最大容量路(Floyd思想)

算法分析：将读入的坐标转换为邻接阵中的权值，然后使用Floyd算法迭代n - 1次插点计算最大容量，其中更新方程为：edge[i][j] = min (edge[i][j], max (edge[i][k], edge[k][j]))

#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 = 0x7fffffff;
const double EPS = 1e-6;

struct Node
{
    int x, y;
};

Node ans[maxn];

double edge[maxn][maxn];
int n;

void floyd ()
{
    int i, j, k;

    for (k = 0; k < n; k++)
    {
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
                edge[i][j] = min (edge[i][j], max (edge[i][k], edge[k][j]));
        }
    }
}


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

    int flag = 1;

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

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

        int j;

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

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

        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                double temp = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2));
                edge[i][j] = temp;
                edge[j][i] = temp;
            }
        }

        floyd ();

        cout << "Scenario #" << flag++ << endl;
        cout << "Frog Distance = " << fixed << setprecision (3) << edge[0][1] << endl << 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 = 666 + 66;

const int INF = 0x7fffffff;

const double EPS = 1e-6;

struct Node

{

int x, y;

};

Node ans[maxn];

double edge[maxn][maxn];

int n;

void floyd ()

{

int i, j, k;

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

{

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

{

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

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

}

int main()

{

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

int flag = 1;

while (cin >> n)

{

if (n == 0)

break;

int i;

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

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

int j;

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

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

{

if (i == j)

edge[i][j] = 0;

else

edge[i][j] = INF;

}

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

{

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

{

double temp = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2));

edge[i][j] = temp;

edge[j][i] = temp;

}

floyd ();

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

cout << "Frog Distance = " << fixed << setprecision (3) << edge[0][1] << endl << endl;

}

return 0;

}

zoj1718

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

11 9月 2015

Building a Space Station

You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write a computer program to complete the task.

The space station is made up with a number of units, called cells. All cells are sphere-shaped, but their sizes are not necessarily uniform. Each cell is fixed at its predetermined position shortly after the station is successfully put into its orbit. It is quite strange that two cells may be touching each other, or even may be overlapping. In an extreme case, a cell may be totally enclosing another one. I do not know how such arrangements are possible.

All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor', or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively.

You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors.

You can ignore the width of a corridor. A corridor is built between points on two cells' surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.
Input

The input consists of multiple data sets. Each data set is given in the following format.

n
x1 y1 z1 r1
x2 y2 z2 r2
...
xn yn zn rn

The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.

The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.

Each of x, y, z and r is positive and is less than 100.0.

The end of the input is indicated by a line containing a zero.
Output

For each data set, the shortest total length of the corridors should be printed, each in a separate line. The printed values should have 3 digits after the decimal point. They may not have an error greater than 0.001.

Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.
Sample Input

3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0
Sample Output

20.000
0.000
73.834

题目类型：MST

算法分析：按照题目中的数据建立边表edge，然后直接调用kruskal算法计算最小权值和即可。建立边表edge时，对于两个太空舱的圆心距小于等于两个太空舱的半径之和的情况，这两个太空舱之间的距离定义为0.000，反之，则距离定义为圆心距减去两个半径之和(表面距离)。注意浮点数误差！！！

#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 = 266 + 66;
const int EPS = 1e-6;

struct Node
{
    double x, y, z, r;
};

Node ans[maxn];
int parent[maxn];

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

Point edge[maxn*maxn];

int len, n;
double sum;

int UnFind (int val)
{
    if (parent[val] == -1)
        return val;

return parent[val] = UnFind (parent[val]);
}

bool Cmp (Point a, Point b)
{
    return a.w < b.w;
}


void kruskal ()
{
    int i;
    for (i = 0; i < maxn; i++)
        parent[i] = -1;

    sum = 0.000;
    int remain = n;
    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            sum += edge[i].w;
            remain--;
        }
    }
}


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

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

        int i;
        for (i = 0; i < n; i++)
            cin >> ans[i].x >> ans[i].y >> ans[i].z >> ans[i].r;

        len = 0;

        int j;
        for (i = 0; i < n - 1; i++)
            for (j = i + 1; j < n; j++)
            {
                edge[len].u = i;
                edge[len].v = j;

                double dis = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2)
                                   + pow (ans[i].z - ans[j].z, 2));

                if (dis > ans[i].r + ans[j].r + EPS)
                    edge[len].w = dis - (ans[i].r + ans[j].r);

                else
                    edge[len].w = 0.000;

                len++;
            }

        sort (edge, edge + len, Cmp);
        kruskal ();

        cout << fixed << setprecision (3) << sum << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#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 = 266 + 66;

const int EPS = 1e-6;

struct Node

{

double x, y, z, r;

};

Node ans[maxn];

int parent[maxn];

struct Point

{

int u, v;

double w;

};

Point edge[maxn*maxn];

int len, n;

double sum;

int UnFind (int val)

{

if (parent[val] == -1)

return val;

return parent[val] = UnFind (parent[val]);

}

bool Cmp (Point a, Point b)

{

return a.w < b.w;

}

void kruskal ()

{

int i;

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

parent[i] = -1;

sum = 0.000;

int remain = n;

for (i = 0; i < len && remain > 1; i++)

{

if (UnFind (edge[i].u) != UnFind (edge[i].v))

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

sum += edge[i].w;

remain--;

}

int main()

{

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

while (cin >> n)

{

if (n == 0)

break;

int i;

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

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

len = 0;

int j;

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

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

{

edge[len].u = i;

edge[len].v = j;

double dis = sqrt (pow (ans[i].x - ans[j].x, 2) + pow (ans[i].y - ans[j].y, 2)

+ pow (ans[i].z - ans[j].z, 2));

if (dis > ans[i].r + ans[j].r + EPS)

edge[len].w = dis - (ans[i].r + ans[j].r);

else

edge[len].w = 0.000;

len++;

}

sort (edge, edge + len, Cmp);

kruskal ();

cout << fixed << setprecision (3) << sum << endl;

}

return 0;

}

zoj1649

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

11 9月 2015

Rescue

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)
Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.
Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."
Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
Sample Output

题目类型：”有权值”的BFS

算法分析：本题使用一个mintime[x][y]二维数组来表示起点到图中(x,y)位置处的最短时间，由于最短路径中的某一个方案所得出的结果不一定最优解，所以一定要将所有的方案都搜到之后，才能输出结果。对于每一个节点，只扩展到下一个节点位置(相邻的4个方向)处所用的时间比mintime在该位置所用时间少的。BFS完成之后直接输出mintime[end_x][end_y]即可

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

const int maxn = 210 + 36;
const int INF = 66666666;

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

struct Node
{
	int x, y, t;
	
	Node (int xx, int yy, int tt) : x (xx), y (yy), t (tt) {}
};

char ans[maxn][maxn];
int mintime[maxn][maxn];

int row, col, s_x, s_y, e_x, e_y;

inline bool OkMove (int x, int y)
{
	if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && ans[x][y] != '#')
		return true;

return false;
}


void BFS (int x, int y, int t)
{
	queue <Node> q;
	q.push (Node (x, y, t));
	mintime[x][y] = 0;

	while (!q.empty ())
	{
		Node temp = q.front ();
		q.pop ();
	
		int i;
		for (i = 0; i < 4; i++)
		{
			if (OkMove (temp.x + dx[i], temp.y + dy[i]))
			{
				Node val (temp.x + dx[i], temp.y + dy[i], temp.t + 1);

				if (ans[val.x][val.y] == 'x')
					val.t++;

				if (mintime[val.x][val.y] > val.t)
				{
					mintime[val.x][val.y] = val.t;
					q.push (Node (val.x, val.y, val.t));
				}
			}
		
		}
	}
}


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

	while (cin >> row >> col)
	{
		int i, j;
		for (i = 0; i < row; i++)
			for (j = 0; j < col; j++)
			{
				cin >> ans[i][j];
				
				mintime[i][j] = INF;

				if (ans[i][j] == 'a')
				{
					s_x = i;
					s_y = j;
				}

				else if (ans[i][j] == 'r')
				{
					e_x = i;
					e_y = j;
				}
			}

		BFS (s_x, s_y, 0);

		if (mintime[e_x][e_y] == INF)
			cout << "Poor ANGEL has to stay in the prison all his life." << endl;

		else
			cout << mintime[e_x][e_y] << endl;
	}

return 0;
}

100

101

102

103

104

#include <iostream>

#include <fstream>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = 210 + 36;

const int INF = 66666666;

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

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

struct Node

{

int x, y, t;

Node (int xx, int yy, int tt) : x (xx), y (yy), t (tt) {}

};

char ans[maxn][maxn];

int mintime[maxn][maxn];

int row, col, s_x, s_y, e_x, e_y;

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1 && ans[x][y] != '#')

return true;

return false;

}

void BFS (int x, int y, int t)

{

queue <Node> q;

q.push (Node (x, y, t));

mintime[x][y] = 0;

while (!q.empty ())

{

Node temp = q.front ();

q.pop ();

int i;

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

{

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

{

Node val (temp.x + dx[i], temp.y + dy[i], temp.t + 1);

if (ans[val.x][val.y] == 'x')

val.t++;

if (mintime[val.x][val.y] > val.t)

{

mintime[val.x][val.y] = val.t;

q.push (Node (val.x, val.y, val.t));

}

int main()

{

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

while (cin >> row >> col)

{

int i, j;

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

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

{

cin >> ans[i][j];

mintime[i][j] = INF;

if (ans[i][j] == 'a')

{

s_x = i;

s_y = j;

}

else if (ans[i][j] == 'r')

{

e_x = i;

e_y = j;

}

BFS (s_x, s_y, 0);

if (mintime[e_x][e_y] == INF)

cout << "Poor ANGEL has to stay in the prison all his life." << endl;

else

cout << mintime[e_x][e_y] << endl;

}

return 0;

}

zoj1403

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

11 9月 2015

Safecracker

=== Op tech briefing, 2002/11/02 06:42 CST ===

"The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh from research knew Klein's secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the alphabet (A=1, B=2, ..., Z=26). The combination is then vwxyz. If there is more than one solution then the combination is the one that is lexicographically greatest, i.e., the one that would appear last in a dictionary."

v - w^2 + x^3 - y^4 + z^5 = target

"For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 - 9^2 + 5^3 - 3^4 + 2^5 = 1. There are actually several solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving, because it could take months of effort to try all the possibilities even if you knew the secret. But of course computers didn't exist then."

=== Op tech directive, computer division, 2002/11/02 12:30 CST ===

"Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations. Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input. For each line output the Klein combination, break ties with lexicographic order, or 'no solution' if there is no correct combination. Use the exact format shown below."
Sample Input

1 ABCDEFGHIJKL
11700519 ZAYEXIWOVU
3072997 SOUGHT
1234567 THEQUICKFROG
0 END
Sample Output

LKEBA
YOXUZ
GHOST
no solution

题目类型：暴力枚举

算法分析：使用递归搜索的方式进行枚举，使用一个贪心策略：按字典序从大到小枚举可用的字符串，然后对于构造好的字符串计算等式的值，如果符合条件，则该字符串就是字典序最大的，直接输出即可，否则继续枚举字符串。这样要比直接枚举要快一倍(好像poj的数据比较弱，两种方法都可以AC~~)。注意计算整数乘方时不要使用pow函数，否则会出现精度误差，此时应该自己写函数并调用

#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;

char maxval[maxn], val[maxn];
long long n;
char s[maxn];
bool visited[maxn];
bool is_valid;

int pow_val(int val,int n)
{
    int i, ans = 1;

    for(i = 1;i <= n; i++)
       ans *= val;

return ans;
}

void DFS (int cur)
{
    if (is_valid)
        return ;

    if (cur == 5)
    {
        long long sum = pow_val (val[0] - 'A' + 1, 1) - pow_val (val[1] - 'A' + 1, 2)
        + pow_val (val[2] - 'A' + 1, 3) - pow_val (val[3] - 'A' + 1, 4) + pow_val (val[4] - 'A' + 1, 5);

        if (sum == n)
        {
            is_valid = true;
            val[cur] = 0;
            strcpy (maxval, val);
        }

    return ;
    }

    int i, len = strlen (s);

    for (i = len - 1; i >= 0; i--)
    {
        if (!visited[i])
        {
            val[cur] = s[i];
            visited[i] = true;
            DFS (cur + 1);
            visited[i] = false;
        }
    }
}


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


    while (cin >> n >> s)
    {
        if (n == 0 && !strcmp (s, "END"))
            break;

        memset (val, 0, sizeof (val));
        memset (maxval, 0, sizeof (maxval));
        memset (visited, false, sizeof (visited));

        is_valid = false;

        int len = strlen (s);

        sort (s, s + len);

        DFS (0);

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

        else
            cout << "no solution" << endl;
    }

return 0;
}

100

101

102

#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;

char maxval[maxn], val[maxn];

long long n;

char s[maxn];

bool visited[maxn];

bool is_valid;

int pow_val(int val,int n)

{

int i, ans = 1;

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

ans *= val;

return ans;

}

void DFS (int cur)

{

if (is_valid)

return ;

if (cur == 5)

{

long long sum = pow_val (val[0] - 'A' + 1, 1) - pow_val (val[1] - 'A' + 1, 2)

+ pow_val (val[2] - 'A' + 1, 3) - pow_val (val[3] - 'A' + 1, 4) + pow_val (val[4] - 'A' + 1, 5);

if (sum == n)

{

is_valid = true;

val[cur] = 0;

strcpy (maxval, val);

}

return ;

}

int i, len = strlen (s);

for (i = len - 1; i >= 0; i--)

{

if (!visited[i])

{

val[cur] = s[i];

visited[i] = true;

DFS (cur + 1);

visited[i] = false;

}

int main()

{

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

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

while (cin >> n >> s)

{

if (n == 0 && !strcmp (s, "END"))

break;

memset (val, 0, sizeof (val));

memset (maxval, 0, sizeof (maxval));

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

is_valid = false;

int len = strlen (s);

sort (s, s + len);

DFS (0);

if (is_valid)

cout << maxval << endl;

else

cout << "no solution" << endl;

}

return 0;

}

1 2 下一页最后一页

超客的水墨烟雨

zoj3609

zoj3203

zoj2913

zoj2797

zoj2750

zoj2412

zoj2193

zoj2110

zoj2016

zoj1967

zoj1952

zoj1948

zoj1942

zoj1718

zoj1649

zoj1403

分类目录

标签云

书签

近期评论

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