首页 > ACM题库 > HDU-杭电 > hdu 1949 Tourist-最小生成树-[解题报告]C++
2013
12-26

hdu 1949 Tourist-最小生成树-[解题报告]C++

Tourist

问题描述 :

A lazy tourist wants to visit as many interesting locations in a city as possible without going one step further than necessary. Starting from his hotel, located in the north-west corner of city, he intends to take a walk to the south-east corner of the city and then walk back. When walking to the south-east corner, he will only walk east or south, and when walking back to the north-west corner, he will only walk north or west. After studying the city map he realizes that the task is not so simple because some areas are blocked. Therefore he has kindly asked you to write a program to solve his problem.
Given the city map (a 2D grid) where the interesting locations and blocked areas are marked, determine the maximum number of interesting locations he can visit. Locations visited twice are only counted once.

输入:

The first line in the input contains the number of test cases (at most 20). Then follow the cases. Each case starts with a line containing two integers, W and H (2 <= W, H <= 100), the width and the height of the city map. Then follow H lines, each containing a string with W characters with the following meaning:
‘.’ Walkable area
‘*’ Interesting location (also walkable area)
‘#’ Blocked area
You may assume that the upper-left corner (start and end point) and lower-right corner (turning point) are walkable, and that a walkable path of length H +W – 2 exists between them.

输出:

The first line in the input contains the number of test cases (at most 20). Then follow the cases. Each case starts with a line containing two integers, W and H (2 <= W, H <= 100), the width and the height of the city map. Then follow H lines, each containing a string with W characters with the following meaning:
‘.’ Walkable area
‘*’ Interesting location (also walkable area)
‘#’ Blocked area
You may assume that the upper-left corner (start and end point) and lower-right corner (turning point) are walkable, and that a walkable path of length H +W – 2 exists between them.

样例输入:

2
9 7
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........
5 5
.*.*.
*###.
*.*.*
.###*
.*.*.

样例输出:

7
8

题目链接:10099 – The Tourist Guide

题目大意:有n个旅游景点,以及m条路,给出m条路的信息,包括连接的景点序号,限制人数,然后再给出起始点和终止点,以及总人数,问说需要多少次的运输才能使得所有人到达目的地。


解题思路:这题因为以前做过一遍,所以知道有个坑点,就是导游每次必须跟团。我是用kruskal算法去做的,因为题目只要求说运输的次数最少,没有说要求路径的长度,所以每次从最长的边开始加入,直道起点与终点相连接,那么最后加入的那条边就是整条路的限制人数,然后算运输次数时注意导游每次要跟队就可以了。


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 105;
struct state {
	int r, l, num;
}s[N * N];
int n, m, ans, begin, end, sum, f[N];

int getfather(int x) {
	return x == f[x] ? x : f[x] = getfather(f[x]);
}

bool cmp(const state& a, const state& b) {
	return a.num > b.num;
}

void init() {
	for (int i = 0; i < m; i++)
		scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].num);
	scanf("%d%d%d", &begin, &end, &sum);
	for (int i = 1; i <= n; i++)
		f[i] = i;
	sort(s, s + m, cmp);
}

int kruskal() {
	for (int i = 0; i < m; i++) {
		int p = getfather(s[i].l), q = getfather(s[i].r);
		if (p != q) {
			f[p] = q;
			if (getfather(begin) == getfather(end))
				return s[i].num;
		}
	}
	return 0;
}

int solve() {
	if (sum % ans)
		return sum / (ans - 1) + 1;
	else
		return sum / (ans - 1);
}

int main () {
	int cas = 1;
	while (scanf("%d%d", &n, &m), n || m ) {
		init();
		ans = kruskal();
		printf("Scenario #%d\n", cas++);
		printf("Minimum Number of Trips = %d\n\n", solve());
	}
	return 0;
}

解题转自:http://blog.csdn.net/keshuai19940722/article/details/12653689


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的