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

poj1458

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

15 9月 2015

Common Subsequence

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, x_ij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc abfcab

programming contest

abcd mnp

Sample Output

Source

Southeastern Europe 2003

题目类型：线性DP

算法分析：求最大公共子串的长度，f[i][j]定义为有前i和j个字符的字符串val_a和val_b的最长公共子串的长度。转移方程为：如果字符串val_a[i] == val_b[j]，则有f[i][j] = f[i-1][j-1] + 1；反之则f[i][j] = max (f[i-1][j], f[i][j-1]); 1 <= 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 = 266;
const int INF = 0x7FFFFFFF;

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

    char val_a[maxn], val_b[maxn];
    int f[maxn][maxn];

    while (cin >> val_a + 1 >> val_b + 1)
    {
        val_a[0] = val_b[0] = '*';

        int len_a = strlen (val_a), len_b = strlen (val_b);
        memset (f, 0, sizeof (f));

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

            for (j = 1; j < len_b; j++)
            {
                if (val_a[i] == val_b[j])
                    f[i][j] = f[i-1][j-1] + 1;

                else
                    f[i][j] = max (f[i-1][j], f[i][j-1]);
            }
        }

        int maxval = -INF;
        for (i = 1; i < len_b; i++)
            if (maxval < f[len_a-1][i])
                maxval = f[len_a-1][i];

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

int main()

{

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

char val_a[maxn], val_b[maxn];

int f[maxn][maxn];

while (cin >> val_a + 1 >> val_b + 1)

{

val_a[0] = val_b[0] = '*';

int len_a = strlen (val_a), len_b = strlen (val_b);

memset (f, 0, sizeof (f));

int i, j;

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

{

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

{

if (val_a[i] == val_b[j])

f[i][j] = f[i-1][j-1] + 1;

else

f[i][j] = max (f[i-1][j], f[i][j-1]);

}

int maxval = -INF;

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

if (maxval < f[len_a-1][i])

maxval = f[len_a-1][i];

cout << maxval << endl;

}

return 0;

}

poj1456

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

15 9月 2015

Supermarket

A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured 阅读全文 »

poj1442

maksyuki 发表于 oj 分类，标签: 数据结构-平衡树(Treap)

15 9月 2015

Black Box

Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions:

ADD (x): put element x into Black Box;
GET: increase i by 1 and give an i-minimum out of all integers containing in the Black Box. Keep in mind that i-minimum is a number located at i-th place after Black Box elements sorting by non- descending. It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions: 30000 of each type.

Let us describe the sequence of transactions by two integer arrays:

1. A(1), A(2), ..., A(M): a sequence of elements which are being included into Black Box. A values are integers not exceeding 2 000 000 000 by their absolute value, M <= 30000. For the Example we have A=(3, 1, -4, 2, 8, -1000, 2).

2. u(1), u(2), ..., u(N): a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and N-transaction GET. For the Example we have u=(1, 2, 6, 6).

The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u(N) is sorted in non-descending order, N <= M and for each p (1 <= p <= N) an inequality p <= u(p) <= M is valid. It follows from the fact that for the p-element of our u sequence we perform a GET transaction giving p-minimum number from our A(1), A(2), ..., A(u(p)) sequence.
Input

Input contains (in given order): M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). All numbers are divided by spaces and (or) carriage return characters.

Output

Write to the output Black Box answers sequence for a given sequence of transactions, one number each line.

Sample Input

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

Sample Output

Source

Northeastern Europe 1996

题目类型：动态查询区间第k小

算法分析：直接使用Treap边插入，边查询即可，注意如果查询出现在插入完所有元素之后的话，此时要注意循环的判出条件！！！

#pragma comment(linker, "/STACK:102400000,102400000")
#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
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

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

struct node
{
	int l, r, v, size, rnd, w;
}tr[maxn];

//分别表示节点的个数、标号变量、根节点和最终的结果
int n, size, root;

void Init ()
{
    root = size = 0;
    memset (tr, 0, sizeof (tr));
}

void UpDate (int rt)//更新结点信息
{
	tr[rt].size = tr[tr[rt].l].size + tr[tr[rt].r].size + tr[rt].w;
}

void lturn (int &rt)
{
	int tt = tr[rt].r; tr[rt].r = tr[tt].l; tr[tt].l = rt;
	tr[tt].size = tr[rt].size; UpDate(rt); rt = tt;
}

void rturn (int &rt)
{
	int tt = tr[rt].l; tr[rt].l = tr[tt].r; tr[tt].r = rt;
	tr[tt].size = tr[rt].size; UpDate(rt); rt = tt;
}

void Insert (int &rt, int x)
{
	if (rt == 0)
	{
		rt = ++size;
		tr[rt].size = tr[rt].w = 1; tr[rt].v = x; tr[rt].rnd = rand();
		return ;
	}

	tr[rt].size++;
    if (tr[rt].v == x) tr[rt].w++;//每个结点顺便记录下与该节点相同值的数的个数

	else if (x > tr[rt].v)
	{
		Insert (tr[rt].r, x);
		if (tr[tr[rt].r].rnd < tr[rt].rnd) lturn (rt);//维护堆性质
	}

	else
	{
		Insert (tr[rt].l, x);
		if (tr[tr[rt].l].rnd < tr[rt].rnd) rturn (rt);
	}
}

int QueryNum (int rt, int x)
{
    if (rt == 0) return 0;

	if (x <= tr[tr[rt].l].size)
		return QueryNum (tr[rt].l, x);

    else if (x > tr[tr[rt].l].size + tr[rt].w)
		return QueryNum (tr[rt].r, x - tr[tr[rt].l].size - tr[rt].w);

    else return tr[rt].v;
}

int a[maxn], u[maxn];

int main()
{
//    CPPFF;
    int m;
    while (cin >> n >> m)
    {
        Init ();

        for (int i = 1; i <= n; i++)
            cin >> a[i];

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

        for (int pa = 1, pb = 1, all = 0; pb <= m; )
        {
            if (u[pb] == all)
            {
                cout << QueryNum(root, pb) << endl;
                pb++;
            }

            else
            {
                Insert(root, a[pa]);
                all++;
                pa++;
            }
        }


    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

#pragma comment(linker, "/STACK:102400000,102400000")

#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

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 3e4 + 66;

struct node

{

int l, r, v, size, rnd, w;

}tr[maxn];

//分别表示节点的个数、标号变量、根节点和最终的结果

int n, size, root;

void Init ()

{

root = size = 0;

memset (tr, 0, sizeof (tr));

}

void UpDate (int rt)//更新结点信息

{

tr[rt].size = tr[tr[rt].l].size + tr[tr[rt].r].size + tr[rt].w;

}

void lturn (int &rt)

{

int tt = tr[rt].r; tr[rt].r = tr[tt].l; tr[tt].l = rt;

tr[tt].size = tr[rt].size; UpDate(rt); rt = tt;

}

void rturn (int &rt)

{

int tt = tr[rt].l; tr[rt].l = tr[tt].r; tr[tt].r = rt;

tr[tt].size = tr[rt].size; UpDate(rt); rt = tt;

}

void Insert (int &rt, int x)

{

if (rt == 0)

{

rt = ++size;

tr[rt].size = tr[rt].w = 1; tr[rt].v = x; tr[rt].rnd = rand();

return ;

}

tr[rt].size++;

if (tr[rt].v == x) tr[rt].w++;//每个结点顺便记录下与该节点相同值的数的个数

else if (x > tr[rt].v)

{

Insert (tr[rt].r, x);

if (tr[tr[rt].r].rnd < tr[rt].rnd) lturn (rt);//维护堆性质

}

else

{

Insert (tr[rt].l, x);

if (tr[tr[rt].l].rnd < tr[rt].rnd) rturn (rt);

}

int QueryNum (int rt, int x)

{

if (rt == 0) return 0;

if (x <= tr[tr[rt].l].size)

return QueryNum (tr[rt].l, x);

else if (x > tr[tr[rt].l].size + tr[rt].w)

return QueryNum (tr[rt].r, x - tr[tr[rt].l].size - tr[rt].w);

else return tr[rt].v;

}

int a[maxn], u[maxn];

int main()

{

// CPPFF;

int m;

while (cin >> n >> m)

{

Init ();

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

cin >> a[i];

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

cin >> u[i];

for (int pa = 1, pb = 1, all = 0; pb <= m; )

{

if (u[pb] == all)

{

cout << QueryNum(root, pb) << endl;

pb++;

}

else

{

Insert(root, a[pa]);

all++;

pa++;

}

return 0;

}

poj1365

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

15 9月 2015

Prime Land

Everybody in the Prime Land is using a prime base number system. In this system, each positive integer x is represented as follows: Let {pi}i=0,1,2,... denote the increasing sequence of all prime numbers. We know that x > 1 can be represented in only one way in the form of product of powers of prime factors. This implies that there is an integer kx and uniquely determined integers e_kx, e_kx-1, ..., e₁, e₀, (e_kx > 0), that The sequence (e_kx, e_kx-1, ... ,e₁, e₀) is considered to be the representation of x in prime base number system. It is really true that all numerical calculations in prime base number system can seem to us a little bit unusual, or even hard. In fact, the children in Prime Land learn to add to subtract numbers several years. On the other hand, multiplication and division is very simple. Recently, somebody has returned from a holiday in the Computer Land where small smart things called computers have been used. It has turned out that they could be used to make addition and subtraction in prime base number system much easier. It has been decided to make an experiment and let a computer to do the operation minus one''. Help people in the Prime Land and write a corresponding program. For practical reasons we will write here the prime base representation as a sequence of such pi and ei from the prime base representation above for which ei > 0. We will keep decreasing order with regard to pi.

Input

The input consists of lines (at least one) each of which except the last contains prime base representation of just one positive integer greater than 2 and less or equal 32767. All numbers in the line are separated by one space. The last line contains number 0.

Output

The output contains one line for each but the last line of the input. If x is a positive integer contained in a line of the input, the line in the output will contain x - 1 in prime base representation. All numbers in the line are separated by one space. There is no line in the output corresponding to the last null'' line of the input.

Sample Input

17 1

5 1 2 1

509 1 59 1

Sample Output

2 4

3 2

13 1 11 1 7 1 5 1 3 1 2 1

Source

Central Europe 1997

题目类型：素因子分解

算法分析：先将输入的数转换成整数val，然后val自减一，最后将val进行素因子分解就可以了，注意要先打出素数表，否则会TLE

#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
#define ULL unsigned 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 = 1e5 + 66;


LL aa[maxn], maxval;

inline LL power (LL a, LL num)
{
    LL res = 1;
    for (LL i = 1; i <= num; i++)
        res *= a;

    return res;
}


LL primelist[maxn], prime_len;
bool prime[maxn];

void Get ()
{
    memset (prime, true, sizeof (prime));
    prime_len = 0;
    for (LL i = 2; i < maxn - 6; i++)
    {
        if (prime[i])
            primelist[prime_len++] = i;

        for (LL j = 0; j < prime_len; j++)
        {
            if (i * primelist[j] > maxn - 6)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}


void PP (LL val)
{
    memset (aa, 0, sizeof (aa));
    maxval = -INF;
    for (LL i = 0; i < prime_len && primelist[i] * primelist[i] <= val; i++)
    {
        while (val % primelist[i] == 0)
        {
            aa[primelist[i]]++;
            maxval = max (maxval, primelist[i]);
            val /= primelist[i];
        }
    }

    if(val > 1)
    {
        aa[val]++;
        maxval = max (maxval, val);
    }
}


int main()
{
    Get ();

//    CPPFF;
    string s;
    while (getline (cin, s))
    {
        if(s == "0")
            break;

        stringstream ss (s);
        LL res = 1, ta, tb;
        while (ss >> ta >> tb)
        {
            res *= power (ta, tb);
        }

        PP (res - 1);
        for (LL i = maxval; i >= 2; i--)
        {
            if (i == maxval && aa[i])
            {
                printf ("%lld %lld", i, aa[i]);
            }

            else if (aa[i])
                printf (" %lld %lld", i, aa[i]);
        }
        puts ("");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#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

#define ULL unsigned 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 = 1e5 + 66;

LL aa[maxn], maxval;

inline LL power (LL a, LL num)

{

LL res = 1;

for (LL i = 1; i <= num; i++)

res *= a;

return res;

}

LL primelist[maxn], prime_len;

bool prime[maxn];

void Get ()

{

memset (prime, true, sizeof (prime));

prime_len = 0;

for (LL i = 2; i < maxn - 6; i++)

{

if (prime[i])

primelist[prime_len++] = i;

for (LL j = 0; j < prime_len; j++)

{

if (i * primelist[j] > maxn - 6)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

void PP (LL val)

{

memset (aa, 0, sizeof (aa));

maxval = -INF;

for (LL i = 0; i < prime_len && primelist[i] * primelist[i] <= val; i++)

{

while (val % primelist[i] == 0)

{

aa[primelist[i]]++;

maxval = max (maxval, primelist[i]);

val /= primelist[i];

}

if(val > 1)

{

aa[val]++;

maxval = max (maxval, val);

}

int main()

{

Get ();

// CPPFF;

string s;

while (getline (cin, s))

{

if(s == "0")

break;

stringstream ss (s);

LL res = 1, ta, tb;

while (ss >> ta >> tb)

{

res *= power (ta, tb);

}

PP (res - 1);

for (LL i = maxval; i >= 2; i--)

{

if (i == maxval && aa[i])

{

printf ("%lld %lld", i, aa[i]);

}

else if (aa[i])

printf (" %lld %lld", i, aa[i]);

}

puts ("");

}

return 0;

}

poj1330

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

15 9月 2015

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:In the figure, each node is labeled with an integer from {1, 2,...,16}.

Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

Sample Input

1 14

8 5

10 16

5 9

4 6

8 4

4 10

1 13

6 15

10 11

6 7

10 2

16 3

8 1

16 12

16 7

2 3

3 4

3 1

1 5

3 5

Sample Output

Source

Taejon 2002

题目类型：最近公共祖先

算法分析：使用一个parent数组来记录节点的父节点的标号，再使用一个cnt数组记录节点所在树的层数，对于输入中的两个节点，每次首先上寻所在树的层数大的节点的父节点，然后判断另一个节点的父节点是否是该节点。相同层数则上寻任意一个节点的父节点。直到找到满足条件的父节点并输出

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

const int maxn = 10000 + 6;

int par[maxn];
int cnt[maxn];

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

	int t;
	int val_a, val_b;

	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		
		int i, a, b;
		
		for (i = 0; i < maxn; i++)
		{
			par[i] = -1;
			cnt[i] = 1;
		}
		

		for (i = 0; i < n - 1; i++)
		{
			cin >> a >> b;
			par[b] = a;
		}
		
		cin >> val_a >> val_b;

		for (i = 0; i < maxn; i++)
			if (par[i] != -1)
			{
				int next = par[i];

				while (next != -1)
				{
					cnt[i]++;
					next = par[next];
				}
			}

		while (1)
		{
			if (cnt[val_a] == cnt[val_b])
			{
				val_a = par[val_a];	
			}

			else
			{
				if (cnt[val_a] > cnt[val_b])
				{
					if (par[val_a] == val_b)
					{
						cout << val_b << endl;
						break;
					}

					else
						val_a = par[val_a];
				}
				
				else if (cnt[val_a] < cnt[val_b])
				{
					if (par[val_b] == val_a)
					{
						cout << val_a << endl;
						break;
					}

					else
						val_b = par[val_b];
				}
			}
		}
	}
	
return 0;
}

使用LCA求解

代码：

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

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

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

int head[maxn], ind[maxn], parent[maxn], ans[maxn];
int tot, vala, valb, n;
bool visited[maxn];

struct Node
{
    int to;
    int next;
}edge[maxn];

void AddEdge (int a, int b)
{
    edge[tot].to = b;
    edge[tot].next = head[a];
    head[a] = tot++;
}

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

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

void Merge (int x, int y)
{
    int a = UnFind (x);
    int b = UnFind (y);
    if (a == b)
        return ;

    parent[b] = a;
}

void Init ()
{
    tot = 0;
    memset (head, -1, sizeof (head));
    memset (ind, 0, sizeof (ind));
    memset (visited, 0, sizeof (visited));

    for (int i = 1; i <= n; i++)
        parent[i] = i;
}


void LCA (int rt)
{
    ans[rt] = rt;
    for(int i = head[rt]; i != -1; i = edge[i].next)
    {
        LCA (edge[i].to);
        Merge (rt, edge[i].to);
        ans[UnFind(rt)] = rt;   //有可能rt并不是新树的根，所以要加这句
    }

    visited[rt] = true;
    if (rt == vala)
    {
        if (visited[valb])
            printf ("%d\n", ans[UnFind(valb)]);
    }

    else if (rt == valb)
    {
        if (visited[vala])
            printf("%d\n", ans[UnFind(vala)]);
    }
}

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

    int t;
    cin >> t;

    while (t--)
    {
        cin >> n;

        Init ();

        for (int i = 1; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            AddEdge (u, v);
            ind[v]++;
        }

        cin >> vala >> valb;
        for (int i = 1; i <= n; i++)
            if (!ind[i])
                LCA (i);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

#include <iostream>

#include <fstream>

using namespace std;

const int maxn = 10000 + 6;

int par[maxn];

int cnt[maxn];

int main()

{

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

int t;

int val_a, val_b;

cin >> t;

while (t--)

{

int n;

cin >> n;

int i, a, b;

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

{

par[i] = -1;

cnt[i] = 1;

}

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

{

cin >> a >> b;

par[b] = a;

}

cin >> val_a >> val_b;

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

if (par[i] != -1)

{

int next = par[i];

while (next != -1)

{

cnt[i]++;

next = par[next];

}

while (1)

{

if (cnt[val_a] == cnt[val_b])

{

val_a = par[val_a];

}

else

{

if (cnt[val_a] > cnt[val_b])

{

if (par[val_a] == val_b)

{

cout << val_b << endl;

break;

}

else

val_a = par[val_a];

}

else if (cnt[val_a] < cnt[val_b])

{

if (par[val_b] == val_a)

{

cout << val_a << endl;

break;

}

else

val_b = par[val_b];

}

return 0;

}

使用LCA求解

代码：

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

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

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

int head[maxn], ind[maxn], parent[maxn], ans[maxn];

int tot, vala, valb, n;

bool visited[maxn];

struct Node

{

int to;

int next;

}edge[maxn];

void AddEdge (int a, int b)

{

edge[tot].to = b;

edge[tot].next = head[a];

head[a] = tot++;

}

int UnFind (int val)

{

if (parent[val] == val)

return val;

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

}

void Merge (int x, int y)

{

int a = UnFind (x);

int b = UnFind (y);

if (a == b)

return ;

parent[b] = a;

}

void Init ()

{

tot = 0;

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

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

memset (visited, 0, sizeof (visited));

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

parent[i] = i;

}

void LCA (int rt)

{

ans[rt] = rt;

for(int i = head[rt]; i != -1; i = edge[i].next)

{

LCA (edge[i].to);

Merge (rt, edge[i].to);

ans[UnFind(rt)] = rt; //有可能rt并不是新树的根，所以要加这句

}

visited[rt] = true;

if (rt == vala)

{

if (visited[valb])

printf ("%d\n", ans[UnFind(valb)]);

}

else if (rt == valb)

{

if (visited[vala])

printf("%d\n", ans[UnFind(vala)]);

}

int main()

{

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

int t;

cin >> t;

while (t--)

{

cin >> n;

Init ();

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

{

int u, v;

cin >> u >> v;

AddEdge (u, v);

ind[v]++;

}

cin >> vala >> valb;

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

if (!ind[i])

LCA (i);

}

return 0;

}

poj1325

maksyuki 发表于 oj 分类，标签: 图论-二分图最大匹配

15 9月 2015

Machine Schedule

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem. There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, ..., mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, ... , mode_m-1. At the beginning they are both work at mode_0. For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y. Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.

The input will be terminated by a line containing a single zero.

Output

The output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

5 5 10

0 1 1

1 1 2

2 1 3

3 1 4

4 2 1

5 2 2

6 2 3

7 2 4

8 3 3

9 4 3

Sample Output

Source

Beijing 2002

题目类型：二分图最大匹配

算法分析：本题易知要求的是二分图的最小点覆盖，可以转换成最大匹配来求解。由于完成作业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 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 = 300 + 66;

int edge[maxn][maxn], vis[maxn];
int cx[maxn], cy[maxn], cxlen, cylen;

void Init ()
{
    for (int i = 1; i < maxn; i++)
        for (int j = 1; j < maxn; j++)
            edge[i][j] = INF;

}

long long dfs (int u)
{
    for (int v = 1; v <= cylen; v++)
    {
        if (edge[u][v] < INF && !vis[v])
        {
            vis[v] = 1;
            if (cy[v] == -1 || dfs (cy[v]))
            {
                cy[v] = u;
                cx[u] = v;
                return 1LL;
            }
        }
    }
    return 0LL;
}


long long MaxMatch ()
{
    long long res = 0;
    memset (cx, -1, sizeof (cx));
    memset (cy, -1, sizeof (cy));
    for (int i = 1; i <= cxlen; i++)
        if (cx[i] == -1)
        {
            memset (vis, 0, sizeof (vis));
            res += dfs (i);
        }

    return res;
}

int main()
{
//    CPPFF;

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

        Init ();
        cin >> cylen >> k;
        for (int i = 1; i <= k; i++)
        {
            int u, a, b;
            cin >> u >> a >> b;
            edge[a][b] = 1;
        }

        cout << MaxMatch () << endl;
    }

    return 0;
}

100

101

102

103

104

105

106

107

108

109

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

int edge[maxn][maxn], vis[maxn];

int cx[maxn], cy[maxn], cxlen, cylen;

void Init ()

{

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

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

edge[i][j] = INF;

}

long long dfs (int u)

{

for (int v = 1; v <= cylen; v++)

{

if (edge[u][v] < INF && !vis[v])

{

vis[v] = 1;

if (cy[v] == -1 || dfs (cy[v]))

{

cy[v] = u;

cx[u] = v;

return 1LL;

}

return 0LL;

}

long long MaxMatch ()

{

long long res = 0;

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

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

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

if (cx[i] == -1)

{

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

res += dfs (i);

}

return res;

}

int main()

{

// CPPFF;

int k;

while (cin >> cxlen)

{

if (cxlen == 0)

break;

Init ();

cin >> cylen >> k;

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

{

int u, a, b;

cin >> u >> a >> b;

edge[a][b] = 1;

}

cout << MaxMatch () << endl;

}

return 0;

}

poj1321

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

15 9月 2015

棋盘问题

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。阅读全文 »

poj1320

maksyuki 发表于 oj 分类，标签: 数论-佩尔方程

15 9月 2015

Street Numbers

A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back. One night she adds up the street numbers of the houses she passes (excluding her own). The next time she walks the other way she repeats this and finds, to her astonishment, that the two sums are the same. Although this is determined in part by her house number and in part by the number of houses in the street, she nevertheless feels that this is a desirable property for her house to have and decides that all her subsequent houses should exhibit it. Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):

6 8
35 49

Input

There is no input for this program.

Output

Output will consist of 10 lines each containing a pair of numbers, in increasing order with the last number, each printed right justified in a field of width 10 (as shown above).

Sample Input

Sample Output

6 8 35 49

Source

New Zealand 1990 Division I,UVA 138

题目类型：佩尔方程

算法分析：原题要求解的是1 + 2 + 3 +….n - 1 = n + 1 + n + 2 + ….m中的n和m，可以化简得到(2 * m + 1) ^ 2 – 8 * n ^ 2 = 1，令x = 2 * m + 1, y = n，则有x ^ 2- 8 * y ^ 2 = 1的佩尔方程，该方程的最小特解易求，然后使用递推式将前10个解输出即可

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

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

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

int main()
{
    int x1 = 3, y1 = 1, xn, yn;

    for (int i = 1; i <= 10; i++)
    {
        xn = 3 * x1 + 8 * y1;
        yn = x1 + 3 * y1;
        cout << setw (10) << yn << setw (10) << (xn - 1) / 2 << endl;
        x1 = xn, y1 = yn;
    }

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>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1000000 + 66;

int main()

{

int x1 = 3, y1 = 1, xn, yn;

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

{

xn = 3 * x1 + 8 * y1;

yn = x1 + 3 * y1;

cout << setw (10) << yn << setw (10) << (xn - 1) / 2 << endl;

x1 = xn, y1 = yn;

}

return 0;

}

poj1316

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

15 9月 2015

Self Numbers

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition 阅读全文 »

poj1305

maksyuki 发表于 oj 分类，标签: 数论-毕达哥拉斯三元组

15 9月 2015

Fermat vs. Pythagoras

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level. This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions of a^n + b^n = c^n for n > 2.
Given a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 = z^2, where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x < y < z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values 0 < p <= N such that p is not part of any triple (not just relatively prime triples).

Input

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file

Output

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <=N). The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N. There should be one output line for each input line.

Sample Input

100

Sample Output

1 4

4 9

16 27

Source

Duke Internet Programming Contest 1991,UVA 106

题目类型：本原毕达哥拉斯三元组

算法分析：直接暴力枚举val以内的所有m和n，判断构成三元组的情况并将三元组的倍数标记为True，最后累加[1,val]中没有被标记的数的个数

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

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

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

bool visited[maxn];

int gcd (int a, int b)
{
    if (b == 0)
        return a;

return gcd (b, a % b);
}


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

    int val;

    while (cin >> val)
    {
        memset (visited, false, sizeof (visited));

        int ans1 = 0, ans2 = 0, x, y, z;

        int len = (int) sqrt (val + 0.0);

        int m, n;
        for (n = 1; n <= len; n++)
        {
            for (m = n + 1; m <= len; m++)
            {
                if (m * m + n * n > val)
                    break;

                if (((n & 1) != (m & 1)) && (gcd (m, n) == 1))
                {
                    x = m * m - n * n;
                    y = 2 * m * n;
                    z = m * m + n * n;
                    ans1++;

                    int i;
                    for (i = 1; ; i++)
                    {
                        if (i * z > val)
                            break;

                        visited[i*x] = visited[i*y] = visited[i*z] = true;
                    }
                }
            }
        }

        cout << ans1;
        for (int i = 1; i <= val; i++)
            if (!visited[i])
                ans2++;

        cout << " " << ans2 << endl;
    }

return 0;
}

100

101

102

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

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1000000 + 66;

bool visited[maxn];

int gcd (int a, int b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

int main()

{

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

int val;

while (cin >> val)

{

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

int ans1 = 0, ans2 = 0, x, y, z;

int len = (int) sqrt (val + 0.0);

int m, n;

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

{

for (m = n + 1; m <= len; m++)

{

if (m * m + n * n > val)

break;

if (((n & 1) != (m & 1)) && (gcd (m, n) == 1))

{

x = m * m - n * n;

y = 2 * m * n;

z = m * m + n * n;

ans1++;

int i;

for (i = 1; ; i++)

{

if (i * z > val)

break;

visited[i*x] = visited[i*y] = visited[i*z] = true;

}

cout << ans1;

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

if (!visited[i])

ans2++;

cout << " " << ans2 << endl;

}

return 0;

}

poj1300

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

15 9月 2015

Door Man

You are a butler in a large mansion. This mansion has so many rooms that they are merely referred to by number (room 0, 1, 2, 3, etc...). Your master is a particularly absent-minded lout and continually leaves doors open throughout a particular floor of the house. Over the years, you have mastered the art of traveling in a single path through the sloppy rooms and closing the doors behind you. Your biggest problem is determining whether it is possible to find a path through the sloppy rooms where you:

Always shut open doors behind you immediately after passing through
Never open a closed door
End up in your chambers (room 0) with all doors closed

In this problem, you are given a list of rooms and open doors between them (along with a starting room). It is not needed to determine a route, only if one is possible.

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 M N", where M indicates the butler's starting room, and N indicates the number of rooms in the house (1 <= N <= 20).
Room list - A series of N lines. Each line lists, for a single room, every open door that leads to a room of higher number. For example, if room 3 had open doors to rooms 1, 5, and 7, the line for room 3 would read "5 7". The first line in the list represents room 0. The second line represents room 1, and so on until the last line, which represents room (N - 1). It is possible for lines to be empty (in particular, the last line will always be empty since it is the highest numbered room). On each line, the adjacent rooms are always listed in ascending order. It is possible for rooms to be connected by multiple doors!
End line - A single line, "END"

Following the final data set will be a single line, "ENDOFINPUT".

Note that there will be no more than 100 doors in any single data set.

Output

For each data set, there will be exactly one line of output. If it is possible for the butler (by following the rules in the introduction) to walk into his chambers and close the final open door behind him, print a line "YES X", where X is the number of doors he closed. Otherwise, print "NO".

Sample Input

START 1 2

END

START 0 5

1 2 2 3 3 4 4

END

START 0 10

1 9

END

ENDOFINPUT

Sample Output

YES 1

YES 10

Source

South Central USA 2002

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

算法分析：使用stringstream将读入的数据构建一个度数表，然后按照判断欧拉回路和欧拉路径的方法直接判断即可。注意输入的格式和方法

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

int deg[maxn];

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

    char str[66];
    int st, n;

    string s;
    stringstream ss;

    while (getline (cin, s))
    {
        if (s[0] == 'E')
            break;

        ss.clear ();
        ss.str (s);

        ss >> str >> st >> n;

        int i;
        memset (deg, 0, sizeof (deg));

        int door = 0;
        for (i = 0; i < n; i++)
        {
            getline (cin, s);
            ss.clear ();
            ss.str (s);

            int temp;
            while (ss >> temp)
            {
                deg[i]++;
                deg[temp]++;
                door++;
            }
        }
        getline (cin, s);

        int even = 0, odd = 0;
        for (i = 0; i < n; i++)
        {
            if (deg[i] % 2)
                odd++;

            else
                even++;
        }

        if (odd == 0 && st == 0)
            cout << "YES " << door << endl;

        else if (odd == 2 && st != 0 && deg[st] % 2 && deg[0] % 2)
            cout << "YES " << door << endl;

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

return 0;
}

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

int deg[maxn];

int main()

{

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

char str[66];

int st, n;

string s;

stringstream ss;

while (getline (cin, s))

{

if (s[0] == 'E')

break;

ss.clear ();

ss.str (s);

ss >> str >> st >> n;

int i;

memset (deg, 0, sizeof (deg));

int door = 0;

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

{

getline (cin, s);

ss.clear ();

ss.str (s);

int temp;

while (ss >> temp)

{

deg[i]++;

deg[temp]++;

door++;

}

getline (cin, s);

int even = 0, odd = 0;

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

{

if (deg[i] % 2)

odd++;

else

even++;

}

if (odd == 0 && st == 0)

cout << "YES " << door << endl;

else if (odd == 2 && st != 0 && deg[st] % 2 && deg[0] % 2)

cout << "YES " << door << endl;

else

cout << "NO" << endl;

}

return 0;

}

poj1287

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

15 9月 2015

Networking

You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable that is needed to connect the points over that route. Note that there may exist many possible routes between two given points. It is assumed that the given possible routes connect (directly or indirectly) each two points in the area. Your task is to design the network for the area, so that there is a connection (direct or indirect) between every two points (i.e., all the points are interconnected, but not necessarily by a direct cable), and that the total length of the used cable is minimal.

Input

The input file consists of a number of data sets. Each data set defines one required network. The first line of the set contains two integers: the first defines the number P of the given points, and the second the number R of given routes between the points. The following R lines define the given routes between the points, each giving three integer numbers: the first two numbers identify the points, and the third gives the length of the route. The numbers are separated with white spaces. A data set giving only one number P=0 denotes the end of the input. The data sets are separated with an empty line.
The maximal number of points is 50. The maximal length of a given route is 100. The number of possible routes is unlimited. The nodes are identified with integers between 1 and P (inclusive). The routes between two points i and j may be given as i j or as j i.

Output

For each data set, print one number on a separate line that gives the total length of the cable used for the entire designed network.

Sample Input

1 0

2 3

1 2 37

2 1 17

1 2 68

3 7

1 2 19

2 3 11

3 1 7

1 3 5

2 3 89

3 1 91

1 2 32

5 7

1 2 5

2 3 7

2 4 8

4 5 11

3 5 10

1 5 6

4 2 12

Sample Output

Source

Southeastern Europe 2002

题目类型：MST

算法分析：读入边的信息，然后直接使用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;

const int maxn = 66 + 66;

int parent[maxn];

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

Node edge[666666];
int sum;
int P, R;

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 = P;
	for (i = 0; i < R && 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 >> P)
	{
		if (P == 0)
			break;

		cin >> R;

		int i;
		for (i = 0; i < R; i++)
			cin >> edge[i].u >> edge[i].v >> edge[i].w;

		sort (edge, edge + R, Cmp);

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

		sum = 0;

		kruskal ();

		cout << sum << endl;
	}
	
return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 66 + 66;

int parent[maxn];

struct Node

{

int u, v, w;

};

Node edge[666666];

int sum;

int P, R;

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 = P;

for (i = 0; i < R && 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 >> P)

{

if (P == 0)

break;

cin >> R;

int i;

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

cin >> edge[i].u >> edge[i].v >> edge[i].w;

sort (edge, edge + R, Cmp);

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

parent[i] = -1;

sum = 0;

kruskal ();

cout << sum << endl;

}

return 0;

}

poj1284

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

15 9月 2015

Primitive Roots

We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xⁱ mod p) | 1 <= i <= p-1 } is equal to { 1, ..., p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7. Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.

Input

Each line of the input contains an odd prime numbers p. Input is terminated by the end-of-file seperator.

Output

For each p, print a single number that gives the number of primitive roots in a single line.

Sample Input

Sample Output

Source

贾怡@pku

题目类型：欧拉函数

算法分析：由于素数p有phi(p - 1)个原根，所以直接计算在p - 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>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

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

long long GetEuler (long long val)
{
    long long ans = val;
    for (long long i = 2; i * i <= val; i++)
    {
        if (val % i == 0)
        {
            ans -= ans / i;

            while (val % i == 0)
            {
                val /= i;
            }
        }
    }

    if (val > 1)
        ans -= ans / val;

return ans;
}

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

    long long val;
    while (cin >> val)
    {
        cout << GetEuler (val - 1) << 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>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 10000000 + 66;

long long GetEuler (long long val)

{

long long ans = val;

for (long long i = 2; i * i <= val; i++)

{

if (val % i == 0)

{

ans -= ans / i;

while (val % i == 0)

{

val /= i;

}

if (val > 1)

ans -= ans / val;

return ans;

}

int main()

{

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

long long val;

while (cin >> val)

{

cout << GetEuler (val - 1) << endl;

}

return 0;

}

poj1273

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

15 9月 2015

Drainage Ditches

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch. Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

Sample Output

Source

USACO 93

题目类型：最大流

算法分析：直接建图，使用EK算法求解即可

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


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

Node edge[maxn][maxn];
int n, m;
int vis[maxn], pre[maxn], res[maxn][maxn];

void FindAugmentPath (int s, int t)
{
	memset (vis, 0, sizeof (vis));
	memset (res, 0, sizeof (res));
	memset (pre, 0, sizeof (pre));
	pre[s] = s, vis[s] = 1;
	queue <int> qu;
	qu.push(s);

	while(!qu.empty() && pre[t] == 0)
	{
        int tt = qu.front(); qu.pop ();
        for (int i = 1; i <= n; i++)
		{
            if (!vis[i])
			{
                if (edge[tt][i].f < edge[tt][i].c)
				{
					res[tt][i] = edge[tt][i].c - edge[tt][i].f;
					vis[i] = 1, pre[i] = tt, qu.push(i);
				}

				else if (edge[i][tt].f > 0)
				{
					res[tt][i] = edge[i][tt].f;
					vis[i] = 1, pre[i] = tt, qu.push(i);
				}
			}
		}
	}
}

long long GetAugmentFlow (int s, int t)
{
    if (pre[t] == 0)
		return 0;

	int pa = t, pb = INF;
	while (pa != s)
	{
        if (res[pre[pa]][pa] < pb)
			pb = res[pre[pa]][pa];

		pa = pre[pa];
	}

	return pb;
}

void UpDateFlow (int s, int t, int v)
{
	if (pre[t] == 0)
		return ;

    int pa = t;
    while (pa != s)
	{
        if (edge[pre[pa]][pa].c > edge[pre[pa]][pa].f)
			edge[pre[pa]][pa].f += v;

		else if (edge[pa][pre[pa]] .f > 0)
			edge[pre[pa]][pa].f += v;

		pa = pre[pa];
	}
}

long long Edmonds_Karp (int s, int t)
{
    long long maxflow = 0, tt;
    while (1)
	{
        FindAugmentPath (s, t);
        tt = GetAugmentFlow (s, t);
        maxflow += tt;
        if (tt > 0)
			UpDateFlow (s, t, tt);

		else
			return maxflow;
	}
}

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

    while (cin >> m >> n)
	{
		memset (edge, 0, sizeof (edge));
        for (int i = 1; i <= m; i++)
		{
            int u, v, w;
            cin>> u >> v >> w;
            edge[u][v].c += w;
		}

		cout << Edmonds_Karp(1, n) << endl;
	}

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

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

struct Node

{

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

};

Node edge[maxn][maxn];

int n, m;

int vis[maxn], pre[maxn], res[maxn][maxn];

void FindAugmentPath (int s, int t)

{

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

memset (res, 0, sizeof (res));

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

pre[s] = s, vis[s] = 1;

queue <int> qu;

qu.push(s);

while(!qu.empty() && pre[t] == 0)

{

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

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

{

if (!vis[i])

{

if (edge[tt][i].f < edge[tt][i].c)

{

res[tt][i] = edge[tt][i].c - edge[tt][i].f;

vis[i] = 1, pre[i] = tt, qu.push(i);

}

else if (edge[i][tt].f > 0)

{

res[tt][i] = edge[i][tt].f;

vis[i] = 1, pre[i] = tt, qu.push(i);

}

long long GetAugmentFlow (int s, int t)

{

if (pre[t] == 0)

return 0;

int pa = t, pb = INF;

while (pa != s)

{

if (res[pre[pa]][pa] < pb)

pb = res[pre[pa]][pa];

pa = pre[pa];

}

return pb;

}

void UpDateFlow (int s, int t, int v)

{

if (pre[t] == 0)

return ;

int pa = t;

while (pa != s)

{

if (edge[pre[pa]][pa].c > edge[pre[pa]][pa].f)

edge[pre[pa]][pa].f += v;

else if (edge[pa][pre[pa]] .f > 0)

edge[pre[pa]][pa].f += v;

pa = pre[pa];

}

long long Edmonds_Karp (int s, int t)

{

long long maxflow = 0, tt;

while (1)

{

FindAugmentPath (s, t);

tt = GetAugmentFlow (s, t);

maxflow += tt;

if (tt > 0)

UpDateFlow (s, t, tt);

else

return maxflow;

}

int main()

{

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

while (cin >> m >> n)

{

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

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

{

int u, v, w;

cin>> u >> v >> w;

edge[u][v].c += w;

}

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

}

return 0;

}

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;

}

返回首页上一页 4 5 6 7 8 下一页最后一页

超客的水墨烟雨

poj1458

poj1456

poj1442

poj1365

poj1330

poj1325

poj1321

poj1320

poj1316

poj1305

poj1300

poj1287

poj1284

poj1273

poj1258

poj1251

分类目录

标签云

书签

近期评论

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