首页 > 搜索 > DFS搜索 > hdu 2614 Beat-DFS-[解题报告]C++
2014
02-12

hdu 2614 Beat-DFS-[解题报告]C++

Beat

问题描述 :

Zty is a man that always full of enthusiasm. He wants to solve every kind of difficulty ACM problem in the world. And he has a habit that he does not like to solve
a problem that is easy than problem he had solved. Now yifenfei give him n difficulty problems, and tell him their relative time to solve it after solving the other one.
You should help zty to find a order of solving problems to solve more difficulty problem.
You may sure zty first solve the problem 0 by costing 0 minute. Zty always choose cost more or equal time’s problem to solve.

输入:

The input contains multiple test cases.
Each test case include, first one integer n ( 2< n < 15).express the number of problem.
Than n lines, each line include n integer Tij ( 0<=Tij<10), the i’s row and j’s col integer Tij express after solving the problem i, will cost Tij minute to solve the problem j.

输出:

The input contains multiple test cases.
Each test case include, first one integer n ( 2< n < 15).express the number of problem.
Than n lines, each line include n integer Tij ( 0<=Tij<10), the i’s row and j’s col integer Tij express after solving the problem i, will cost Tij minute to solve the problem j.

样例输入:

3
0 0 0
1 0 1
1 0 0
3
0 2 2
1 0 1
1 1 0
5
0 1 2 3 1
0 0 2 3 1
0 0 0 3 1
0 0 0 0 2
0 0 0 0 0

样例输出:

3
2
4
Hint
Hint: sample one, as we know zty always solve problem 0 by costing 0 minute. So after solving problem 0, he can choose problem 1 and problem 2, because T01 >=0 and T02>=0. But if zty chooses to solve problem 1, he can not solve problem 2, because T12 < T01. So zty can choose solve the problem 2 second, than solve the problem 1.

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.

URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2614
Name  : 2614 Beat

Date  : Saturday, August 13, 2011
Time Stage : 1 hours around

Result:
4404951	2011-08-13 14:52:37 Accepted 2614 31MS 192K 1185 B C++ pyy


Test Data:

Review:
一开始没用used标记已做完的工作,结果超时了……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define infinity	0x7f7f7f7f
#define minus_inf	0x80808080

#define MAXSIZE 16

int n, most ;
int time[MAXSIZE][MAXSIZE], used[MAXSIZE] ;

void dfs (int cur, int t, int cnt)
{
	most = max (most, cnt) ; // 这里的比较要随时进行
	if (cnt == n)
		return ;

	int i ;
	for (i = 1 ; i < n ; ++i)
	{
		if (!used[i] && time[cur][i] >= t)
		{
			used[i] = 1 ;
			dfs (i, time[cur][i], cnt + 1) ;
			used[i] = 0 ;
		}
	}
}

int main ()
{
	int i, j ;
	while (scanf ("%d", &n) != EOF)
	{
		most = 0 ;
		memset (used, 0, sizeof (used)) ;
		for (i = 0 ; i < n ; ++i)
		{
			for (j = 0 ; j < n ; ++j)
				scanf ("%d", &time[i][j]) ;
		}
		used[0] = 1 ;
		dfs (0, 0, 1) ;
		printf ("%d\n", most) ;
	}
	return 0 ;
}

解题转自:http://blog.csdn.net/panyanyany/article/details/6684235


,
  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……