Show all threads Hide all threads Show all messages Hide all messages | weak tests | Vit Demidenko | 1099. Work Scheduling | 15 Jun 2021 21:00 | 1 | | If blossom's writer gets WA12 ... | Mickkie | 1099. Work Scheduling | 13 Jan 2020 22:19 | 2 | 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. | Does anybody want to know the best algorithm for this problem.My program use only 0.03 sec to get accepted. | Huang Yizheng | 1099. Work Scheduling | 2 May 2014 01:12 | 60 | 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 ТестоВор2 3 May 2004 02:14 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! 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! | Why are blossoms needed? | Carlos Colmenares | 1099. Work Scheduling | 31 Jan 2013 23:26 | 1 | 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. | who can give me some wa data??although I know my solution is wa. | ben3ben | 1099. Work Scheduling | 17 Apr 2012 17:00 | 2 | #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 | Very userful paper! Modified DFS to solve mathchig without flowers tree | RybKMU | 1099. Work Scheduling | 4 Feb 2012 04:58 | 5 | 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... | about judge? | ckl1994 | 1099. Work Scheduling | 17 May 2011 05:58 | 1 | Did it use special Judge or somethine else? | why wr on test 12# | DSLZTX | 1099. Work Scheduling | 12 Apr 2011 17:57 | 2 | 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 just used dfs with a little change and I ACed my program in 0.04 sec. | shrek | 1099. Work Scheduling | 6 Mar 2011 10:16 | 5 | 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. | Who can give test#1 | cloudygooose | 1099. Work Scheduling | 20 Aug 2010 12:15 | 1 | 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? | some tests... | Oracle[Lviv NU] | 1099. Work Scheduling | 20 Aug 2010 10:55 | 3 | 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 | Please help me WA2 can you give me some test aganist it? | Edric Mao | 1099. Work Scheduling | 10 Aug 2010 17:26 | 1 | 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. | Problem 1099 "Work scheduling" has been rejudged | Vladimir Yakovlev (USU) | 1099. Work Scheduling | 31 May 2010 13:39 | 2 | New tests have been added. 91 authors have lost AC after rejudge. Thanks to Sergey Kopeliovich. | Disaster WA#64 | lrcrichard | 1099. Work Scheduling | 17 Apr 2010 18:39 | 1 | | why WA#61? | Gary | 1099. Work Scheduling | 1 Apr 2010 18:40 | 1 | | Problem 1099 "Work scheduling" has been rejudged | Vladimir Yakovlev (USU) | 1099. Work Scheduling | 20 Jul 2009 12:34 | 1 | New tricky tests have been added. 104 authors have lost AC after rejudge. Thanks to Arseny Smirnov. | Give me some another tests, please | igor2103 | 1099. Work Scheduling | 30 Jun 2009 07:51 | 1 | Can you give me some another test data suite? With correct output in each... I feel, I do not understand this task properly( | Project on Edmonds` flower tree algorithm | HeypaBHoBeceH | 1099. Work Scheduling | 29 Jun 2009 18:33 | 1 | 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 | WA#57... | StarForever | 1099. Work Scheduling | 17 Jan 2007 20:39 | 3 | 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! | Problem 1099 "Work scheduling" has been rejudged (+) | Vladimir Yakovlev (USU) | 1099. Work Scheduling | 23 Dec 2006 02:02 | 1 | TL was decreased to 0.5 sec. New tests were added. Thanks to Vsevolod Oparin. 35 authors have lost AC. |
|
|