JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Assignment Problem and Hungarian Algorithm (Article) Java implementation
 Java implementation | Reply Nice tutorial!! Here is my Java implementation if anyone wants it ...``` /* * w[i][j] = amount bidder j is willing to pay for item i (0 if he is not bidding) * run time is O(nm^2) where n = #of items and m = #of bidders * resets negative bids in w to 0 * returns a, where a[i] = j means ith item got assigned to bidder j * a[i] = -1 means item i did not get assigned * for minimizing set w[i][j] = max(w) - w[i][j] * for assigning all, w[i][j] = min(w) + w[i][j] */ public static int[] hungarianMethod(int w[][]) { final int n = w.length, m = w[0].length, PHI = -1, NOL = -2; boolean[] x[] = new boolean[n][m], ss = new boolean[n], st = new boolean[m]; int[] u = new int[n], v = new int[m], p = new int[m], ls = new int[n], lt = new int[m], a = new int[n]; int f = 0;   for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) f = max(f, w[i][j]);   fill(u, f); fill(p, INF); fill(lt, NOL); fill(ls, PHI); fill(a, -1);   while(true) { f = -1; for(int i = 0; i < n && f == -1; i++) if(ls[i] != NOL && !ss[i]) f = i;   if(f != -1) { ss[f] = true; for(int j = 0; j < m; j++) if(!x[f][j] && u[f] + v[j] - w[f][j] < p[j]) { lt[j] = f; p[j] = u[f] + v[j] - w[f][j]; } } else { for(int i = 0; i < m && f == -1; i++) if(lt[i] != NOL && !st[i] && p[i] == 0) f = i;   if(f == -1) { int d1 = INF, d2 = INF, d; for(int i : u) d1 = min(d1, i);   for(int i : p) if(i > 0) d2 = min(d2, i);   d = min(d1, d2);   for(int i = 0; i < n; i++) if(ls[i] != NOL) u[i] -= d;   for(int i = 0; i < m; i++) { if(p[i] == 0) v[i] += d; if(p[i] > 0 && lt[i] != NOL) p[i] -= d; }   if(d2 >= d1) break; } else { st[f] = true; int s = -1;   for(int i = 0; i < n && s == -1; i++) if(x[i][f]) s = i;   if(s == -1) { for(int l,r ;;f=r) { r = f; l = lt[r];   if(r >= 0 && l >= 0) x[l][r] = !x[l][r]; else break;   r = ls[l]; if(r >= 0 && l >= 0) x[l][r] = !x[l][r]; else break; }   fill(p, INF); fill(lt, NOL); fill(ls, NOL); fill(ss, false); fill(st, false);   for(int i = 0; i < n; i++) { boolean ex = true; for(int j = 0; j < m && ex; j++) ex = !x[i][j]; if(ex) ls[i] = PHI; } } else ls[s] = f; } } }   for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(x[i][j]) a[j] = i; return a; }   ```
 Re: Java implementation (response to post by wrick) | Reply It was generous of you to post this, but let me remind people that if you use this code in a contest [at TopCoder] (unlesss you are wrick) you will be suspended for cheating.[At TopCoder you must write ALL of your code yourself.]
 Re: Java implementation (response to post by Rustyoldman) | Reply How about in the google code jam? Rules state that you can use a library written by somebody else under the condition we have a license for it. It's not specified how a code with no license provided is treated.
 Re: Java implementation (response to post by Rustyoldman) | Reply Really? Wow! My "library" is all codes from my ACM team...And, yes, I don't know much about licenses - anyone can use this.
 Re: Java implementation (response to post by wrick) | Reply It is not really forbidden to use some other person's code. What's forbidden is to get caught doing so.
 Re: Java implementation (response to post by vexorian) | Reply It is still cheating, even if you don't get caught. The difference is that not getting caught is successful cheating while getting caught is unsuccessful cheating.
 Re: Java implementation (response to post by wrick) | Reply You want to be careful using shared library codes.
 Re: Java implementation (response to post by Rustyoldman) | Reply I didn't say it is not cheating.
 Re: Java implementation (response to post by vexorian) | Reply The rules specifically forbid cheating.
 Re: Java implementation (response to post by wrick) | Reply what are min, max , fill are they ready functions in java...
 Re: Java implementation (response to post by Rustyoldman) | Reply I didn't imply otherwise.
 Re: Java implementation (response to post by onmcv) | Reply http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.htmlhttp://java.sun.com/j2se/1.4.2/docs/api/java/lang/Math.html
 Re: Java implementation (response to post by wrick) | Reply Nice code. There is a small bug though: the second-last line should be```a[i] = j; ```
 Forums Tutorial Discussions Assignment Problem and Hungarian Algorithm (Article) Java implementation Previous Thread  |  Next Thread