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

poj1258

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

15 9月 2015

Agri-Net

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. The distance between any two farms will not exceed 100,000.

Input

The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.

Output

For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

Sample Input

0 4 9 21

4 0 8 17

9 8 0 16

21 17 16 0

Sample Output

Source

USACO 102

题目类型：MST

算法分析：直接使用prim算法计算最小权值和即可

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

const int maxn = 100 + 36;

int ans[maxn][maxn], dis[maxn];
bool visited[maxn];
int sum, n;

void Init ()
{
	memset (visited, false, sizeof (visited));
	
	dis[0] = 666666666;
	int i;
	for (i = 1; i < n; i++)
		dis[i] = ans[0][i];
}

void Prim ()
{
	sum = 0;
	visited[0] = true;

	int i, j;
	for (i = 1; i < n; i++)
	{
		int temp = 0;
		for (j = 1; j < n; j++)
			if (!visited[j] && dis[j] < dis[temp])
			temp = j;

		visited[temp] = true;
		sum += dis[temp];

		for (j = 1; j < n; j++)
			if (!visited[j])
				dis[j] = min (dis[j], ans[j][temp]);
	}
}


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

	while (cin >> n)
	{
		int i, j;
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				cin >> ans[i][j];

		Init ();

		Prim ();
		
		cout << sum << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 100 + 36;

int ans[maxn][maxn], dis[maxn];

bool visited[maxn];

int sum, n;

void Init ()

{

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

dis[0] = 666666666;

int i;

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

dis[i] = ans[0][i];

}

void Prim ()

{

sum = 0;

visited[0] = true;

int i, j;

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

{

int temp = 0;

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

if (!visited[j] && dis[j] < dis[temp])

temp = j;

visited[temp] = true;

sum += dis[temp];

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

if (!visited[j])

dis[j] = min (dis[j], ans[j][temp]);

}

int main()

{

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

while (cin >> n)

{

int i, j;

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

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

cin >> ans[i][j];

Init ();

Prim ();

cout << sum << endl;

}

return 0;

}

poj1251

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

15 9月 2015

ungle Roads

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

Input

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

Output

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

Sample Input

A 2 B 12 I 25

B 3 C 10 H 40 I 8

C 2 D 18 G 55

D 1 E 44

E 2 F 60 G 38

F 0

G 1 H 35

H 1 I 35

A 2 B 10 C 40

B 1 C 20

Sample Output

216

Source

Mid-Central USA 2002

题目类型：MST

算法分析：读入数据并处理得到每个边的信息，然后存到edge数组中。最后直接调用kruskal算法计算最小生成树即可

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

#define EPS 1e-8
#define INF (1 << 10)
#define PI acos (-1.0);


const int maxn = 36 + 66;

int parent[maxn];

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

Node edge[maxn];
int len, sum;
int n;

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


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

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


void kruskal ()
{
	int i, 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");
//	freopen ("aaa.txt", "r", stdin);

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


		int i;
		for (i = 0; i < n - 1; i++)
		{
			char c_a;
			int k;
			cin >> c_a >> k;

			if (k > 0)
			{
				int j;
				char c_b;
				int c_w;
				for (j = 0; j < k; j++)
				{
					cin >> c_b >> c_w;

					edge[len].u = c_a - 'A';
					edge[len].v = c_b - 'A';
					edge[len].w = c_w;
					len++;
				}
			}
		}

		sum = 0;
		for (i = 0; i < maxn; i++)
			parent[i] = -1;
		
		sort (edge, edge + len, Cmp);

		kruskal ();

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

#define EPS 1e-8

#define INF (1 << 10)

#define PI acos (-1.0);

const int maxn = 36 + 66;

int parent[maxn];

struct Node

{

int u, v, w;

};

Node edge[maxn];

int len, sum;

int n;

bool Cmp (Node a, Node b)

{

return a.w < b.w;

}

int UnFind (int val)

{

if (parent[val] == -1)

return val;

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

}

void kruskal ()

{

int i, 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");

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

while (cin >> n)

{

if (n == 0)

break;

len = 0;

int i;

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

{

char c_a;

int k;

cin >> c_a >> k;

if (k > 0)

{

int j;

char c_b;

int c_w;

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

{

cin >> c_b >> c_w;

edge[len].u = c_a - 'A';

edge[len].v = c_b - 'A';

edge[len].w = c_w;

len++;

}

sum = 0;

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

parent[i] = -1;

sort (edge, edge + len, Cmp);

kruskal ();

cout << sum << endl;

}

return 0;

}

poj1220

maksyuki 发表于 oj 分类，标签: 基础算法-高精度

15 9月 2015

NUMBER BASE CONVERSION

Write a program to convert numbers in one base to numbers in a second base. There are 62 different digits:{ 0-9,A-Z,a-z }HINT: If you make a sequence of base conversions using the output of 阅读全文 »

poj1218

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

15 9月 2015

THE DRUNK JAILER

A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked.One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He repeats this for n rounds, takes a final drink, and passes out. Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.

Given the number of cells, determine how many prisoners escape jail.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

Output

For each line, you must print out the number of prisoners that escape when the prison has n cells.

Sample Input

100

Sample Output

Source

Greater New York 2002

题目类型：模拟

算法分析：先将数组中的每一个元素初始化为某一个标志，然后按照题目所给的关于开、闭门及转换门状态的规律模拟进行n次，最后统计与初始标志相反的元素的个数，即为所求

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

int isopen[106];

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

    cin >> cases;

    while (cases--)
    {
        cin >> n;
        memset (isopen, -1, sizeof (isopen));
        int i;

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

            for (j = 1; i * j <= n; j++)
                isopen[i*j] = - isopen[i*j];
        }

            int num = 0;
            for (i = 1; i <= n; i++)
            {
                if (isopen[i] == 1)
                    num++;
            }

            printf ("%d\n", num);
    }

    return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

int isopen[106];

int main()

{

int n, cases;

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

cin >> cases;

while (cases--)

{

cin >> n;

memset (isopen, -1, sizeof (isopen));

int i;

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

{

int j;

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

isopen[i*j] = - isopen[i*j];

}

int num = 0;

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

{

if (isopen[i] == 1)

num++;

}

printf ("%d\n", num);

}

return 0;

}

poj1195

maksyuki 发表于 oj 分类，标签: 数据结构-树状数组

15 9月 2015

Mobile phones

Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns 阅读全文 »

poj1182

maksyuki 发表于 oj 分类，标签: 数据结构-并查集

15 9月 2015

食物链

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。阅读全文 »

poj1163

maksyuki 发表于 oj 分类，标签: DP-线性DP

15 9月 2015

The Triangle

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either 阅读全文 »

poj1157

maksyuki 发表于 oj 分类，标签: DP-线性DP

15 9月 2015

LITTLE SHOP OF FLOWERS

You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.

		V A S E S
		1	2	3	4	5
Bunches	1 (azaleas)	7	23	-5	-24	16
	2 (begonias)	5	21	-4	10	23
	3 (carnations)	-21	5	-4	-20	20

According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

Input

The first line contains two numbers: F, V.
The following F lines: Each of these lines contains V integers, so that A_ij is given as the j^th number on the (i+1)^st line of the input file.

1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
F <= V <= 100 where V is the number of vases.
-50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.

Output

The first line will contain the sum of aesthetic values for your arrangement.

Sample Input

3 5

7 23 -5 -24 16

5 21 -4 10 23

-21 5 -4 -20 20

Sample Output

Source

IOI 1999

题目类型：线性dp

算法分析：类似于经典线性dp的三角形最大和问题，只不过这里的下一行的数必须上一行的数的列数大，可以直接在原数组上进行递推，最后查找最后一行中最大的数即可

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

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

int ans[maxn][maxn];

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

    int row, col;

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

        for (int i = 1; i < row; i++)
        {
            for (int j = i; j < col; j++)
            {
                int temp = ans[i][j];
                ans[i][j] += ans[i-1][0];
                for (int k = 1; k < j; k++)
                    ans[i][j] = max (ans[i][j], ans[i-1][k] + temp);
            }
        }

        int maxval = -INF;
        for (int i = 2; i < col; i++)
            maxval = max (maxval, ans[row-1][i]);

        cout << maxval << 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;

const int INF = 0x7FFFFFFF;

const int MOD = 1000000000 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

int ans[maxn][maxn];

int main()

{

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

int row, col;

while (cin >> row >> col)

{

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

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

cin >> ans[i][j];

for (int i = 1; i < row; i++)

{

for (int j = i; j < col; j++)

{

int temp = ans[i][j];

ans[i][j] += ans[i-1][0];

for (int k = 1; k < j; k++)

ans[i][j] = max (ans[i][j], ans[i-1][k] + temp);

}

int maxval = -INF;

for (int i = 2; i < col; i++)

maxval = max (maxval, ans[row-1][i]);

cout << maxval << endl;

}

return 0;

}

poj1151

maksyuki 发表于 oj 分类，标签: 数据结构-线段树

15 9月 2015

Atlantis

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different 阅读全文 »

poj1149

maksyuki 发表于 oj 分类，标签: 图论(网络流)-最大流

15 9月 2015

PIGS

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs. All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold. More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses. An unlimited number of pigs can be placed in every pig-house. Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

3 3

3 1 10

2 1 2 2

2 1 3 3

1 2 6

Sample Output

Source

Croatia OI 2002 Final Exam - First day

题目类型：最大流

算法分析：将每个顾客看做是一个节点，然后对于第一个去猪圈的顾客，将源点和其相连，边权是这个猪圈的初始猪数，对于一个猪圈，之后来的顾客，其与前一个在这个猪圈的顾客相连，权值是INF，最后每个顾客希望得到的最大猪数就是其与汇点相连的边权，建完图之后，直接调用EK算法即可，注意此时源点和汇点分别取值0、n+1

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

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


struct Node
{
	int c, f;//分别表示弧之间的容量和流量
};

Node edge[maxn][maxn];
int n, m, pre[maxn], a[maxn];

long long Edmonds_Karp (int s, int t)
{
    queue <int> q;
    memset (a, 0, sizeof(a));
    memset (pre, 0, sizeof(pre));
    long long maxflow = 0;

    while (1)
    {
        memset (a, 0, sizeof(a));
        a[s] = INF;
        q.push(s);
        while (!q.empty())
        {
            int tt = q.front(); q.pop();

            for (int i = 0; i <= n + 1; i++)
            if(!a[i] && edge[tt][i].c > edge[tt][i].f)
            {
                pre[i] = tt;
                q.push (i);
                a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f;
            }
        }

        if(a[t] == 0) break;

        for(int i = t; i != s; i = pre[i])
        {
            edge[pre[i]][i].f += a[t];
            edge[i][pre[i]].f -= a[t];
        }

        maxflow += a[t];
    }
    return maxflow;
}


int pig[maxn], last[maxn];

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

    while (cin >> m >> n)
	{
		memset (edge, 0, sizeof (edge));
        memset (last, 0, sizeof (last));

        for (int i =1;  i <= m; i++)
            cin >> pig[i];

        for (int i = 1; i <= n; i++)
        {
            int tt;
            cin >> tt;
            for (int j = 1; j <= tt; j++)
            {
                int k;
                cin >> k;
                if (!last[k])
                    edge[0][i].c += pig[k];

                else
                    edge[last[k]][i].c = INF;

                last[k] = i;
            }
            cin >> edge[i][n+1].c;
        }

        cout << Edmonds_Karp (0, n + 1) << 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

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

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

struct Node

{

int c, f;//分别表示弧之间的容量和流量

};

Node edge[maxn][maxn];

int n, m, pre[maxn], a[maxn];

long long Edmonds_Karp (int s, int t)

{

queue <int> q;

memset (a, 0, sizeof(a));

memset (pre, 0, sizeof(pre));

long long maxflow = 0;

while (1)

{

memset (a, 0, sizeof(a));

a[s] = INF;

q.push(s);

while (!q.empty())

{

int tt = q.front(); q.pop();

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

if(!a[i] && edge[tt][i].c > edge[tt][i].f)

{

pre[i] = tt;

q.push (i);

a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f;

}

if(a[t] == 0) break;

for(int i = t; i != s; i = pre[i])

{

edge[pre[i]][i].f += a[t];

edge[i][pre[i]].f -= a[t];

}

maxflow += a[t];

}

return maxflow;

}

int pig[maxn], last[maxn];

int main()

{

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

while (cin >> m >> n)

{

memset (edge, 0, sizeof (edge));

memset (last, 0, sizeof (last));

for (int i =1; i <= m; i++)

cin >> pig[i];

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

{

int tt;

cin >> tt;

for (int j = 1; j <= tt; j++)

{

int k;

cin >> k;

if (!last[k])

edge[0][i].c += pig[k];

else

edge[last[k]][i].c = INF;

last[k] = i;

}

cin >> edge[i][n+1].c;

}

cout << Edmonds_Karp (0, n + 1) << endl;

}

return 0;

}

poj1144

maksyuki 发表于 oj 分类，标签: 图论-求解割点\割边(Tarjan)

15 9月 2015

Network

A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.

Input

The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated
by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0;

Output

The output contains for each block except the last in the input file one line containing the number of critical places.

Sample Input

5 1 2 3 4

2 1 3

5 4 6 2

Sample Output

Hint

You need to determine the end of one line.In order to make it's easy to determine,there are no extra blank before the end of each line.

Source

Central Europe 1996

题目类型：割点数量

算法分析：直接使用Tarjan算法求出每个点的连通分量的个数，然后按照所得的结果判断每个节点是否是割点，注意要额外判断根节点的情况！！！

#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 i64 long long

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

//分别表示邻接矩阵、访问数组、dfs深度优先数、当前节点可以到达的最低优先数和每个节点的连通分量数(删去该节点)
int edge[maxn][maxn], vis[maxn], dfsn[maxn], low[maxn], subnets[maxn];
int n, id;//分别表示节点总数和全局标志(标记dfs深度优先数)

void Init (int rt)
{
    for (int i = 0; i < maxn; i++)//初始化邻接矩阵
        for (int j = 0; j < maxn; j++)
        {
            if (i == j)
                edge[i][j] = 0;

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

    dfsn[rt] = low[rt] = id = 1;//将根节点的dfsn和low值都置为1
    memset (vis, 0, sizeof (vis));
    vis[rt] = 1;//初始化访问数组vis
    memset (subnets, 0, sizeof (subnets));//初始化连通分量数组subnets
}

void dfs (int u)
{
    for (int v = 1; v <= n; v++)//依次判断所有的邻接点
    {
        if (edge[u][v] < INF && u != v && !vis[v])//如果邻接且v为u的孩子节点
        {
            vis[v] = 1;
            dfsn[v] = low[v] = ++id;//访问该孩子节点并打上标志
            dfs (v);//递归地访问v的孩子节点
            low[u] = min (low[u], low[v]);//使用u的孩子节点v的low值来更新u的low值

            if (low[v] >= dfsn[u])//如果孩子节点的low值(深度)大于等于当前节点u的dfsn值(深度)，连通分量个数自加1
                subnets[u]++;
        }

        else if (edge[u][v] < INF && u != v && vis[v])//如果邻接且v为u的祖先节点
            low[u] = min (low[u], dfsn[v]);//直接使用回边中祖先节点的dfsn值更新u的low值即可
    }
}

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

        Init(1);

        string s;
        getline (cin, s);
        while(getline(cin, s))
        {
            stringstream ss (s);
            int a;

            ss >> a;
            if (a == 0)
                break;

            int b;
            while (ss >> b)
            {
                edge[a][b] = edge[b][a] = 1;
            }
        }

        dfs (1);
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i == 1 && subnets[i] > 1)
                res++;

            else if (i != 1 && subnets[i])
                res++;
        }

        cout << res << 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 <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 i64 long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1000 + 66;

//分别表示邻接矩阵、访问数组、dfs深度优先数、当前节点可以到达的最低优先数和每个节点的连通分量数(删去该节点)

int edge[maxn][maxn], vis[maxn], dfsn[maxn], low[maxn], subnets[maxn];

int n, id;//分别表示节点总数和全局标志(标记dfs深度优先数)

void Init (int rt)

{

for (int i = 0; i < maxn; i++)//初始化邻接矩阵

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

{

if (i == j)

edge[i][j] = 0;

else

edge[i][j] = INF;

}

dfsn[rt] = low[rt] = id = 1;//将根节点的dfsn和low值都置为1

memset (vis, 0, sizeof (vis));

vis[rt] = 1;//初始化访问数组vis

memset (subnets, 0, sizeof (subnets));//初始化连通分量数组subnets

}

void dfs (int u)

{

for (int v = 1; v <= n; v++)//依次判断所有的邻接点

{

if (edge[u][v] < INF && u != v && !vis[v])//如果邻接且v为u的孩子节点

{

vis[v] = 1;

dfsn[v] = low[v] = ++id;//访问该孩子节点并打上标志

dfs (v);//递归地访问v的孩子节点

low[u] = min (low[u], low[v]);//使用u的孩子节点v的low值来更新u的low值

if (low[v] >= dfsn[u])//如果孩子节点的low值(深度)大于等于当前节点u的dfsn值(深度)，连通分量个数自加1

subnets[u]++;

}

else if (edge[u][v] < INF && u != v && vis[v])//如果邻接且v为u的祖先节点

low[u] = min (low[u], dfsn[v]);//直接使用回边中祖先节点的dfsn值更新u的low值即可

}

int main()

{

// CPPFF;

while (cin >> n)

{

if (n == 0)

break;

Init(1);

string s;

getline (cin, s);

while(getline(cin, s))

{

stringstream ss (s);

int a;

ss >> a;

if (a == 0)

break;

int b;

while (ss >> b)

{

edge[a][b] = edge[b][a] = 1;

}

dfs (1);

int res = 0;

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

{

if (i == 1 && subnets[i] > 1)

res++;

else if (i != 1 && subnets[i])

res++;

}

cout << res << endl;

}

return 0;

}

poj1135

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

15 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 阅读全文 »

poj1125

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

15 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 阅读全文 »

poj1122

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

15 9月 2015

FDNY to the Rescue!

The Fire Department of New York (FDNY) has always been proud of their response time to fires in New York City, but they want to make their response time even better. To help them 阅读全文 »

poj1088

maksyuki 发表于 oj 分类，标签: DP-线性DP

15 9月 2015

滑雪

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡阅读全文 »

poj1068

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

15 9月 2015

Parencodings

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways: 阅读全文 »

返回首页上一页 6 7 8 9 10 下一页最后一页

超客的水墨烟雨

poj1258

poj1251

poj1220

poj1218

poj1195

poj1182

poj1163

poj1157

poj1151

poj1149

poj1144

poj1135

poj1125

poj1122

poj1088

poj1068

分类目录

标签云

书签

近期评论

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