2014
02-12

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 */
/*----------------------------------------------------------------------------//

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:

//----------------------------------------------------------------------------*/

#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 ;
}

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

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