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