JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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.html
http://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;
RSS