|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияCan't you tell me how to solve this problem? I have used both Blossom and BFS but WA(19). Blossom is O(N^4), BFS is wrong in fact - and I don't know absolutely correct and fast algo... So, my solution is just BFS-based heuristics. Algorithm is not easy. I can send you a PDF. Please send me. My email is quangviet2004@yahoo.com Thanks Link Vladimir Yakovlev (USU) 23 июн 2004 01:10 Gabow's algorithm also uses Berge's theorem. This theorem is basic in matching theory. What method did you use? My algorithm goes as follows: do foundPath=false for i=1 to n do begin if exists augumenting path from vertex i then begin apply found path foundPath=true end end while (foundPath) Edited by author 23.06.2004 04:40 But how do you check if exists augumenting path? A simple DFS? Or something like random search? Can you send me your source? See e-mail in my profile. Can you send it to me? Thanks quangviet2004@yahoo.com I can send it to everyone who already has Accepted - otherwise it would be unfair. But I can give you my DFS: int FindAndApply(int v) { visited[v] = 1; for (PEdge t=out[v]; t != NULL; t = t->next) { int u = t->v; if (u == S[v]) continue; if (visited[u] || visited[S[u]]) continue; visited[u] = 1; if (S[u] == 0 || FindAndApply(S[u])) { S[u] = v; S[v] = u; return 1; } } return 0; } S[i] holds a vertex matched with vertex i. Edited by author 23.06.2004 19:33 You can send it to anybody now becouse it doesn't work anymore ;-) I've added several new tests. All wrong methods (BFS, DFS, random search) won't pass these tests. If your wrong program still can get AC now, please tell me. Yes, I have access, but I don't see the tests if I don't solve the problem. Thanks (-) Dmitry 'Diman_YES' Kovalioff 23 июн 2004 08:32 |
|
|