poj 基础图论题小结

现在的位置: 首页 > 综合 > 正文

poj 基础图论题小结

2018年04月05日 ⁄ 综合 ⁄ 共 11445字 ⁄ 字号小中大 ⁄ 评论关闭

poj 1860

Currency Exchange

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 3318		Accepted: 1014

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
R_AB
, C_AB
, R_BA
and C_BA
- 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.

Input

The
first line of the input contains four numbers: N - the number of
currencies, M - the number of exchange points, S - the number of
currency Nick has and V - the quantity of currency units he has. The
following M lines contain 6 numbers each - the description of the
corresponding exchange point - in specified above order. Numbers are
separated by one or more spaces. 1<=S<=N<=100,
1<=M<=100, V is real number, 0<=V<=10³
.

For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10^-2
<=rate<=10²
, 0<=commission<=10²
.

Let us call some sequence of the exchange operations simple if no
exchange point is used more than once in this sequence. You may assume
that ratio of the numeric values of the sums at the end and at the
beginning of any simple sequence of the exchange operations will be
less than 10⁴
.

Output

If Nick can increase his wealth, output YES, in other case output NO to the output file.

Sample Input

3 2 1 20.0

1 2 1.00 1.00 1.00 1.00

2 3 1.10 1.00 1.10 1.00

Sample Output

YES


有一些货币兑换点，兑换有汇率和手续费，要求最后能否增值原有的钱，并且钱种类和增值前是一样的。


可以建立图模型，A－B 有一条边，存储rab 和 cab的值，然后 bellman 算法求能否增值。

代码如下：
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
using namespace std;
const int MaxN = 110;
const double eps = 1e-8;
int N,M,S,cnt;
double V;

typedef struct edge{
	int u,v;
	double r,c;
}edge;
edge E[1001];

int bellman(){
	double d[MaxN];
	memset(d,0,sizeof(d));
	d[S] = V;
	while(d[S] <= V + eps){
		int f = 0;
		for(int i = 0 ;i < cnt; ++i){
			if(d[E[i].v] + eps < (d[E[i].u] - E[i].c) * E[i].r){
				d[E[i].v] = (d[E[i].u] - E[i].c) * E[i].r;
				f = 1;
			}
		}
		if(!f) return d[S] > V + eps;
	}
	return 1;
}
int main(){
	int a,b;
	double rab,cab,rba,cba;
	scanf("%d%d%d%lf",&N,&M,&S,&V);
	cnt = 0;
	for(int i = 0 ;i < M; ++i){
		scanf("%d%d",&a,&b);
		scanf("%lf%lf%lf%lf",&rab,&cab,&rba,&cba);
		E[cnt].u = a; E[cnt].v = b;
		E[cnt].r = rab; E[cnt].c = cab;
		++cnt;
		E[cnt].u = b; E[cnt].v = a;
		E[cnt].r = rba; E[cnt].c = cba;
		++cnt;
	}
	if(bellman()) printf("YES/n");
	else printf("NO/n");
	return 0;
}


poj 3259

Wormholes

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 4233		Accepted: 1463

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.

和1860几乎一样，用bellman 算法求是否有负环，代码如下：

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
using namespace std;
const int MaxM = 7000;
const int MaxN = 1010;
typedef struct edge{
	int u,v;
	int w;
}edge;
edge e[MaxM];
int F,N,M,W,cnt;

void input(){
	int a,b,w;
	cnt = 0;
	scanf("%d%d%d",&N,&M,&W);
	for(int i = 0 ;i < M; ++i){
		scanf("%d%d%d",&a,&b,&w);
		e[cnt].u = a;
		e[cnt].v = b;
		e[cnt].w = w;
		++cnt;
		e[cnt].u = b;
		e[cnt].v = a;
		e[cnt].w = w;
		++cnt;
	}
	for(int i = 0 ;i < W; ++i){
		scanf("%d%d%d",&a,&b,&w);
		e[cnt].u = a;
		e[cnt].v = b;
		e[cnt].w = -w;
		++cnt;
	}
}
bool bellman(){
	int d[MaxN];
	memset(d,0,sizeof(d));
	d[1] = 0;
	for(int i = 1 ;i < N; ++i){
		for(int j = 0 ;j < cnt; ++j){
			if(d[e[j].v] > d[e[j].u] + e[j].w)
				d[e[j].v] = d[e[j].u] + e[j].w;
		}
	}
	for(int i = 0 ;i < cnt; ++i)
		if(d[e[i].v] > d[e[i].u] + e[i].w)
			return false;
	return true;
}
int main(){
	int a,b,w;
	scanf("%d",&F);
	while(F--){
		input();
		if(bellman()) printf("NO/n");
		else printf("YES/n");
	}
	return 0;
}


poj 2253

Frogger

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6059		Accepted: 2084

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.

Input

The
input will contain one or more test cases. The first line of each test
case will contain the number of stones n (2<=n<=200). The next n
lines each contain two integers xi,yi (0 <= xi,yi <= 1000)
representing the coordinates of stone #i. Stone #1 is Freddy's stone,
stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's
a blank line following each test case. Input is terminated by a value
of zero (0) for n.

Output

For
each test case, print a line saying "Scenario #x" and a line saying
"Frog Distance = y" where x is replaced by the test case number (they
are numbered from 1) and y is replaced by the appropriate real number,
printed to three decimals. Put a blank line after each test case, even
after the last one.

Sample Input

2
0 0
3 4
3
17 4
19 4
18 5
0

Sample Output

Scenario #1
Frog Distance = 5.000
Scenario #2
Frog Distance = 1.414

Source

可以修改Floyid算法求 D[i,j] = min(D[i,k],D[k,j]) 1 <= k <= j

代码如下：

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#define sqr(x) ((x)*(x))
using namespace std;

const int MaxN = 500;
const double Inf = 1e30;
typedef struct point{
	double x,y;
}point;
point P[MaxN];
double map[MaxN][MaxN];
int N; 

void input(){
	for(int i = 0 ;i < N; ++i)
		scanf("%lf%lf",&P[i].x,&P[i].y);
}
double dis(const point& a,const point& b){
	return sqrt(sqr(a.x -b.x) + sqr(a.y - b.y));
}
void calc(){
	for(int i = 0 ;i < N; ++i){
		for(int j = 0; j < N; ++j)
			map[i][j] = dis(P[i],P[j]);
	}
}
void work(){
	for(int k = 0 ;k < N; ++k){
		for(int i = 0 ;i < N; ++i){
			for(int j = 0 ;j < N; ++j){
				if(max(map[i][k],map[k][j]) < map[i][j])
					map[i][j] = max(map[i][k],map[k][j]);
			}
		}
	}
}
int main(){
	int t = 1;
	while(scanf("%d",&N) && N){
		input();
		calc();
		work();
		printf("Scenario #%d/n",t);
		printf("Frog Distance = %.3f/n",map[0][1]);
		printf("/n");
		++t;
	}	
	return 0;
}


poj 3026

Borg Maze

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1807		Accepted: 572

Description

The
Borg is an immensely powerful race of enhanced humanoids from the delta
quadrant of the galaxy. The Borg collective is the term used to
describe the group consciousness of the Borg civilization. Each Borg
individual is linked to the collective by a sophisticated subspace
network that insures each member is given constant supervision and
guidance.

Your task is to help the Borg (yes, really) by developing a program
which helps the Borg to estimate the minimal cost of scanning a maze
for the assimilation of aliens hiding in the maze, by moving in north,
west, east, and south steps. The tricky thing is that the beginning of
the search is conducted by a large group of over 100 individuals.
Whenever an alien is assimilated, or at the beginning of the search,
the group may split in two or more groups (but their consciousness is
still collective.). The cost of searching a maze is definied as the
total distance covered by all the groups involved in the search
together. That is, if the original group walks five steps, then splits
into two groups each walking three steps, the total distance is
11=5+3+3.

Input

On
the first line of input there is one integer, N <= 50, giving the
number of test cases in the input. Each test case starts with a line
containg two integers x, y such that 1 <= x,y <= 50. After this,
y lines follow, each which x characters. For each character, a space ``
'' stands for an open space, a hash mark ``#'' stands for an
obstructing wall, the capital letter ``A'' stand for an alien, and the
capital letter ``S'' stands for the start of the search. The perimeter
of the maze is always closed, i.e., there is no way to get out from the
coordinate of the ``S''. At most 100 aliens are present in the maze,
and everyone is reachable.

Output

For every test case, output one line containing the minimal cost of a succesful search of the maze leaving no aliens alive.

Sample Input

2

6 5

##### 

#A#A##

# # A#

#S  ##

##### 

7 7

#####  

#AAA###

#    A#

# S ###

#     #

#AAA###

#####

Sample Output

8
11

现对每个 ‘A’ 和 ‘S’ 的点 BFS 求得他与其他‘A’  ‘S’点的距离，然后从S 求 Minmum Spanning Tree 把所有

代价加起来，就是答案

代码如下：
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "algorithm"
#include "cstring"
using namespace std;

const int MaxN = 110;
const int INF = 0x7fffffff;
char map[MaxN][MaxN];
int g[MaxN][MaxN];
int graph[110][110];
int X,Y,num;
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
typedef struct point{
	int x,y;
	void init(int _x,int _y){
		x = _x;
		y = _y;
	}
}point;
point q[MaxN * MaxN];

int input(){
	int cnt = 2;
	char tmp[1000];
	scanf("%d%d",&X,&Y);
	gets(tmp);
	for(int i = 0 ;i < Y; ++i){
		gets(tmp);
		strcpy(map[i],tmp);
		for(int j = 0 ;j < X; ++j){
			if(tmp[j] == ' ') g[i][j] = 0;
			else if(tmp[j] == '#') g[i][j] = -1;
			else if(tmp[j] == 'S') g[i][j] = 1;
			else g[i][j] = cnt++;
		}
	}
	return cnt-1;
}
void bfs(int x,int y){
	int s,e;
	int dis[MaxN][MaxN];
	bool vis[MaxN][MaxN];
	for(int i = 0 ;i < MaxN; ++i)
		for(int j = 0 ;j < MaxN; ++j)
			vis[i][j] = false;
	vis[x][y] = true;
	dis[x][y] = 0;
	point tmp;
	tmp.init(x,y);
	s = e = 0;
	q[e++] = tmp;
	int a,b,na,nb;
	while(s != e){
		tmp = q[s++];
		a = tmp.x;
		b = tmp.y;
		//printf("a = %d b = %d/n",a,b);
		//getchar();
		for(int i = 0 ;i < 4; ++i){
			na = a + dir[i][0];
			nb = b + dir[i][1];
			if(na >= 0 && na < Y && 
			   nb >= 0 && nb < X &&
			   g[na][nb] >= 0 && !vis[na][nb]){
				vis[na][nb] = true;
				dis[na][nb] = dis[a][b] + 1;
				tmp.init(na,nb);
				q[e++] = tmp;
				if(g[na][nb] > 0){
					graph[g[x][y]][g[na][nb]] = dis[na][nb];
					graph[g[na][nb]][g[x][y]] = dis[na][nb];
				}
			}
		}
	}
}
int prime(){
	int ret = 0;
	int dis[MaxN];
	bool vis[MaxN];
	memset(vis,false,sizeof(vis));
	for(int i = 0 ;i < MaxN; ++i)
		dis[i] = INF;
	dis[1] = 0;
	for(int i = 1;i <= num; ++i){
		int tmin = INF;
		int pos;
		for(int j = 1 ;j <= num; ++j){
			if(!vis[j] && dis[j] < tmin){
				tmin = dis[j];
				pos = j;
			}
		}
		vis[pos] = true;
		ret += dis[pos];
		for(int j = 1; j <= num; ++j){
			if(!vis[j] && graph[pos][j] != INF &&
					graph[pos][j] < dis[j])
				dis[j] = graph[pos][j];
		}
	}
	return ret;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		for(int i =0 ;i < MaxN; ++i)
			for(int j = 0 ;j < MaxN; ++j)
				g[i][j] = 0;
		num = input();
		for(int i = 0 ;i <= num; ++i)
			for(int j = 0 ;j <= num; ++j)
				graph[i][j] = INF;
		for(int i = 0 ;i < Y; ++i)
			for(int j = 0 ;j < X; ++j)
				if(g[i][j] > 0)
					bfs(i,j);
		/*for(int i = 1;i <= num; ++i){
			for(int j = 1; j<= num; ++j){
				printf("%d ",graph[i][j]);
			}
			putchar('/n');
		}*/
		printf("%d/n",prime());
	}
	return 0;
}

【上篇】次小生成树
【下篇】poj 2774

作者: shanks

该日志由 shanks 于6年前发表在综合分类下，最后更新于 2018年04月05日.
转载请注明: poj 基础图论题小结 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

poj 基础图论题小结

作者: shanks

书签

最新文章New

本站推荐

返回首页