| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用BFS复杂度为 O(max(NM , N^2)) 竟然还会TLE!最后我不得不进行矩阵压缩,157MS通过,哈哈。。。。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator