Category Archives: POJ

POJ 3070-Fibonacci

POJ 3070-Fibonacci

Fibonacci
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 14933 Accepted: 10500

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

.

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

Hint

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

.

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

.

Source

Stanford Local 2006


斐波那契数列是这样一个数列:0,1,1,2,3,5...,其数学定义为:

\begin{equation}f(n)=\begin{cases} 0, & n=0;\\ 1, & n=1;\\ f(n-1)+f(n-2), & n>1.\end{cases}\end{equation}


最简单的递归解法为:

typedef long long LL;
LL Fib1(int n) {
	if (n == 0)return 0;
	if (n == 1)return 1;
	return Fib1(n - 1) + Fib1(n - 2);
}

这种算法的时间复杂度是O(2^n)的。
但是这种解法有很多重复计算,比如算f(8)=f(7)+f(6)时,f(7)重复计算了f(6)。所以我们可以从小开始算起,把f(n)的前两个值保存下来,每次滚动赋值,代码如下:

LL Fib2(int n) {
	if (n == 0)return 0;
	if (n == 1)return 1;
	LL fn_2 = 0, fn_1 = 1, ans = 0;
	for (int i = 2; i <= n; ++i) {
		ans = fn_1 + fn_2;
		fn_2 = fn_1;
		fn_1 = ans;
	}
	return ans;
}

这种算法的时间复杂度是O(n)的。
最近遇到快速幂相关的题,发现求解斐波那契数列也可以用快速幂来求解,时间复杂度居然能降到O(lgn)
题目的图中给出了斐波那契数列的矩阵形式,f(n)为矩阵[1,1;1,0]的n次幂的第一行第二个数。可以用归纳法证明矩阵的n次幂和数的n次幂都可以用快速幂来求解,时间复杂度能降到O(lgn)。代码如下:

const int MAXN = 2;
vector<vector<LL>> multi(const vector<vector<LL>> &mat1, const vector<vector<LL>> &mat2) {
	vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
	for (int i = 0; i < MAXN; ++i) {
		for (int j = 0; j < MAXN; ++j) {
			for (int k = 0; k < MAXN; ++k) {
				mat[i][j] += mat1[i][k] * mat2[k][j];
			}
		}
	}
	return mat;
}
vector<vector<LL>> fastPow(vector<vector<LL>> &mat1, int n) {
	vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
	for (int i = 0; i < MAXN; ++i)mat[i][i] = 1;
	while (n != 0) {
		if (n & 1)mat = multi(mat, mat1);
		mat1 = multi(mat1, mat1);
		n >>= 1;
	}
	return mat;
}
LL Fib3(int n) {
	if (n == 0)return 0;
	if (n == 1)return 1;
	vector<vector<LL>> mat = { {1,1},{1,0} };
	vector<vector<LL>> matN = fastPow(mat, n);
	return matN[0][1];
}

POJ这题的代码如下,古老的POJ居然不支持第37行的vector初始化,崩溃。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int MAXN = 2;
const int MOD = 10000;
vector<vector<LL>> multi(const vector<vector<LL>> &mat1, const vector<vector<LL>> &mat2) {
	vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
	for (int i = 0; i < MAXN; ++i) {
		for (int j = 0; j < MAXN; ++j) {
			for (int k = 0; k < MAXN; ++k) {
				mat[i][j] = (mat[i][j] + mat1[i][k] * mat2[k][j]) % MOD;
			}
		}
	}
	return mat;
}
vector<vector<LL>> fastPow(vector<vector<LL>> &mat1, int n) {
	vector<vector<LL>> mat(MAXN, vector<LL>(MAXN, 0));
	for (int i = 0; i < MAXN; ++i)mat[i][i] = 1;
	while (n != 0) {
		if (n & 1)mat = multi(mat, mat1);
		mat1 = multi(mat1, mat1);
		n >>= 1;
	}
	return mat;
}
LL Fib3(int n) {
	if (n == 0)return 0;
	if (n == 1)return 1;
	//vector<vector<LL>> mat = { { 1,1 },{ 1,0 } };
	//-----------------------
	vector<vector<LL>> mat;
	vector<LL> r1;
	r1.push_back(1), r1.push_back(1);
	vector<LL> r2;
	r2.push_back(1), r2.push_back(0);
	mat.push_back(r1);
	mat.push_back(r2);
	//----------------------
	vector<vector<LL>> matN = fastPow(mat, n);
	return matN[0][1];
}
int main() {
	int n;
	while (scanf("%d", &n) && n != -1) {
		LL ans = Fib3(n);
		printf("%d\n", ans%MOD);
	}
	return 0;
}

本代码提交AC,用时32MS,真的好快呀。

POJ 2369-Permutations

POJ 2369-Permutations
Permutations
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2792 Accepted: 1473
Description
We remind that the permutation of some final set is a one-to-one mapping of the set onto itself. Less formally, that is a way to reorder elements of the set. For example, one can define a permutation of the set {1,2,3,4,5} as follows:

This record defines a permutation P as follows: P(1) = 4, P(2) = 1, P(3) = 5, etc.
What is the value of the expression P(P(1))? It’s clear, that P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3. One can easily see that if P(n) is a permutation then P(P(n)) is a permutation as well. In our example (believe us)

It is natural to denote this permutation by P2(n) = P(P(n)). In a general form the defenition is as follows: P(n) = P1(n), Pk(n) = P(Pk-1(n)). Among the permutations there is a very important one — that moves nothing:

It is clear that for every k the following relation is satisfied: (EN)k = EN. The following less trivial statement is correct (we won't prove it here, you may prove it yourself incidentally): Let P(n) be some permutation of an N elements set. Then there exists a natural number k, that Pk = EN. The least natural k such that Pk = EN is called an order of the permutation P.
The problem that your program should solve is formulated now in a very simple manner: "Given a permutation find its order."
Input
In the first line of the standard input an only natural number N (1 <= N <= 1000) is contained, that is a number of elements in the set that is rearranged by this permutation. In the second line there are N natural numbers of the range from 1 up to N, separated by a space, that define a permutation — the numbers P(1), P(2),…, P(N).
Output
You should write an only natural number to the standard output, that is an order of the permutation. You may consider that an answer shouldn't exceed 109.
Sample Input
5
4 1 5 2 3
Sample Output
6
Source
Ural State University Internal Contest October'2000 Junior Session


有一个序列和一个置换T,问对这个序列置换多少次能恢复成原来的序列。这其实就是求置换群T的秩k使得T^k=e,e为单位置换f(x)=x。
在离散数学中有一个定理,k等于T中所有循环节长度的最小公倍数。
比如题中的P(n)有1->4->2->1,则循环节长度就为3,以及3->5->3,循环节长度为2,则最小公倍数为lcm(3,2)=6,即k=6。
设x,y的最小公倍数为lcm(x,y),最大公约数为gcd(x,y),则有gcd(x, y)×lcm(x, y) = xy,挺神奇的,所以求最小公倍数可以转换为求最大公约数。
完整代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 1005;
bool visited[kMaxN];
int permutation[kMaxN];
//最大公约数
int gcd(int x, int y)
{
	int tmp;
	while (y)
	{
		tmp = y;
		y = x % y;
		x = tmp;
	}
	return x;
}
int main()
{
	int n,ans,len;
	while (scanf("%d", &n)!=EOF)
	{
		ans = 1;
		memset(visited, false, n + 1);
		for (int i = 1; i <= n; i++)
			scanf("%d", &permutation[i]);
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = true;
				int j = permutation[i];
				len = 1;
				while (j!=i)
				{
					visited[j] = true;
					j = permutation[j];
					len++;
				}
				ans = len*ans/gcd(ans, len);//gcd(a, b)×lcm(a, b) = ab
			}
		}
		printf("%dn", ans);
	}
	return 0;
}

本代码提交AC,用时0MS,内存136K。

POJ 2352-Stars

POJ 2352-Stars
Stars
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 36453 Accepted: 15852
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
Source
Ural Collegiate Programming Contest 1999


星星的level为其左下星星的数量,要求输出level从0~n-1的星星的个数。
因为本题的数据已经按先Y后X从小到大排好序了,所以后面的星星一定不可能出现在前面星星的左下部分,所以当来了一个星星(x,y)之后,只需求出之前出现过的星星中x'<=x的星星的个数。
所以可以只考虑星星的x坐标。假设有一个数组A[],A[x]表示横坐标为x的星星的个数,则可以画出这样一张图:

树状数组[1]

当来了一个横坐标为4的星星之后,其level正是A[1]+...+A[4]=C[4],在树状数组中正好是其左下方的和。
关于树状数组可以参考[1]的文章。
所以横坐标为4的星星的level就是sum(4)。当又来了一个横坐标为4的星星之后,需要修改A[4],使A[4]++,其实就是A[4]+1,可以使用add(4,1)操作。
因为本题中x可能等于0,但是树状数组中下标从1开始,所以需要整体将x+1。本题是树状数组的一个简单应用,完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 32005;//NOT 15005;
int n;
int level[kMaxN];
int c[kMaxN];
int lowbit(int x)
{
	return x&(-x);
}
int sum(int i)
{
	int rs = 0;
	while (i > 0)
	{
		rs += c[i];
		i -= lowbit(i);
	}
	return rs;
}
void add(int i, int val)
{
	while (i <= kMaxN)
	{
		c[i]+=val;
		i += lowbit(i);
	}
}
int main()
{
	scanf("%d", &n);
	int x, y;
	for (int i = 0; i < n; i++)
	{
		scanf("%d %d", &x, &y);
		x++;
		level[sum(x)]++;
		add(x, 1);
	}
	for (int i = 0; i < n; i++)
		printf("%dn", level[i]);
	return 0;
}

本代码提交AC,用时188MS,内存344K。
参考:
[1]. http://www.cnblogs.com/Creator/archive/2011/09/10/2173217.html

POJ 1386-Play on Words

POJ 1386-Play on Words
Play on Words
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10039 Accepted: 3441
Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm'' can be followed by the word ``motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
Source
Central Europe 1999


给定一系列字符串,问能否将这些字符串依次首尾相连成一个长串,字符串a和b能够相连的条件就是a的最后一个字母和b的第一个字母相同。
这个题目很有意思,像小时候玩的扑克牌游戏“钓鱼”。我一开始想到的是方法是深度优先搜索DFS,在输入的时候将字符串按首字母不同分到不同的队列里面,然后枚举每一个字符串为第一个字符串,进行DFS,如果DFS结束之后遍历了所有字符串,则成功,否则失败。
用枚举+DFS的方法代码如下:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int M=26;
int n,used;
vector<vector<string> > s;
//vector<string> rs;//rs内字符串的先后顺序就是这个游戏的先后顺序
bool dfs(string last)
{
	//rs.push_back(last);//记录字符串
	used++;
	if(used==n)
		return true;
	else
	{
		int c=last[last.size()-1]-'a';
		int sz=s.size();
		for(int i=0;i<sz;i++)
		{
			if(dfs(s[i]))
				return true;
			else
				used--;//rs.pop_back();//回溯
		}
		return false;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t;
	string tmp;
	cin>>t;
	while(t--)
	{
		cin>>n;
		s.clear();
		s.resize(M);
		for(int i=0;i<n;i++)
		{
			cin>>tmp;
			s[tmp[0]-'a'].push_back(tmp);
		}
		bool success=false;
		for(int i=0;i<M;i++)
		{
			int sz=s[i].size();
			for(int j=0;j<sz;j++)
			{
				used=0;
				success=false;
				if(dfs(s[i][j]))
				{
					success=true;
					break;
				}
			}
			if(success)
				break;
		}
		if(success)
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}

这一版代码提交MLT,估计是DFS递归栈太深导致的,看来只能想其他办法了。
看了讨论后,发现大多数方法是欧拉路+并查集/DFS。我们先来复习一下欧拉路:
通过图(无向图或有向图)中所有边一次且仅一次,行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。
根据定义,欧拉回路肯定是欧拉通路。相关定理有:
1.无向连通图G是欧拉图,当且仅当G不含奇数度结点(G的所有结点度数为偶数);
2.无向连通图G含有欧拉通路,当且仅当G有零个或两个奇数度的结点;
3.有向连通图D是欧拉图,当且仅当D的基图(即其无向图)为连通图且D中每个结点的入度=出度
4.有向连通图D含有欧拉通路,当且仅当D的基图(即其无向图)为连通图且D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=±1。(起始点s的入度=出度-1,结束点t的出度=入度-1 或两个点的入度=出度)
5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
6.如果图G是欧拉图且 H = G - uv,则H有奇数个u,v-迹仅在最后访问v;同时,在这一序列的u,v-迹中,不是路径的迹的条数是偶数。(Todia[1973])
以上内容摘自百度百科·欧拉图;关于欧拉路,还可以参考这篇文章。对于本题,我们可以把一个单词的首尾字母看成图的一条边,比如增加"acm"这个单词,则在图上增加一条a->m的有向边。要使所有字符串组成一个首尾相连的长串,等价于在a~z这26个字符串为点构成的图中只存在一条欧拉通路。判断是否存在欧拉通路可以用上面的定理3和4;判断是否只有一条欧拉通路(也就是判断基图是否连通)就需要借助并查集或者DFS,如果用并查集,要保证所有有边的点属于同一个集合;如果用DFS,则从图的某个点出发能遍历到所有右边的点。我使用的是并查集。
理清思路之后就可以开始写代码了,欧拉路+并查集版本的代码如下:

#include<iostream>
#include<string>
using namespace std;
const int M=26;
int n;
int showed[M];//showed[i]表示点i出现过,也就是有边连在i点
int G[M][M];//图
int father[M];//并查集
int degree[M][2];//degree[i][0]入度;degree[i][1]出度
void init_data()
{
	for(int i=0;i<M;i++)
	{
		father[i]=i;
		showed[i]=0;
		degree[i][0]=0;
		degree[i][1]=0;
		for(int j=0;j<M;j++)
			G[i][j]=0;
	}
}
int find_father(int x)
{
	return x==father[x]?x:(father[x]=find_father(father[x]));
}
void union_father(int x,int y)
{
	father[find_father(x)]=find_father(y);
}
//判断有边的点是否属于一个集合
bool is_one_set()
{
	int root=-1;
	for(int i=0;i<M;i++)
	{
		if(showed[i]==1)//有边
		{
			int tmp=find_father(i);
			if(root==-1)
				root=tmp;
			else if(tmp!=root)
				return false;
		}
	}
	return true;
}
bool judge()
{
	if(!is_one_set())
		return false;
	else
	{
		for(int i=0;i<M;i++)
		{
			for(int j=0;j<M;j++)
			{
				if(G[i][j]!=0)
				{
					degree[i][1]+=G[i][j];
					degree[j][0]+=G[i][j];
				}
			}
		}
		int a=0,b=0;//a:入度-出度=-1的个数;b:入度-出度=1的个数
		for(int i=0;i<M;i++)
		{
			int rs=degree[i][0]-degree[i][1];
			if(rs==-1)
				a++;
			else if(rs==1)
				b++;
			else if(rs!=0)
				return false;
		}
		if((a==1&&b==1)||(a==0&&b==0))//欧拉回路或欧拉通路
			return true;
		return false;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t,a,b;
	string tmp;
	cin>>t;
	while(t--)
	{
		cin>>n;
		init_data();
		for(int i=0;i<n;i++)
		{
			cin>>tmp;
			a=tmp[0]-'a';
			b=tmp[tmp.size()-1]-'a';
			showed[a]=1;
			showed[b]=1;
			G[a][b]++;//首字母指向尾字母的边
			union_father(a,b);//首字母指向尾字母的边
		}
		if(judge())
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}

本代码提交AC,用时782MS,内存244K。

POJ 1061-青蛙的约会

POJ 1061-青蛙的约会
青蛙的约会
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 92723 Accepted: 17043
Description
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
Output
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4
Source
浙江


本题考察数论的相关知识。假设A,B跳了k次后相遇,则有方程(x+km)modL=(y+kn)modL成立,即(x+km-y-kn)=tL,k和t即为我们要求的一组解。
令a=m-n; b=y-x;则上式转换为

ka+tL=b \ \ ---------------(1)


因为t可正可负,所以这里加号减号都可以。
根据裴蜀定理,要使ka+tL=b有整数解,必须满足b是d的倍数,其中d是a和L的最大公约是,即d=gcd(a,L)。所以我们首先利用欧几里得算法求a,L的最大公约d,判断b是否是d的倍数,如果不是,则直接输出Impossible。
如果b是d的倍数,那么怎样来求解ka+tL=b这个二元一次方程呢?
将(1)式同时除以d,得到

k(a/d)+t(L/d)=(b/d) \ \ ---------------(2)


(1)式和(2)式的解是完全等价的。
因为d=gcd(a,L),且b是d的倍数,所以a/d, L/d, b/d都是整数,并且gcd(a/d, L/d)=1。所以我们可以先求得

k(a/d)+t(L/d)=gcd(a/d, L/d)=1 \ \ ---------------(3)


的解,再将解乘以(b/d)不就是式(2)的解了吗,那么怎样求(3)式的解呢,这时候要用到扩展欧几里得算法,维基百科上有具体的演算例子,不懂的可以参考,下图是《算法导论》上关于扩展欧几里得算法算法的描述,也非常清晰易懂:

设利用扩展欧几里得算法求到的式(3)的解为k_0t_0,那么式(2)的解为k=(b/d)k_0t=(b/d)t_0。那么最小的k是多少呢?
又因为根据数论中的相关定理,如果ax+by=m有一组解(x0,y0),则整个解系为x=x0+ub; y=y0+ua; 其中u为整数,所以对照等式(2)可得k的解系为k=(b/d)k_0+u(L/d),它的最小值就是这个解系中的最小正整数。
理清了上述关系后,可以开始写代码了,如下:

#include<stdio.h>
#define LL long long
LL x,y,m,n,L,k0,t0,d;//k0,t0为某一组解,d为最大公因数
//求a,b的最大公因数
LL gcd(LL a,LL b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
//扩展欧几里得算法求ax+by=gcd(a,b)的一组解(x,y)
void extended_euclid(LL a,LL b,LL& x,LL& y)
{
	if(b==0)
	{
		x=1;
		y=0;
	}
	else
	{
		extended_euclid(b,a%b,x,y);
		LL tmp=x;
		x=y;
		y=tmp-(a/b)*y;
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	LL a,b;
	while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L)!=EOF)
	{
		if(m==n)//因为青蛙起点不一样,如果速度一样,肯定不可能相遇
		{
			printf("Impossible\n");
			continue;
		}
		a=m-n;
		b=y-x;
		if(a<0)//扩展欧几里得需要非负数
		{
			a=-a;
			b=-b;
		}
		d=gcd(a,L);
		if(b%d!=0)
		{
			printf("Impossible\n");
			continue;
		}
		a/=d;
		L/=d;
		b/=d;
		extended_euclid(a,L,k0,t0);
		k0*=b;
		t0*=b;//无需求解,没用到
		if(k0>0)
			k0=k0%L;
		else
			k0=k0%L+L;
		printf("%lld\n",k0);
	}
	return 0;
}

本代码提交AC,用时0MS,内存132K。
因为扩展欧几里得算法包含了欧几里得算法,所以该代码还可以稍微优化一下。

POJ 1163-The Triangle

POJ 1163-The Triangle
The Triangle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 38525 Accepted: 23126
Description

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 diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Source
IOI 1994


DP水题一个,如果将等边三角形转换成Sample Input里的等腰直角三角形,设则某一点的路径和为sum[i][j],则因为只能从(i-1,j)和(i-1,j-1)这两个点到达(i,j),所以sum[i][j]=max{sum[i-1][j],sum[i-1][j-1]}+triangle[i][j]。如果为了节省空间,j可以从i downto 0循环,也就是DP表从右往左填,这样只需要一行空间。
不多说,简单题,直接上代码。

#include<iostream>
using namespace std;
const int MAX_N=101;
int triangle[MAX_N][MAX_N];
int sum[MAX_N]={0};
int DP(int n)
{
     int rs=0;
     for(int i=0;i<n;i++)
     {
          for(int j=i;j>=0;j--)//从右往左填表,只需一行空间
          {
               if(j>0)
               {
                    sum[j]=(sum[j]>sum[j-1]?sum[j]:sum[j-1])+triangle[i][j];
               }
               else if(j==0)
               {
                    sum[j]+=triangle[i][j];
               }
               if(sum[j]>rs)//记录最大值
                    rs=sum[j];
          }
     }
     /*int rs=0;
     for(int i=0;i<n;i++)
          if(sum[i]>rs)
               rs=sum[i];*/
     return rs;
}
int main()
{
     //freopen("input.txt","r",stdin);
     int n;
     cin>>n;
     for(int i=0;i<n;i++)
          for(int j=0;j<=i;j++)
               cin>>triangle[i][j];
     cout<<DP(n);
     return 0;
}

本代码提交AC,用时0MS,内存260K。

POJ 1330-Nearest Common Ancestors

POJ 1330-Nearest Common Ancestors
Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19432 Accepted: 10292
Description
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
2
16
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
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
Source
Taejon 2002


昨天被hihoCoder Problem 1067: 最近公共祖先·二的离线算法虐了之后,今天在POJ上找了一个水题来重塑信心,这个题也是最近公共祖先问题,只不过它是目前为止最简单的,和hihoCoder Problem 1062: 最近公共祖先·一类似,甚至更简单,因为这个题每个case只询问一次,所以没必要用离线算法,而且给的就是数字,不是字符串,连转换都不要。直接记录一个节点node1的所有祖先,然后从下往上查找另一个节点node2的所有祖先,每找到一个祖先,则判断这个祖先是否是node1的祖先,如果是,则这就是他们的公共祖先。
这一次我甚至连set和map都没有用,因为给定的是连续的整数,直接用数组当hash即可,而且查找效率比set和map还快。
完整代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     //freopen("input.txt","r",stdin);
     int t,n;
     int node1,node2;
     cin>>t;
     while(t--)
     {
          cin>>n;
          vector<int> s_f(n+1,0);//s_f[i]为第i个节点的父亲,开始时所有节点的父亲为0
          for(int i=0;i<n-1;i++)
          {
               cin>>node1>>node2;
               s_f[node2]=node1;//保存输入关系
          }
          cin>>node1>>node2;
          vector<int> node1_father(n+1,0);//node1的父亲
          node1_father[node1]=1;//自己是自己的祖先
          while(s_f[node1]!=0)
          {
               node1_father[s_f[node1]]=1;//记录哪些点是node1的父亲
               node1=s_f[node1];
          }
          if(node1_father[node2]!=0)//node2也是自己的祖先
          {
               cout<<node2<<endl;
               continue;
          }
          while(s_f[node2]!=0)
          {
               if(node1_father[s_f[node2]]!=0)//从下网上找node2的祖先是否出现在node1的祖先里
               {
                    cout<<s_f[node2]<<endl;
                    break;
               }
               else
                    node2=s_f[node2];
          }
     }
     return 0;
}

本代码提交AC,用时125MS,内存336K。
关于最近公共祖先问题,还有一种牛逼的在线算法RMQ,在hihoCoder上也有提到,下回再战!

POJ 1080-Human Gene Functions

POJ 1080-Human Gene Functions
Human Gene Functions
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17334 Accepted: 9637
Description
It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them.
A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function.
One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions – many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet.
A database search will return a list of gene sequences from the database that are similar to the query gene.
Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.
Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity
of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of
the genes to make them equally long and score the resulting genes according to a scoring matrix.
For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in –GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal
length. These two strings are aligned:
AGTGAT-G
-GT--TAG
In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.
![](http://poj.org/images/1080/1080_1.gif)
denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.
Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):
AGTGATG
-GTTA-G
This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the
similarity of the two genes is 14.
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 consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100.
Output
The output should print the similarity of each test case, one per line.
Sample Input
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
Sample Output
14
21
Source
Taejon 2001


这一题是LCS(最长公共子序列)的变种,但是还是用DP来解决。
题目问给两个基因序列s1,s2插入'-',使得两个序列的`相似度`最大,求最大的相似度。假设f[i-1,j-1]为s1[1,...,i-1]和s2[1,...,j-1]的最大相似度,怎么通过f[i-1,j-1]来求f[i,j]呢?分如下三种情况:(这里假设f下标从0开始,s1,s2下标从1开始)
1. s1取第i个基因,s2取'-',则f[i,j]=f[i-1,j]+score[s1[i]],'-'];
2. s1取'-',s2取第j个基因,则f[i,j]=f[i,j-1]+score['-',s2[j]];
3. s1取第i个基因,s2取第j个基因,则f[i,j]=f[i-1,j-1]+score[s1[i],s2[j]];
所以f[i,j]即为上述三者的最大值。
对于初始值,自然有f[0,0]=0; f[0,j]=f[0,j-1]+score['-',s2[j]]; f[i,0]=f[i-1,0]+score[s1[i],'-']。
有了上述状态转换方程及初始值,便可以写出DP代码:

#include<iostream>
#include<string>
using namespace std;
int score['T'+1]['T'+1];
int inf=-5;//负无穷
const int MAX_N=101;//基因最大长度
int f[MAX_N][MAX_N];//f[i][j]表示s1[0...i-1]和s2[0...j-1]的相识度
//初始化分数表
void init_score()
{
     score['A']['A']=score['C']['C']=score['G']['G']=score['T']['T']=5;//可以连续赋值
     score['-']['-']=inf;//负无穷
     score['A']['C']=score['C']['A']=-1;
     score['A']['G']=score['G']['A']=-2;
     score['A']['T']=score['T']['A']=-1;
     score['A']['-']=score['-']['A']=-3;//'-'的ASCII小于'T'
     score['C']['G']=score['G']['C']=-3;
     score['C']['T']=score['T']['C']=-2;
     score['C']['-']=score['-']['C']=-4;
     score['G']['T']=score['T']['G']=-2;
     score['G']['-']=score['-']['G']=-2;
     score['T']['-']=score['-']['T']=-1;
}
//动态规划求值
int DP(string s1,int n1,string s2,int n2)
{
     f[0][0]=0;
     for(int i=1;i<=n1;i++)
          //f[0][i]=f[0][i-1]+score['-'][s1[i-1]];//注意顺序不要弄错了,这里表示i,s1为纵轴;j,s2为横轴
          f[i][0]=f[i-1][0]+score[s1[i-1]]['-'];
     for(int j=1;j<=n2;j++)
          //f[j][0]=f[j-1][0]+score[s2[j-1]]['-'];
          f[0][j]=f[0][j-1]+score['-'][s2[j-1]];
     for(int i=1;i<=n1;i++)
     {
          for(int j=1;j<=n2;j++)
          {
               int a=f[i-1][j]+score[s1[i-1]]['-'];
               int b=f[i][j-1]+score['-'][s2[j-1]];
               int c=f[i-1][j-1]+score[s1[i-1]][s2[j-1]];
               int rs=a>b?a:b;
               f[i][j]=rs>c?rs:c;//三者最大值
          }
     }
     return f[n1][n2];
}
int main()
{
     //freopen("input.txt","r",stdin);
     int t;
     cin>>t;
     init_score();
     while(t--)
     {
          int n1,n2;
          string s1,s2;
          cin>>n1>>s1>>n2>>s2;
          cout<<DP(s1,n1,s2,n2)<<endl;
     }
     return 0;
}

本代码提交AC,用时0MS,内存272K。

POJ 1094-Sorting It All Out

POJ 1094-Sorting It All Out
Sorting It All Out
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 28397 Accepted: 9814
Description
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sample Input
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
Source
East Central North America 2001


这一题有一定的难度,有很多细节需要兼顾。题目的意思为:给定一系列小于关系,问能否从中得出一个严格有序的序列。需要明确的是,题目所指的严格有序的序列需要满足如下几个条件:1.包含n个所有字母;2.每个字母都有明确的大小关系。
另外根据测试样例我们可以知道:每输入一个关系都要判断一次,如果可以得到严格有序序列,则输出结果,但这个测试用例后续的输入还是要输入的;如果出现相互依赖(环),也输出结果,同样的,这个测试用例后面的数据还是要输入;如果所有关系都输入了还不能得出一个严格有序的序列,则输入无法判断。
这一题很自然的想到用拓扑排序来做。下面我们先来回顾一下拓扑排序。

如上图是《算法导论》中关于拓扑排序的一个例子,这是某位教授起床后需要穿戴衣物的顺序,比如只有先穿了袜子才能穿鞋、但是穿鞋和戴手表并没有严格的先后顺序。拓扑排序的功能就是根据图(a)的拓扑图,得到图(b)中节点的先后顺序。
常见的拓扑排序算法有两种:Kahn算法和基于DFS的算法,这两种算法都很好理解,详细的解释请看维基百科Topological sorting,下面简要介绍一下这两个算法。
Kahn算法
拓扑排序强调先后顺序,先做的事情排在前面,那么反应到有向图上,最先做的事情就是没有入度的节点(可能 有/没有 出度)。所以Kahn算法很朴素,他就是把所有没有入度的点加入到集合S中,在S不为空的情况下循环:从S中取出一个节点a,把a加入到L链表的尾部,对于每一条a的出度边,如< a,b>,删除它,并把b的入度减一,如果b的入度也为0了,则又把b加入到集合S中。如果S为空了,但是图中还有边未删除,说明图中至少有一个,拓扑排序失败;否则拓扑排序成功,且链表L保存了一条拓扑排序链。(链表L的生成使用尾插法)
维基百科上关于Kahn算法的伪代码描述如下:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

基于DFS的算法
这个算法类似于深度优先搜索,它不断的递归访问下一个节点,直到不能再递归时,把最后一个节点插入到链表的头部,然后返回。
拿上面穿衣物的例子来说,如果我们首先选择了内裤,则可以递归访问裤子->腰带->夹克。到夹克时,无法递归了,则把夹克插入到L的头部,返回到腰带,腰带也无法递归了,则把腰带插入到L的头部,这个时候就形成了L:腰带->夹克的中间结果,也就是腰带要在夹克前面穿。这个算法不太好表述,还请大家看伪代码领会。(链表L的生成使用头插法)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

那么问题来了,只使用拓扑排序并不能满足本题的要求。因为本题问的是能否生成一个严格有序的序列,一个拓扑序列并不一定是严格有序的序列,比如上图中的穿衣物生成的拓扑序列中,先穿袜子和先穿衬衫都是可以的,也就是说袜子和衬衫是没有明确的先后顺序的,所以这不是一个严格有序的序列。再比如下图的拓扑序列,也不是一个严格有序的序列,因为C和A,D,E,F无法比较大小。

那么怎么判断生产的拓扑序列是否是严格的有序序列呢?基本原则就是就是任意取序列中的两个点,看能不能比较大小,如果能则是严格有序,否则不是。
我起初想到的是对拓扑序列的第一个节点进行深度遍历,遍历之后如果所有的节点都访问了,那么这是一个严格有序的序列,否则不是。后来证明这是不正确的,比如上图从B点开始DFS,遍历完F之后回溯到B点再访问C点,这样即使它不是严格有序的,但DFS还是访问了所有节点。
后来想到了Floyd算法。对拓扑图进行Floyd算法之后,会得到任意两点之间的最短距离。如果拓扑序列中前面的节点都可以到达后面的节点(最短距离不为无穷),则是严格有序的;否则不是。比如上图的一个拓扑序列为BCADEF(不唯一,还可以是BADEFC),但是C到ADEF的最短距离都是无穷,所以这个序列不是严格有序的。
把这些大的问题搞清楚之后就可以写代码了,一些小细节可以看我代码里的注释。

#include<iostream>
//#include<set>
#include<list>
#include<string>
#include<vector>
using namespace std;
int n,m;
const int MAX_N=26;
const int MAX_DIS=10000;
//*******这些都是维基百科关于拓扑排序(DFS版)里的变量含义
int temporary[MAX_N];
int permanent[MAX_N];
int marked[MAX_N];
//*******************************
int path[MAX_N][MAX_N];
//int dfs_visited[MAX_N];
list<int> L;//拓扑排序生产的顺序链
bool isDAG;//DAG=directed acyclic graph,无回路有向图
//每一个测试用例都要初始化路径
void init_path()
{
     for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
               path[i][j]=0;
}
//每一次拓扑排序都要初始化temporary,permanent,marked
void init_tpm()
{
     isDAG=true;
     L.clear();
     for(int i=0;i<n;i++)
     {
          temporary[i]=0;
          permanent[i]=0;
          marked[i]=0;
     }
}
//递归访问。具体看维基百科
void visit(int i)
{
     if(temporary[i]==1)
     {
          isDAG=false;
          return;
     }
     else
     {
          if(marked[i]==0)
          {
               marked[i]=1;
               temporary[i]=1;
               for(int j=0;j<n;j++)
               {
                    if(path[i][j]==1)
                    {
                         visit(j);
                    }
               }
               permanent[i]=1;
               temporary[i]=0;
               L.push_front(i);
          }
     }
}
/*
void init_dfs()
{
     for(int i=0;i<n;i++)
          dfs_visited[i]=0;
}*/
/*
//DFS有缺陷
void DFS(int v)
{
     if(dfs_visited[v]==0)
     {
          dfs_visited[v]=1;
          for(int i=0;i<n;i++)
          {
               if(dfs_visited[i]==0&&path[v][i]==1)
               {
                    DFS(i);
               }
          }
     }
}*/
//使用Floyd算法来判断生产的拓扑排序是否是严格有序的
bool Floyd()
{
     int copy_path[MAX_N][MAX_N];
     for(int i=0;i<n;i++)//首先复制一份路径图
          for(int j=0;j<n;j++)
          {
               copy_path[i][j]=path[i][j];
               if(i!=j&&copy_path[i][j]==0)//如果原来两点距离为0,说明他们是不直接连通的
                    copy_path[i][j]=MAX_DIS;//置为无穷
          }
     //floyd算法
     for(int k=0;k<n;k++)
          for(int i=0;i<n;i++)
               for(int j=0;j<n;j++) if(copy_path[i][j]>copy_path[i][k]+copy_path[k][j])
                         copy_path[i][j]=copy_path[i][k]+copy_path[k][j];
     vector<int> seq;//把原来用链表的拓扑序列转换成数组,方便后面的操作
     list<int>::iterator it=L.begin();
     while(it!=L.end())
     {
          seq.push_back(*it);
          it++;
     }
     //如果这个拓扑链是严格有序的话,则前面的元素到后面的元素一定是可达的。
     for(int i=0;i<n-1;i++)
     {
          for(int j=i+1;j<n;j++) { if(copy_path[seq[i]][seq[j]]>=MAX_DIS)//如果不可达,则不是严格有序的。
                    return false;
          }
     }
     return true;
}
//拓扑排序DFS版本。返回0:有回路;1:虽然是拓扑排序,但非连通(不是严格有序);2:是拓扑排序且连通(严格有序)(即任意两个元素都可以比较大小)
int topological_sorting()
{
     for(int i=0;i<n;i++)
     {
          if(marked[i]==0)
          {
               visit(i);
          }
     }
     if(!isDAG)
          return 0;
     else
     {
          /*init_dfs();
          DFS(*L.begin());
          for(int i=0;i<n;i++) { if(dfs_visited[i]==0) { return 1; } }*/ if(Floyd()) return 2; else return 1; } } int main() { //freopen("input.txt","r",stdin); string tmp; while(cin>>n>>m&&n&&m)
     {
          init_path();
          vector<string> relations(m);
          int i;
          for(i=0;i<m;i++)//一次性把所有输入都存起来,免得后续麻烦 { cin>>relations[i];
          }
          int rs=-1;
          for(i=0;i<m;i++)//每增加一个关系,都要重新拓扑排序一次
          {
               init_tpm();//每次都要初始化
               tmp=relations[i];
               path[tmp[0]-'A'][tmp[2]-'A']=1;
               rs=topological_sorting();
               if(rs==0)
               {
                    cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
                    break;//如果是回路的话,后续的输入可以跳过
               }
               else if(rs==2)//成功
               {
                    cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
                    list<int>::iterator it=L.begin();
                    while(it!=L.end())
                    {
                         char c='A'+*it;
                         cout<<c;
                         it++;
                    }
                    cout<<"."<<endl;
                    break;//后续输入跳过
               }
          }
          if(i==m&&rs==1)//如果处理完所有输入都没有形成严格有序的拓扑序列
               cout<<"Sorted sequence cannot be determined."<<endl;
     }
     return 0;
}

我原本以为又是DFS,又是Floyd,算法时空效率会很低,但是提交后AC,用时125MS,内存244K,也不是很差。
代码中的拓扑排序算法使用的是基于DFS的版本,大家也可以改成Kahn算法。
如果觉得自己的代码是对的,但是提交WA的,可以使用这两个测试数据:数据1数据2

POJ 2263-Heavy Cargo

POJ 2263-Heavy Cargo
Heavy Cargo
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3549 Accepted: 1894
Description
Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.
Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.
Input
The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2<=n<=200) and the number of road segments r (1<=r<=19900) making up the street network.
Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.
The last line of the test case contains two city names: start and destination.
Input will be terminated by two values of 0 for n and r.
Output
For each test case, print three lines:
a line saying "Scenario #x" where x is the number of the test case
a line saying "y tons" where y is the maximum possible load
a blank line
Sample Input
4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0
Sample Output
Scenario #1
80 tons
Scenario #2
170 tons
Source
Ulm Local 1998


题意:给定一个公路核载图,图上标明了每一段公路载重限额,问从A地到B地最多能装载多少吨货物。这一题和POJ Problem 2240: Arbitrage有点相似,也是使用Floyd算法,稍作修改即可。

如上图所示,假设要从A到B,在用Floyd算法时,判断要不要借助C点,如果不借助,则load_ton[A][B]=80;如果借助C点,则路径变为A->C->B,A->C最多能载100吨,C->B最多能载90吨,所以总的来说,A->C->B最多能载min{100,90}=90吨;而90>80,所以借助C点后的载重大于不借助C点的载重,所以修改load_ton[A][B]=90。
知道这一点,我们可以很快的写出代码:

#include<iostream>
#include<map>
#include<string>
using namespace std;
const int MAX_N=202;
int load_ton[MAX_N][MAX_N];
//初始化数据
void init_load(int n)
{
     for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
               load_ton[i][j]=0;
}
//改造Floyd算法
void Floyd(int n)
{
     for(int k=0;k<n;k++)
     {
          for(int i=0;i<n;i++)
          {
               for(int j=0;j<n;j++)
               {
                    int min_ton=load_ton[i][k]<load_ton[k][j]?load_ton[i][k]:load_ton[k][j];//这条路上的最小值即为能通过的最大值
                    if(load_ton[i][j]<min_ton)
                    {
                         load_ton[i][j]=min_ton;//对称矩阵
                         load_ton[j][i]=min_ton;//对称矩阵
                    }
               }
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     int n,r;
     int case_num=1;
     while(cin>>n>>r&&n&&r)
     {
          init_load(n);
          map<string,int> city_index;//保存城市和下标的对应关系
          string city1,city2;
          int w;
          int i=0;
          while(r--)
          {
               cin>>city1>>city2>>w;
               if(city_index.find(city1)==city_index.end())
                    city_index[city1]=i++;
               if(city_index.find(city2)==city_index.end())
                    city_index[city2]=i++;
               //load_ton[i-2][i-1]=w;//错,因为有可能cityi在之前已经加入了,这个时候i-1,i-2就不是cityi的下标了
               //load_ton[i-1][i-2]=w;
               load_ton[city_index[city1]][city_index[city2]]=w;//还是要从map里找对应下标
               load_ton[city_index[city2]][city_index[city1]]=w;//因为路是两边通的,所以a[i][j]和a[j][i]相等
          }
          cin>>city1>>city2;
          Floyd(n);
          cout<<"Scenario #"<<case_num++<<endl;//
          cout<<load_ton[city_index[city1]][city_index[city2]]<<" tons"<<endl<<endl;
     }
     return 0;
}

本代码提交AC,用时79MS,内存316K。
在写代码的时候有几个小细节需要注意。在输入数据的时候,用MAP来保存城市和下标的关系,方便后面Floyd算法的操作;因为道路是双向通行的,所以保存数据时要保存成对称矩阵。