Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用BFS复杂度为 O(max(NM , N^2)) 竟然还会TLE!最后我不得不进行矩阵压缩,157MS通过,哈哈。。。。

Posted by gfedcba at 2009-03-03 13:29:04 on Problem 3275 and last updated at 2009-03-03 13:33:24
In Reply To:上一道的COW PINIC我用DFS求本身1+入度,这一道我决定用BFS,求出度,力求同时灵活掌握DFS和BFS.此两题用Floyd算法(时间复杂度为N^3)都会TLE,可见Floyd算法还有待优化呀!!!!! Posted by:gfedcba at 2009-03-02 23:18:30
        scanf("%d%d",&cows,&rates);
	for (i=0; i<=rates-1; i++)
	{
		scanf("%d%d",&cow1,&cow2);
		matrix[cow1][++compress[cow1]] = cow2;
	}
	
	for (n=1; n<=cows; n++)
	{
		memset(isVisit, 0, (N+1)*sizeof(bool));
		dfs(n);
	}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator