In my case this test may help you 16 19 1 2 2 3 3 4 4 5 5 1 1 6 6 7 7 8 8 9 9 10 10 6 5 11 11 12 12 13 13 4 3 14 14 15 15 16 16 2 The sequence of contraction affects the solution if you do not repeat the process after release the blossom. if you contract (6,7,8,9,10), (4,5,11,12,13), (2,3,14,15,16) first you get maximum matching. but if you contract (1,2,3,4,5) first and don't repeat the process after release it you don't get to the maximum. Hope this helps. Thank you for this case! I didn't realize that the blossoms should be reset in each iteration. Yes, email me at raynaldo_adp@yahoo.com Write it here or email to: lee-e.@263.net(pay attention that there's a dot before '@') dima.voitovich@mail.ru thank you I also want to know! baiko@go.ro > please send me the solution at Daniciuc_Marian@yahoo.com > > please email me the solution at Daniciuc_Marian@yahoo.com > Yes, email me at ratrax2002@yahoo.com > I want to know too, email me at andie13@bonbon.net > Anh Hiep oi gui luon cho em nhe Cestlavie_27@yahoo.com Edited by author 12.04.2004 21:44 give me one thanks ls223224@hotmail.com please email me at <peng1294@hotmail.com> thanks Mail to "walter_ddr@163.com",please. please send it to lijianopenfind@hotmail.com mail me: mc01wjg@student.zsu.edu.cn Yes , I`d like to see it too :) e-mail me : yosif_slavov@yahoo.com Thanks dont forget chert0v@list.ru I'd like to know, too !!!! Don't forget about me !!!! VRomanchik@tut.by I'd like to know, too !!!! Don't forget about me !!!! VRomanchik@tut.by me too, thx! cannon_songkai@yahoo.com.cn Please mail me:leibniz_sunhong@sina.com Would you give me an email?My email is: luotianbao@163.com My E-mail is ge_worm@hotmail.com post it already. everyone wants to know Edited by author 29.05.2004 00:38 hey j also want to know send to pavlo4@wp.pl thx me too windyblue730@hotmail.com thank you so much please, me too dkorduban[at]ukr.net please,thx u9089000@cc.ncu.edu.tw mail:zfd4230@sina.com thanks So there are so many e-mails that i can start spuming ;) hbn@pku.edu.cn Thank you!!! yuyuanming163@163.com Thank you! cyh412@163.com thank you! I want it too, please. alexpopa9@gmail.com Thank you ! Please, send me too!!! thx!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! email: xujand000@rambler.ru Edited by author 18.10.2006 16:14 Edited by author 18.10.2006 16:14Thank you! Please mail to "ywwbill@163.com" You are so great that you can make your program solve the problem in just 0.03s erictwpt@gmail.com Thank you..!!! My solution only runs in 0.015 sec. Maximum non-bipartie matching is pretty general problem to post that algo in forum (not code of course). Please give me! cuijiangfeng_copy@yahoo.com.cn Edited by author 06.11.2008 23:27 Edited by author 06.11.2008 23:28 Hi ,could you tell me the aglorithm please? my email is ikhomeriki@gmail.com I might be wrong be as far as I can see you did not solve this problem(it is in your list of problems under development). I have a solution which takes 0.0001 and has the same success. If anyone wants it - write here. It would be great to have it and look how great coders work, i'm new to programming contests and would appreciate any help.. my email: sparemail4books@gmail.com Thanks a lot please mail:twinsclover@163.com thx!! Yes, please, send me whatever you have to rwrobinson@estudiantes.uci.cu or to shaka.shadows@gmail.com. I also want to know,my email is lagiro@estudiantes.uci.cu or lagirouci@gmail.com. thanks you... please email me dslztx@gmail.com PLease if someone can send me tooo.... sfpm007@gmail.com Send me please! goldenxbullet@gmail.com thanks! You're so awesome, dwhuang9@gmail.com Thank you ikhomeriki@gmail.com please send me algo as well, thanks! Hello all, I've been studying this topic lately, and I came out with a question which answer I have not been able to find anywhere. I know very well the history about Edmonds' Blossom algorithm, however, it is well known that a given matching is the maximum one if no more augmenting paths can be found on the graph. So, my question is the following one: I implemented a simple DFS algorithm that tries to find an augmenting path, and if found, it makes the flip we all know and adds/removes the flipped edges to the matching. In my DFS I only mark nodes that are reached in even levels (i.e. nodes found after following a matched edge, plus the first unmatched node) as visited, furthermore I also care about the nodes in the active path so as to avoid stepping in the same node and generating cycles. So, why this does not work? of course the reason is because there are augmenting paths my algorithm cannot find, but why? All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary! Thanks for your help. #include <cstdio> #include <string.h> using namespace std; struct dat_edge { int last,aim; }edge[500000]; int temp[300],len_edge,pl[300],next[300],n,m; void edge_insert(int x,int y) { len_edge++; edge[len_edge].aim=y; edge[len_edge].last=pl[x]; pl[x]=len_edge; } bool dfs(int root,int ps) { if (temp[root]==ps) return false; if (ps==-1) return true; temp[root]=ps; int p=pl[root]; bool t; while (p!=-1) { int tmp=edge[p].aim; if (temp[tmp]==ps) { p=edge[p].last;continue; } if (next[tmp]==-1) t=dfs(tmp,-1); else t=dfs(next[tmp],ps); if (t) { next[root]=edge[p].aim; next[edge[p].aim]=root; return true; } p=edge[p].last; } return false; } int main() { //freopen("1099.in","r",stdin); //freopen("1099.out","w",stdout); int i,j,k,ans,coun,x,y; bool ok; scanf("%d",&n); len_edge=-1; for (i = 0;i<=n;i++) pl[i]=-1; while (scanf("%d%d",&x,&y)!=EOF) { edge_insert(x,y); edge_insert(y,x); } coun=0; for (i = 0;i<=n;i++) next[i]=-1; memset(temp,0,sizeof(temp)); ans=0; for (i = 1;i<=n;i++) { ok=false; if (next[i]==-1) ok=dfs(i,++coun); if (ok) ans++; } printf("%d\n",ans*2); for (i = 1;i<=n;i++) if (next[i]>i) { printf("%d %d\n",i,next[i]); } } 15 1 7 10 9 7 1 5 2 1 6 13 8 13 15 2 3 3 6 10 14 5 5 11 15 1 3 13 5 15 3 13 2 ans:12 What is file .Z? What prog I can use to viewed it! It is UNIX archive. Use 7-Zip This algo not easier than flowers tree... Did it use special Judge or somethine else? does anybody have the test data of 12#,i am wrong on this test data for a long time,could someone help me?my thanks. me too, I got tle, who can give the test data I can send it to anybody who has ACed his(or hers). I have ACed. Could you send it to me? jsyzzyc@gmail.com Please, send it to me(IGrebnov@goal.ru). I will find bad test and add to server. Edited by author 15.12.2006 12:30 Edited by author 15.12.2006 12:30 please send to me dslztx@gmail.com,thanks. At first I got WA#12 I change a few codes then I got WA#1 I can not got WA#12 Who can help me? 20 9 13 12 14 12 19 12 20 13 18 13 20 17 20 18 20 //ans: 6 20 2 6 2 8 3 13 3 15 3 16 3 17 6 11 6 12 6 13 6 15 6 18 8 11 9 13 11 14 11 16 11 18 12 14 12 19 13 18 15 16 //ans: 14 10 1 4 1 6 1 8 4 10 4 3 3 7 4 6 6 2 2 5 5 9 //ans: 10 8 1 2 2 3 1 3 1 4 1 5 //ans: 4 4 1 2 1 3 1 4 2 3 //ans: 4 10 10 9 10 2 10 1 9 6 9 5 8 7 8 2 8 1 7 4 7 3 6 5 6 3 4 3 //ans: 10 10 1 2 1 9 1 10 2 5 2 6 3 4 3 9 3 10 4 7 4 8 5 6 5 8 7 8 //ans: 10 8 1 2 1 3 1 6 2 3 2 4 4 7 4 8 5 6 5 7 //ans: 8 8 1 2 1 7 1 8 2 5 2 6 3 4 3 7 4 5 5 6 //ans: 8 16 1 7 2 4 2 5 3 15 4 5 5 12 5 13 6 14 6 16 8 12 8 14 9 10 9 15 11 15 13 14 //ans: 14 5 1 2 2 3 3 4 3 5 1 5 //ans: 4 6 1 2 2 3 1 3 3 4 2 5 5 6 //ans: 6 5 1 2 2 3 1 3 3 4 2 5 //ans: 4 3 1 2 2 3 1 3 //ans: 3 10 1 2 2 3 3 5 2 4 9 10 //ans: 6 4 1 2 2 3 1 3 1 4 //ans: 4 5 1 2 1 3 1 4 1 5 //ans: 2 5 1 2 1 3 1 4 1 5 5 2 //ans: 4 And the test against the greed algorithm. 10 1 2 1 3 2 3 2 4 1 4 3 4 3 5 5 6 6 7 6 8 6 9 6 10 7 8 7 9 7 10 8 9 8 10 9 10 //ans: 10 program ural; var n,a,b,z,i:byte; r:integer; h:array[1..222]of integer; l:array[1..49062]of integer; t:array[1..49062]of byte; p,u:array[1..222]of boolean; v:array[1..222]of byte; procedure search(f,d:byte); var r:integer; begin r:=h[d]; p[d]:=true; while r<>0 do begin if(t[r]<>f)and(p[t[r]]=false)then begin if v[d]=0 then begin inc(z); v[d]:=t[r]; v[t[r]]:=d; end; search(d,t[r]); end; r:=l[r]; end; end; function match(d:byte):boolean; var r:integer; begin r:=h[d]; p[d]:=false; while r<>0 do begin if(v[t[r]]>0)and(p[v[t[r]]])and(u[v[t[r]]]=false)and(match(v[t[r]]))then begin v[t[r]]:=d; v[d]:=t[r]; exit(true); end; r:=l[r]; end; u[d]:=true; exit(false); end; begin readln(n); while not eof do begin readln(a,b); inc(r); l[r]:=h[a]; h[a]:=r; t[r]:=b; inc(r); l[r]:=h[b]; h[b]:=r; t[r]:=a; end; for i:=1 to n do if p[i]=false then search(0,i); for i:=1 to n do if v[i]=0 then begin fillchar(p,sizeof(p),true); if match(i) then inc(z); end; writeln(z*2); for i:=1 to n do if v[i]>i then writeln(i,' ',v[i]); end. New tests have been added. 91 authors have lost AC after rejudge. Thanks to Sergey Kopeliovich. New tricky tests have been added. 104 authors have lost AC after rejudge. Thanks to Arseny Smirnov. Can you give me some another test data suite? With correct output in each... I feel, I do not understand this task properly( Hi, I am making a project on Edmonds` flower tree algo, but I am having some difficulties on the actual implemention (I am currently in session so I can't really dedicate all my time to it). Can someone who has solved it in C/C++ please send me his code, or (preferred) send a very short step by step instruction how to implement the main steps - shrinking and expanding blossoms seems to worry me. Thanks very much in advance! My email is slayer_ac[ a t ]abv[ d o t ]bg Edited by author 29.06.2009 18:35 I wonder how many tests there are.... O, damn it. There must be some tests that N>222 because I just change the code const long maxN=222; to const long maxN=500; and I got AC... to Jury, if so, please correct this error... ps.Gabow is very beautiful! TL was decreased to 0.5 sec. New tests were added. Thanks to Vsevolod Oparin. 35 authors have lost AC. |
|