ACM/ICPC 之 Floyd练习六道(ZOJ2027-POJ2253-POJ2472-POJ1125-POJ1603-POJ2607)

以Floyd解法为主的练习题六道

---

ZOJ2027-Travelling Fee

//可免去一条线路中直接连接两城市的最大旅行费用，求最小总旅行费用

//Time:0Ms	Memory:604K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 205

#define MAXS 12

#define INF 0x3f3f3f3f

int n,m;

int dis[MAX][MAX];

int high[MAX][MAX];	//该线路中直接连接两城市的最大旅行费用

struct City {

	char name[MAXS];

}c[MAX];

int find(char s[MAXS])

{

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

		if (!strcmp(s, c[i].name))	return i;

	return -1;

}

void floyd()

{

	for (int k = 0; k < n; k++)

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

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

			{

				if (high[i][k] == -1 || high[k][j] == -1)	continue;

				int maxCost = max(high[i][k], high[k][j]);

				if (dis[i][j] - high[i][j] > dis[i][k] + dis[k][j] - maxCost)

				{

					dis[i][j] = dis[i][k] + dis[k][j];

					high[i][j] = maxCost;

				}

			}

}

int main()

{

	while (scanf("%s%s", c[0].name, c[1].name) != EOF)

	{

		memset(dis, INF, sizeof(dis));

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

		int d; n = 2;

		char s[MAXS],t[MAXS];

		scanf("%d", &m);

		while (m--)

		{

			scanf("%s%s%d", s, t, &d);

			int ns = find(s), nt = find(t);

			if (ns == -1) {

				memcpy(c[n].name, s, sizeof(s));

				ns = n++;

			}

			if (nt == -1) {

				memcpy(c[n].name, t, sizeof(t));

				nt = n++;

			}

			high[ns][nt] = dis[ns][nt] = d;

		}

		floyd();

		printf("%d\n", dis[0][1] - high[0][1]);

	}

	return 0;

}

---

POJ2253-Frogger

//求0->1间的最小的最大单次青蛙跳跃距离

//Time:94Ms	Memory:508K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define MAX 205

#define POW2(x) ((x)*(x))

#define DIS(a,b) (sqrt(POW2(p[a].x - p[b].x) + POW2(p[a].y - p[b].y)))

struct Point {

	double x, y;

}p[MAX];

int n;

double dis[MAX][MAX];	//两点间最小的最大一次跳跃距离

void floyd()

{

	for (int k = 0; k < n; k++)

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

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

				dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));

}

int main()

{

	int cas = 1;

	while (scanf("%d", &n), n)

	{

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

		{

			scanf("%lf%lf", &p[i].x, &p[i].y);

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

				dis[i][j] = dis[j][i] = DIS(i, j);

			dis[i][i] = 0;

		}

		floyd();

		printf("Scenario #%d\n", cas++);

		printf("Frog Distance = %.3f\n\n", dis[0][1]);

	}

	return 0;

}

---

POJ2472-106 miles to Chicago

//求1到n的最大存活率

//Time:157Ms	Memory:264K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 105

int n, m;

double dis[MAX][MAX];

void floyd()

{

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

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

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

				dis[i][j] = max(dis[i][j], dis[i][k] * dis[k][j]);

}

int main()

{

	while (scanf("%d%d", &n, &m), n)

	{

		memset(dis, 0, sizeof(dis));

		int x, y, d;

		while (m--) {

			scanf("%d%d%d", &x, &y, &d);

			dis[x][y] = dis[y][x] = d / 100.0;

		}

		floyd();

		printf("%.6lf percent\n", 100*dis[1][n]);

	}

	return 0;

}

---

POJ1125-Stockbroker Grapevine

//从某点扩散到所有点的最短时间-求出该点及时间

//Time:0Ms	Memory:208K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 105

#define INF 0x3f3f3f3f

int n, m;

int dis[MAX][MAX];

int time[MAX];

void floyd()

{

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

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

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

				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

}

int main()

{

	while (scanf("%d", &n), n)

	{

		memset(dis, INF, sizeof(dis));

		memset(time, 0, sizeof(time));

		int y, d;

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

		{

			scanf("%d", &m);

			while (m--) {

				scanf("%d%d", &y, &d);

				dis[x][y] = d;

				dis[x][x] = 0;

			}

		}

		floyd();

		int Min = INF;

		int k = 0;

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

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

				time[i] = max(time[i], dis[i][j]);

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

		{

			if (Min > time[i])

			{

				Min = time[i];

				k = i;

			}

		}

		if (Min == INF)	printf("disjoint\n");

		else printf("%d %d\n", k, Min);

	}

	return 0;

}

---

POJ1603-Risk

//求依靠攻打接壤国需要最少攻打多少国家才能从起始国家打到终止国家

//Time:0Ms	Memory:168K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 21

#define INF 0x3f3f3f3f

int n, m;

int dis[MAX][MAX];

void floyd()

{

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

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

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

				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

}

int main()

{

	int cas = 0;

	n = 20;

	while (scanf("%d", &m) != EOF)

	{

		memset(dis, INF, sizeof(dis));

		int x, y;

		for (x = 1; x <= 19; x++)

		{

			while (m--) {

				scanf("%d", &y);

				dis[x][y] = dis[y][x] = 1;

			}

			scanf("%d", &m);

		}

		floyd();

		if (cas)	printf("\n");

		printf("Test Set #%d\n", ++cas);

		while (m--) {

			scanf("%d%d", &x, &y);

			printf("%d to %d: %d\n", x, y, dis[x][y]);

		}

	}

	return 0;

}

---

POJ2607-Fire Station

　　这道题稍微比上面的五道题复杂一些

//Floyd解法

//已知消防站，现建新消防站，使得所有路口到消防站的最大值减至最小，将最小序列路口输出

//Time:1797Ms	Memory:1164K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 505

#define INF 0x3f3f3f3f

int f, n, m;

int dis[MAX][MAX];

bool v[MAX];

int md[MAX];    //各路口到消防站最短距离

void floyd()

{

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

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

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

				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

}

int main()

{

	memset(dis, INF, sizeof(dis));

	memset(md, INF, sizeof(md));

	scanf("%d%d", &f, &n);

	int x, y, d;

	for (int i = 0; i < f;i++){

		scanf("%d", &x);

		v[x] = true;

		dis[x][x] = 0;

	}

	while (scanf("%d%d%d", &x, &y, &d) != EOF)

		dis[x][y] = dis[y][x] = d;

	floyd();

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

	{

		dis[i][i] = 0;

		if (!v[i])	continue;

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

			md[j] = min(md[j], dis[i][j]);

	}

	int Max = INF, k = 1;	//默认为1，否则A不掉(我怀疑数据有问题或题目描述不清)

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

	{

		if (v[i])	continue;

		int tmp = 0;

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

			tmp = max(tmp, min(md[j], dis[i][j]));

		if (Max > tmp)

		{

			Max = tmp;

			k = i;

		}

	}

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

	return 0;

}