Maximum Matching
ავტორი brolia
SRM 549 Div1 250p
წერილები: 50
brolia says:
10 ივლისი 2012, 13:37
import java.util.*;


public class PointyWizardHats{
	int i, j, n, m, ans;
	boolean [] vis, a[];
	
	public int getNumHats(int[] topHeight, int[] topRadius, int[] bottomHeight, int[] bottomRadius){
			n = topHeight.length;
			m = bottomHeight.length;
			a = new boolean[n + m + 2][n + m + 2];
			vis = new boolean[n + m + 2];
			for (i = 0; i < n; i++)
				for (j = 0; j < m; j++)
					if (check(topHeight[i], topRadius[i], bottomHeight[j], bottomRadius[j])){
						a[i + 1][n + j + 1] = true;
					//	a[n + j + 1][i + 1] = true;
						System.out.println((i + 1) + " " + (n + j + 1));
					}
			for (i = 1; i <= n; i++)
				a[0][i] = true;
				
			for (j = 1; j <= m; j++)
				a[n + j][n + m + 1] = true;
			while (findPath(0)){
				Arrays.fill(vis, false);
				ans ++;
			}
			return ans;
	}
	
	boolean check(int topHeight, int topRadius, int bottomHeight, int bottomRadius){
		return topRadius < bottomRadius && topRadius * bottomHeight < topHeight * bottomRadius;
	}
	
	boolean findPath(int v){
		System.out.println(v);
		vis[v] = true;
		if (v == n + m + 1) return true;
		for (int w = 0; w <= n + m + 1; w ++)
			if (!vis[w] && a[v][w])
				if (findPath(w)){
					a[v][w] = false;
					a[w][v] = true;
					return true;
				}
		return false;
	}
}


gzis agebisas marto erT mxares roca vakeTeb gzas maSin gadis, da roca orive mxares aRar gadis. anu dakomentarebuli rac maq imas uncommenti ro gavukeTo aRar muSaobs :-?


rato iZleba sxvadasxva Sedegs ? nakadis gaSvebisas sadac gaivlis is xom mainc gaafalse_bs sapirispiro gzebs :-?
გთხოვთ გაიარეთ ავტორიზაცია კომენტარის გამოსაქვეყნებლად.
სიახლეები Facebook-ზე
მომავალი ღონისძიებები
მომავალი ღონისძიებების სია ცარიელია.
ღონისძიებების კალენდარი
მხარდამჭერები






ახალი კომენტარები
Dixtosa Episode II - Analysis...
Eშისაიდან მოვიდა 3**13?ისე 4 * 52 * 3**13 = 331M+ ...
Quick GeOlymp 2013 - ფინალური ეპიზოდი იწყება...
Upsolving ჩაირთო...
saba_tavdgiridze GeOlymp 2013 - ფინალური ეპიზოდი იწყება...
აღარ მინდა.:)...
saba_tavdgiridze GeOlymp 2013 - ფინალური ეპიზოდი იწყება...
B ამოცანის 17 ტესტს ვერ მიმანიშნებთ?...
tornike5 GeOlymp 2013 - ფინალის შესახებ...
ვაპირებდი იგივე მეკითხა მარა მეგონა უეჭველი იქნება...
giorgi123 GeOlymp 2013 - ფინალის შესახებ...
მადლობა.შარშან ფინალში ამოცანების ყურებით ვიფარგლე...
Elle GeOlymp 2013 - ფინალის შესახებ...
შარშან ფინალს codeblocks-ით წერდით?დავაყენეთ codeb...