分类:ACM_POJ

REPORT POJ1258-Agri-Net

REPORT POJ1258-Agri-Net

Agri-Net
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 53017 Accepted: 22052
Description

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.

//=======================================================
赤裸裸的最小生成树,在于使用PRIM还是KRUSKAL
向PRIM势力低头(滑稽
注意输入输出
//=======================================================

#include <iostream>
#include <string.h>
#define inf 0x3f3f3f3f
#define N 110
using namespace std;
int G[N][N], n;

int prim()
{
	int dist[N], visited[N];
	int pos, min = inf, result = 0;
	memset(visited, 0, sizeof(visited));
	visited[1] = 1; pos = 1;
	for (int i = 1; i <= n; i++)
		if (i != pos) dist[i] = G[pos][i];
	for (int i = 1; i<n; i++)
	{
		min = inf;
		for (int j = 1; j <= n; j++)
			if (visited[j] == 0 && min > dist[j])
				min = dist[j], pos = j;
		result += min;
		visited[pos] = 1;
		for (int j = 1; j <= n; j++)
			if (visited[j] == 0 && dist[j]>G[pos][j])
				dist[j] = G[pos][j];
	}
	return result;
}

int main()
{
	while (cin >> n)
	{
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				cin >> G[i][j];
		cout << prim() << endl;
	}
	return 0;
}
REPORT POJ2485-Highways

REPORT POJ2485-Highways

Highways
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 28843 Accepted: 13165
Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
//===================================================
PRIM求最小生成树,求的时候记录当前最小生成树里的最大边
还有记得用scanf……用cin就TLE
//===================================================

#include <iostream>
#include <cstdio>
#include <string.h>
#define inf 0x3f3f3f3f
#define MAXN 505
using namespace std;

int dist[MAXN][MAXN];
int n;  

int prim()
{
	int s = 1, m = 1, min, point, ANS = 0, currentShortest[MAXN];
	bool u[501] = { false };
	u[s] = true;
	
	memset(currentShortest, inf, sizeof(currentShortest));

	while (true)
	{
		if (m == n)
			break;

		min = inf;
		for (int i = 2; i <= n; i++)
		{
			if (!u[i] && currentShortest[i] > dist[s][i]) currentShortest[i] = dist[s][i];
			if (!u[i] && min>currentShortest[i])
			{
				min = currentShortest[i];
				point = i;

			}
		}

		if (ANS < min) ANS = min;
		s = point;
		u[s] = true;
		m++;
	}
	return ANS;
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				scanf("%d",&dist[i][j]);
		cout << prim() << endl;
	}
	return 0;
}
REPORT POJ1789-Truck History

REPORT POJ1789-Truck History

Truck History
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 25362 Accepted: 9902
Description

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of company’s history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on.

Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan — i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as
1/Σ(to,td)d(to,td)

where the sum goes over all pairs of types in the derivation plan such that to is the original type and td the type derived from it and d(to,td) is the distance of the types.
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan.

//=========================================================
如果没有题解我应该做不出……完全没看懂……有毒……先感谢http://blog.csdn.net/lyy289065406/article/details/6645974
主要是PRIM算法,由距离构图然后用这个图构筑最小生成树。
所以题目的关键是构图
//=========================================================

#include <iostream>
#include <string>
#define INF 0x3f3f3f3f
#define MAX 2005
using namespace std;

int N;
string t[MAX];
int d[MAX][MAX];

int calc(int a, int b)
{
	int d = 0;
	for (int i = 0; i < 7; i++)
		if (t[a][i] != t[b][i]) d++;
	return d;
}

int prim(void)
{
	int startPoint = 1, visitedCount = 1, weight = 0, shortest, flag, shortestDist[MAX];
	bool includePoint[MAX];

	memset(shortestDist, INF, sizeof(shortestDist));
	memset(includePoint, false, sizeof(includePoint));
	includePoint[startPoint] = true;

	while (true)
	{
		if (visitedCount == N) break;
		shortest = INF;
		for (int j = 2; j <= N; j++)
		{
			if (!includePoint[j] && shortestDist[j] > d[startPoint][j])
				shortestDist[j] = d[startPoint][j];
			if (!includePoint[j] && shortest > shortestDist[j])
			{
				shortest = shortestDist[j];
				flag = j;
			}
		}
		startPoint = flag;
		includePoint[startPoint] = true;
		weight += shortest;
		visitedCount++;
	}
	return weight;
}

int main()
{
	while (cin >> N && N != 0)
	{
		for (int i = 1; i <= N; i++)
			cin >> t[i];
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
			{
				d[i][j] = calc(i, j);
			}
		int ans = prim();
		cout << "The highest possible quality is 1/" << ans << '.' << endl;
	}
}
REPORT POJ2240-Arbitrage

REPORT POJ2240-Arbitrage

Arbitrage
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 21264 Accepted: 9061
Description

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

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
//========================================
盲人ACM,BEST ACM……醉了
花了半个小时找数据compare看了半天没错……结果最后发现我自己输出把No和Yes输出成了NO和YES
瞎了……
我用的BellmanFord算法做的,就是判断是否存在一个正权环,据说能用Floyd做,但是我还没研究
//========================================

#include <iostream>
#include <string>
#include <map>
#include <string.h>
#define MAXN 100
using namespace std;

typedef struct Edge
{
	int u, v;
	double cost;
}Edge;
double dis[1005];
int edges, countNode;
Edge edge[5200];
map<string, int> table;

bool Bellman_Ford()
{
	for (int i = 0; i < countNode - 1; i++)
	{
		for (int j = 0; j < edges; j++)
		{
			if (dis[edge[j].v] < dis[edge[j].u] * edge[j].cost)
			{
				dis[edge[j].v] = dis[edge[j].u] * edge[j].cost;
			}
		}
	}
	for (int i = 0; i < edges; i++)
	{
		if (dis[edge[i].v] < dis[edge[i].u] * edge[i].cost)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	int F = 0;
	while (cin >> countNode&&countNode != 0)
	{
		F++;
		memset(dis, 0x3F, sizeof(dis));
		for (int i = 0; i < countNode; i++)
		{
			string name;
			cin >> name;
			table.insert(pair<string, int>(name, i));
		}
		cin >> edges;
		for (int i = 0; i < edges; i++)
		{
			string name1, name2;
			double rate;
			cin >> name1 >> rate >> name2;
			int u = table[name1];
			int v = table[name2];
			edge[i].u = u;
			edge[i].v = v;
			edge[i].cost = rate;
		}
		cout << "Case " << F << ": ";
		if (!Bellman_Ford())
			cout << "No" << endl;
		else
			cout << "Yes" << endl;
	}
	return 0;
}
REPORT POJ1125-Stockbroker Grapevine

REPORT POJ1125-Stockbroker Grapevine

Stockbroker Grapevine
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 34407 Accepted: 19049
Description

Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way.

Unfortunately for you, stockbrokers only trust information coming from their “Trusted sources” This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.

//===========================================
躶FLOYD,算出FLOYD矩阵,然后求出每个点开始的所需的扩散时间。也就是每条路径完成时间
//===========================================

#include <iostream>
#include <string.h>
#define MAXN 105
using namespace std;
int G[MAXN][MAXN], n;

int floyd()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
			{
				if (j != k && G[j][k]>G[j][i] + G[i][k])
					G[j][k] = G[j][i] + G[i][k];
			}
	int startPoint, wayCost, min = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++)
	{
		wayCost = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i != j && G[i][j]>wayCost) wayCost = G[i][j];
		}
		if (wayCost<min)
		{
			min = wayCost;
			startPoint = i;
		}
	}
	if (min >= 0x3f3f3f3f) 
		cout << "disjoint" << endl;
	else
		cout << startPoint << " " << min << endl;
	return 0;
}

int main()
{
	while (cin >> n && n != 0)
	{
		memset(G, 0x3f3f3f3f, sizeof(G));
		for (int i = 1; i <= n; i++)
		{
			int m, target, cost;
			cin >> m;
			for (int j = 1; j <= m; j++)
			{
				cin >> target >> cost;
				G[i][target] = cost;
			}
		}
		floyd();
	}

	return 0;
}
REPORT POJ2253-Frogger

REPORT POJ2253-Frogger

Frogger
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 38333 Accepted: 12345
Description

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.

//=====================================================
大意就是在所有路径中找一个路径,这个路径中最长的边在所有的路径中最长边中最小。
Floyd搞吧,只是要把Floyd定义的最短路径改为这条路径中最长边的大小。
//=====================================================

#include <iostream>
#include <cmath>
#include <string.h>
#include <iomanip> 
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MAXN 1005
using namespace std;
double x[MAXN], y[MAXN];
double graph[MAXN][MAXN];

int main()
{
	int n, cases = 0;
	while (cin >> n&&n != 0)
	{
		cases++;
		for (int i = 0; i < n; i++)
		{
			cin >> x[i] >> y[i];
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				double deltaX = x[i] - x[j];
				double deltaY = y[i] - y[j];
				graph[i][j] = sqrt(deltaX*deltaX + deltaY*deltaY);
			}
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				for (int k = 0; k < n; k++)
				{
					graph[j][k] = MIN(graph[j][k], MAX(graph[j][i], graph[i][k]));
				}
		cout << "Scenario #" << cases << endl;
		cout << fixed << setprecision(3) << "Frog Distance = " << graph[0][1] << endl;
		cout << endl;
	}
	return 0;
}
REPORT POJ1062-昂贵的聘礼

REPORT POJ1062-昂贵的聘礼

昂贵的聘礼
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 45796Accepted: 13583
Description

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:”嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。如果你能够弄来他的水晶球,那么只要5000金币就行了。”探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格。探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接用金币换,或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西,因为不会得到更低的价格。探险家现在很需要你的帮忙,让他用最少的金币娶到自己的心上人。另外他要告诉你的是,在这个部落里,等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触,包括交易。他是一个外来人,所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见,我们把所有的物品从1开始进行编号,酋长的允诺也看作一个物品,并且编号总是1。每个物品都有对应的价格P,主人的地位等级L,以及一系列的替代品Ti和该替代品所对应的”优惠”Vi。如果两人地位等级差距超过了M,就不能”间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

//================================================
中文题!中文题啊!!!
将物品作为点,加钱的价格作为边的权值,同时设一条边连向每个物品,这条边的权值是物品单买的价格
然后枚举起始点求最短路径,注意等级差距就好。
//================================================

#include <iostream>
#include <string.h>
using namespace std;
#define MAXN 105
#define MAXNUM 0x3F3F3F3F
int N, M, graph[MAXN][MAXN] = { 0 }, tier[MAXN] = { 0 }, dist[MAXN] = { MAXNUM };
bool visited[MAXN] = { false };

int Dijkstra()
{
	int tempNode, tempShortest;
	for (int i = 1; i <= N; i++)
		dist[i] = graph[0][i];

	for (int i = 1; i <= N; i++)
	{
		tempNode = 0;
		tempShortest = MAXNUM;
		for (int j = 1; j <= N; j++)
			if (!visited[j] && tempShortest > dist[j])
			{
				tempShortest = dist[j];
				tempNode = j;
			}
		if (tempNode == 0) break;
		visited[tempNode] = true;
		for (int j = 1; j <= N; j++)
		{
			if (!visited[j] && graph[tempNode][j] > 0 && dist[j] > dist[tempNode] + graph[tempNode][j])
			{
				dist[j] = dist[tempNode] + graph[tempNode][j];
			}
		}
	}

	return dist[1];
}

int main()
{
	int currentPrice, currentTier, minPrice = MAXNUM;
	cin >> M >> N;
	for (int i = 1; i <= N; i++)
	{
		int X;
		cin >> graph[0][i] >> tier[i] >> X;
		for (int j = 0; j < X; j++)
		{
			int T, V;
			cin >> T >> V;
			graph[T][i] = V;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		currentTier = tier[i];
		for (int j = 1; j <= N; j++)
		{
			if (tier[j] > currentTier || currentTier > tier[j] + M)
				visited[j] = true;
			else visited[j] = false;
		}
		currentPrice = Dijkstra();
		if (currentPrice < minPrice)
			minPrice = currentPrice;
	}

	cout << minPrice << endl;

	return 0;
}
REPORT POJ3259-Wormholes

REPORT POJ3259-Wormholes

Wormholes
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 44770 Accepted: 16486
Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself 🙂 .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output

Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output

NO
YES
Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.
Source

USACO 2006 December Gold

//===========================================================
一个标准的Bellman_Ford,在图中找到一个负权环。
题目大致是给你一堆地点和一堆虫洞,虫洞可以用来回到过去。比如a到b和b到a你需要花费cost的时间,但是你走a到b虫洞花费的时间是-cost。注意虫洞是单向的。问题就在于能不能回到过去。
所以我又想起昨天Bellman_Ford忘记初始化的鬼畜错误。
我选择全局变量,嗯。(我好菜啊
//===========================================================

#include <iostream>
#include <string.h>
#define MAXN 100
using namespace std;

typedef struct Edge
{
	int u, v;
	int cost;
}Edge;
int dis[1005], edges, countNode, M, W;
Edge edge[5200];

bool Bellman_Ford()
{
	for (int i = 0; i < countNode - 1; i++)
	{
		for (int j = 0; j < edges; j++)
		{
			if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost)
			{
				dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
			}
		}
	}
	for (int i = 0; i < edges; i++)
	{
		if (dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	int F;
	cin >> F;
	while (F--)
	{
		cin >> countNode >> M >> W;
		memset(dis, 0x3F, sizeof(dis));
		edges = 0;
		for (int i = 0; i < M; i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			edge[edges].u = u;
			edge[edges].v = v;
			edge[edges].cost = w;
			edges++;
			edge[edges].v = u;
			edge[edges].u = v;
			edge[edges].cost = w;
			edges++;
		}
		for (int i = 0; i<W; i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			edge[edges].u = u;
			edge[edges].v = v;
			edge[edges].cost = -w;
			edges++;
		}
		if (!Bellman_Ford())
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}

	return 0;
}
REPORT POJ1860-Currency Exchange

REPORT POJ1860-Currency Exchange

Currency Exchange
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 21122 Accepted: 7572
Description

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.
For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 – 0.39) * 29.75 = 2963.3975RUR.
You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B – numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA – exchange rates and commissions when exchanging A to B and B to A respectively.
Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.

//==============================================================
感觉自己像智障一样……因为初始化变量的问题WA一晚上……
//==============================================================
题意就是给你几种货币让你换看怎么越换越多233空手套白狼
总体而言这个是个反向的BELLMAN_FORD,就是求一个图中是否存在一个正权最大环(正权回路
例如A货币和B货币,A到B的汇率为Rab,手续费为Cab,那么A到B的权为(V-Cab)*Rab,以这个作为BF算法中的松弛条件。
注意BF时初始化。
其实SPFA应该也是可以的,本身就是BF的优化版嘛。
//==============================================================

#include <iostream>
#include <string.h>
#define MAXN 205
using namespace std;

int countNode, countEdge, pointStart, edges;
double moneyStart;

typedef struct Edge
{
	int u, v;
	double rate, cost;
}Edge;
double dis[MAXN];
Edge edge[MAXN];

bool Bellman_Ford()
{
	bool flag;
	memset(dis, 0, sizeof(dis));
	dis[pointStart] = moneyStart;
	for (int i = 1; i <= countNode - 1; i++)
	{
		for (int j = 0; j < edges; j++)
		{
			if (dis[edge[j].v] < (dis[edge[j].u] - edge[j].cost)*edge[j].rate)
			{
				dis[edge[j].v] = (dis[edge[j].u] - edge[j].cost)*edge[j].rate;
			}
		}
	}
	for (int i = 0; i < edges; i++)
	{
		if (dis[edge[i].v] < (dis[edge[i].u] - edge[i].cost)*edge[i].rate)
		{
			return true;
		}
	}
	return false;
}

int main()
{
	int a, b;
	double rab, rba, cab, cba;
	while (cin >> countNode >> countEdge >> pointStart >> moneyStart)
	{
		edges = 0;
		for (int i = 0; i < countEdge; i++)
		{
			cin >> a >> b >> rab >> cab >> rba >> cba;
			edge[edges].u = a;
			edge[edges].v = b;
			edge[edges].rate = rab;
			edge[edges].cost = cab;
			edges++;
			edge[edges].u = b;
			edge[edges].v = a;
			edge[edges].rate = rba;
			edge[edges].cost = cba;
			edges++;
		}
		if (!Bellman_Ford())
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
	return 0;
}
REPORT POJ2993/2996

REPORT POJ2993/2996

POJ 2993:http://poj.org/problem?id=2996
POJ 2996:http://poj.org/problem?id=2996

//=====================================
两道单纯的字符/字符串处理题,就是很麻烦
自己代码写的太丑就转载别人的吧= =
//=====================================

//POJ 2993
#include<iostream>
#include<string>
using namespace std;

class whit
{
public:
	int row;
	char col;
	char pie;
}ww[16];

class blac
{
public:
	int row;
	char col;
	char pie;
}bb[16];

int main(void)
{
	char white[63],black[63];
	gets(white);
	gets(black);

	int x,y,z,r;

	int count_w=0;
	int count_b=0;
	const int length_w=strlen(white);
	const int length_b=strlen(black);

	for(x=7,y=0;x<length_w;)
		if(white[x]>='B' && white[x]<='R')
		{
			ww[y].pie=white[x];
			ww[y].col=white[x+1];
			ww[y].row=white[x+2]-'0';
			y++;
			x+=4;
			count_w++;
		}
		else if(white[x]>='a' && white[x]<='h')
		{
			ww[y].pie='P';
			ww[y].col=white[x];
			ww[y].row=white[x+1]-'0';
			y++;
			x+=3;
		    count_w++;
		}
		else
			break;

		for(x=7,y=0;x<length_b;)
		if(black[x]>='B' && black[x]<='R')
		{
			bb[y].pie=black[x]+32;
			bb[y].col=black[x+1];
			bb[y].row=black[x+2]-'0';
			y++;
			x+=4;
			count_b++;
		}
		else if(black[x]>='a' && black[x]<='h')
		{
			bb[y].pie='p';
			bb[y].col=black[x];
			bb[y].row=black[x+1]-'0';
			y++;
			x+=3;
		    count_b++;
		}
		else
			break;

		char chess[9]['i'];

		memset(chess,':',sizeof(chess));

		for(x=1;x<=7;x+=2)
			for(y='a';y<='g';y+=2)
				chess[x][y]='.';
		for(x=2;x<=8;x+=2)
			for(y='b';y<='h';y+=2)
				chess[x][y]='.';

		for(x=0;x<count_w;x++)
			chess[9-ww[x].row][ww[x].col]=ww[x].pie;

		for(x=0;x<count_b;x++)
			chess[9-bb[x].row][bb[x].col]=bb[x].pie;

		cout<<"+---+---+---+---+---+---+---+---+"<<endl;
		
		for(x=1,r=2;x<=7;x+=2,r+=2)
		{
			cout<<'|';
			for(y='a',z='b';y<='g';y+=2,z+=2)
				cout<<"."<<chess[x][y]<<".|:"<<chess[x][z]<<":|";
			cout<<endl;
			cout<<"+---+---+---+---+---+---+---+---+"<<endl;
			cout<<'|';
			for(y='a',z='b';y<='g';y+=2,z+=2)
				cout<<":"<<chess[r][y]<<":|."<<chess[r][z]<<".|";
			cout<<endl;
			cout<<"+---+---+---+---+---+---+---+---+"<<endl;
		}

	return 0;
}
POJ2996
#include<iostream>  
using namespace std;  
  
class white_piece  
{  
public:  
    int row;  
    char col;  
    bool flag;
}K,Q,R[3],B[3],N[3];  
  
bool pawn[9]['i']={false};
int PR=0,PB=0,PN=0;
  
class black_piece  
{  
public:  
    int row;  
    char col;  
    bool flag;  
}k,q,r[2],b[2],n[2],p[8];  
  
int pr=0,pb=0,pn=0,pp=0;    
  
char chess[9]['i'];
int x,z;  
char y;  
int w_count=0;
int b_count=0;
  
void judge()  
{  
    if(chess[x][y]=='.' || chess[x][y]==':')  
        return;  
    else if(chess[x][y]=='k')
    {  
        k.row=9-x;  
        k.col=y;  
        k.flag=true;  
        b_count++;  
        return;  
    }  
    else if(chess[x][y]=='q')  
    {  
        q.row=9-x;  
        q.col=y;  
        q.flag=true;  
        b_count++;  
        return;  
    }  
    else if(chess[x][y]=='r')  
    {  
        r[pr].row=9-x;  
        r[pr++].col=y;  
        b_count++;  
        return;  
    }  
    else if(chess[x][y]=='b')  
    {  
        b[pb].row=9-x;  
        b[pb++].col=y;  
        b_count++;  
        return;  
    }  
    else if(chess[x][y]=='n')  
    {  
        n[pn].row=9-x;  
        n[pn++].col=y;  
        b_count++;  
        return;  
    }  
    else if(chess[x][y]=='p')  
    {  
        p[pp].row=9-x;  
        p[pp++].col=y;  
        b_count++;  
        return;  
    }  
    else if(chess[x][y]=='K')
    {  
        K.row=9-x;  
        K.col=y;  
        K.flag=true;  
        w_count++;  
        return;  
    }  
    else if(chess[x][y]=='Q')  
    {  
        Q.row=9-x;  
        Q.col=y;  
        Q.flag=true;  
        w_count++;  
        return;  
    }  
    else if(chess[x][y]=='R')  
    {  
        R[PR].row=9-x;  
        R[PR++].col=y;  
        w_count++;  
        return;  
    }  
    else if(chess[x][y]=='B')  
    {  
        B[PB].row=9-x;  
        B[PB++].col=y;  
        w_count++;  
        return;  
    }  
    else if(chess[x][y]=='N')  
    {  
        N[PN].row=9-x;  
        N[PN++].col=y;  
        w_count++;  
        return;  
    }  
    else if(chess[x][y]=='P')  
    {  
        pawn[9-x][y]=true;  
        w_count++;  
        return;  
    }  
}  
  
void Print(void)  
{  
    cout<<"White: ";  
    if(K.flag)  
    {  
        cout<<'K'<<K.col<<K.row;  
        if(--w_count>0)  
            cout<<',';  
    }  
    if(Q.flag)  
    {  
        cout<<'Q'<<Q.col<<Q.row;  
        if(--w_count>0)  
            cout<<',';  
    }  
  
    if(PR==2)  
        if(R[1].row<R[0].row)  
        {  
            R[2]=R[0];  
            R[0]=R[1];  
            R[1]=R[2];  
        }  
    for(x=0;x<PR;x++)  
    {  
        cout<<'R'<<R[x].col<<R[x].row;  
        if(--w_count>0)  
            cout<<',';  
    }  
  
    if(PB==2)  
        if(B[1].row<B[0].row)  
        {  
            B[2]=B[0];  
            B[0]=B[1];  
            B[1]=B[2];  
        }  
    for(x=0;x<PB;x++)  
    {  
        cout<<"B"<<B[x].col<<B[x].row;  
        if(--w_count>0)  
            cout<<',';  
    }  
  
    if(PN==2)  
        if(N[1].row<N[0].row)  
        {  
            N[2]=N[0];  
            N[0]=N[1];  
            N[1]=N[2];  
        }  
    for(x=0;x<PN;x++)  
    {  
        cout<<'N'<<N[x].col<<N[x].row;  
        if(--w_count>0)  
            cout<<',';  
    }  
  
    for(x=1;x<=8;x++)  
        for(y='a';y<='h';y++)  
            if(pawn[x][y])  
            {  
                cout<<y<<x;  
                if(--w_count>0)  
                    cout<<',';  
            }  
      
    cout<<endl;  
  
    cout<<"Black: ";  
    if(k.flag)  
    {  
        cout<<'K'<<k.col<<k.row;  
        if(--b_count>0)  
            cout<<',';  
    }  
    if(q.flag)  
    {  
        cout<<'Q'<<q.col<<q.row;  
        if(--b_count>0)  
            cout<<',';  
    }  
    for(x=0;x<pr;x++)  
    {  
        cout<<'R'<<r[x].col<<r[x].row;  
        if(--b_count>0)  
            cout<<',';  
    }  
    for(x=0;x<pb;x++)  
    {  
        cout<<"B"<<b[x].col<<b[x].row;  
        if(--b_count>0)  
            cout<<',';  
    }  
    for(x=0;x<pn;x++)  
    {  
        cout<<'N'<<n[x].col<<n[x].row;  
        if(--b_count>0)  
            cout<<',';  
    }  
    for(x=0;x<pp;x++)  
    {  
        cout<<p[x].col<<p[x].row;  
        if(--b_count>0)  
            cout<<',';  
    }  
  
    cout<<endl;  
  
    return;  
}  
  
int main()  
{  
    char temp;  

    for(z=0;z<33;z++)  
        cin>>temp;  
  
    for(x=1;x<=8;x++)  
    {  
        cin>>temp;  
        for(y='a';y<='h';y++)  
        {  
            cin>>temp>>chess[x][y]>>temp>>temp;  
            judge();  
        }  
        for(z=0;z<33;z++)  
            cin>>temp;  
    }  

    Print();  
    return 0;  
}