Dining [Joe Zimmerman and Eric Price, 2006]

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others. Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible. Farmer John has cooked F (1 <= F <= 100) types of foods and prepared D (1 <= D <= 100) types of drinks. Each of his N (1 <= N <= 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both. Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2). PROBLEM NAME: dining INPUT FORMAT: * Line 1: Three space-separated integers: N, F, and D * Lines 2..N+1: Each line i starts with a two integers F_i and D_i, the number of dishes that cow i likes and the number of drinks that cow i likes. The next F_i integers denote the dishes that cow i will eat, and the D_i integers following that denote the drinks that cow i will drink. SAMPLE INPUT (file dining.in): 4 3 3 2 2 1 2 3 1 2 2 2 3 1 2 2 2 1 3 1 2 2 1 1 3 3 INPUT DETAILS: Cow 1: foods from {1,2}, drinks from {1,3} Cow 2: foods from {2,3}, drinks from {1,2} Cow 3: foods from {1,3}, drinks from {1,2} Cow 4: foods from {1,3}, drinks from {3} OUTPUT FORMAT: * Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes SAMPLE OUTPUT (file dining.out): 3 OUTPUT DETAILS: One way to satisfy three cows is: Cow 1: no meal Cow 2: Food #2, Drink #2 Cow 3: Food #1, Drink #1 Cow 4: Food #3, Drink #3 The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

სადილი – ლევან გოდერძიშვილის თარგმანი

ძროხები საკმაოდ პრტენზიული მჭამელები არიან. ყოველი ძროხა უპირატესობას ანიჭებს გარკვეულ კერძსა და გარკვეულ სასმელს ანუ აქვს რაღაც „პრეფერენციები“ კერძებისა და სასმლის მიმართ და შესაბამისად უარს ამბობს სხვა ტიპის საკვებზე. ფერმერმა ჯონმა გაამზადა არაჩვეულებრივი საკვები მისი ძროხებისათვის, მაგრამ მას დაავიწყდა გაეთვალისწინებინა მათი პრეფერენციები. რადგანაც ის ყველა ძროხას შესაბამისი საკვებით ვეღარ მოამარაგებს, მას უნდა, რომ მისცეს სრულყოფილი საკვები (კერძი და სასმელი) რაც შეიძლება მეტ ძროხას. ჯონმა გაამზადა F (1 ≤ F ≤ 100) ტიპის კერძი და D (1 ≤ D ≤ 100) ტიპის სასმელი. თითოეული მისი N (1 ≤ N ≤ 100) ძროხა იღებს გადაწყვეტილებას რომ მას სურს მიირთვას კონკრეტული კერძი და დალიოს კონკრეტული სასმელი. ფერმერმა ჯონმა თითოეულ ძროხას ისე უნდა გაუნაწილოს სასმელი და კერძები, რომ რაც შეიძლება მეტ ძროხას შეხვდეს ორივე(სასურველი კერძი და სასმელი). თითოეული სასმელი ან საჭმელი შეიძლება შეხვდეს მხოლოდ ერთ ძროხას (მაგ. როგორც კი მე-2-ე ტიპის კერძი შეირჩევა რომელიმე ძროხისთვის, სხვა ძროხას იმავე მე-2-ე ტიპის კერძი ვეღარ შეხვდება). ამოცანა: სადილი შესატანი მონაცემები: პირველი სტრიქონი: სამი მთელი რიცხვი N, F, D თითოეული გამოყოფილი space სიმბოლოთი. შემდეგი სტრიქონები 2 . . N+1: ყოველი i-ური სტიქონი იწყება ორი მთელი რიცხვით Fi და Di - შესაბამისად რაოდენობა რაოდენობა კერძებისა და სასმელებისა, რომლებიც i-ურ ძროხას მოსწონს. შემდეგი Fi ცალი მთელი რიცხვი მიუთითებს კონკრეტულად იმ კერძებზე, რომლებსაც i-ური ძროხა შეჭამს, ხოლო შემდეგ მოსდევს Di ცალი მთელი რიცხვი, რომლებიც მიუთითებს იმ სასმელებზე, რომლებსაც i ძროხა დალევს. შესატანი მონაცემების ნიმუში (ფაილი dining.in): 4 3 3 2 2 1 2 3 1 2 2 2 3 1 2 2 2 1 3 1 2 2 1 1 3 3 შესატანი მონაცემების განმარტება: ძროხა 1: კერძები {1, 2}, სასმელი {1, 3} ძროხა 2: კერძები {2, 3}, სასმელი {1, 2} ძროხა 3: კერძები {1, 3}, სასმელი {1, 2} ძროხა 4: კერძები {1, 3}, სასმელი {3} გამოსატანი მონაცემების ფორმატი: პირველი სტრიქონი: ერთადერთი მთელი რიცხვი - მაქსიმალური რაოდენობა ძროხებისა, რომლებსაც შეგვიძლია მივართვათ მათი სასურველი კერძი ისევე როგორც მათი სასურველი სასმელი. გამოსატანი მონაცემების ნიმუში (ფაილი dining.out): 3 გამოტანილი მონაცემების განმარტება: ერთი გზა სამი ძროხის დაკმაყოფილებისა: ძროხა 1: არ ვაჭმევთ ძროხა 2: კერძი #2, სასმელი #2 ძროხა 3: კერძი #1, სასმელი #1 ძროხა 4: კერძი #3, სასმელი #3 დირიხლეს პრინიპის მიხედვით, ჩვენ არ შეგვიძლია უკეთესი შესაბამისობის პოვნა, რადგან გვაქვს მხოლოდ 3 ტიპის საჭმელი და 3 ტიპის სასმელი. დანარჩენი ტესტები ცხადია მეტად რთული და მრავალფეროვანია.

dining

This problem is meant to be a standard network flow problem. Consider the following graph with the drinks on top, cows in middle, food on bottom and all edges having capacity one: source / | \ D_1 D_2 .. D_D / \ / \ / \ / \ / \ (put an edge only if Ci likes Dj) C_1a C_2a .. C_Na | | | C_1b C_2b .. C_Nb \ / \ / \ / \ / \ / F_1 F_2 .. F_F (put an edge only if Ci likes Fj) \ | / sink Each path from source to sink corresponds to a cow being fed since it passes through a drink, a cow and a food. Clearly, no drink, cow, or food can be used on two paths due to the edge of limit 1 from source to D_i, C_ia to C_ib, F_i to sink respectively. Hence, the maximum number of cows being fed is the maximum flow of this network. The 'structure' of the flow resembles bipartite matching somewhat, so a initial greedy sweep should take care of most of the flow. Then the standard Ford-Fulkerson algorithm can be applied to get the actual flow. Even though this algorithm is asymptotically a bit slow, it runs quite fast in practice due to the greedy sweep doing most of the work. Testdata At first 20 cases were generated randomly, then a few 'wrong' solutions are considered and the appropriate cases deleted so the following happens (bugs not considered): A max flow solution gets 100% of the cases A brute-force search gets 30-40% of the cases A randomized guessing solution gets 40% of the cases Below is the solution of Romania's Airinei Adrian: #include <stdio.h> #include <string.h> #define MAXN 512 int N, F, D; int src, dest, Q[MAXN], viz[MAXN], from[MAXN]; char C[MAXN][MAXN]; int bfs(void) { int inc, sf, x, i, ok = 1; memset(viz, 0, sizeof(viz)); Q[inc = sf = 0] = src, viz[src] = 1, from[src] = -1; while(inc <= sf && ok) { x = Q[inc++]; for(i = src; i <= dest; i++) if(!viz[i] && C[x][i] > 0) { viz[i] = 1, Q[++sf] = i, from[i] = x; if(i == dest) { x = dest, ok = 0; break ; } } } if(x != dest) return 0; while(from[x] > -1) C[from[x]][x]--, C[x][from[x]]++, x = from[x]; return 1; } void read_and_solve(void) { int i, j, k, nrf, nrd, a, b, flow; scanf("%d %d %d\n", &N, &F, &D); src = 0, dest = F+2*N+D+1; for(i = 1; i <= N; i++) { scanf("%d %d ", &nrf, &nrd); for(k = 1; k <= nrf; k++) scanf("%d ", &j), C[j][i+F] = 1; for(k = 1; k <= nrd; k++) scanf("%d ", &j), C[F+N+i][F+2*N+j] = 1; } for(i = 1; i <= F; i++) C[src][i] = 1; for(i = 1; i <= N; i++) C[F+i][F+N+i] = 1; for(i = 1; i <= D; i++) C[F+2*N+i][dest] = 1; flow = 0; while( bfs() ) flow++; printf("%d\n", flow); } int main(void) { freopen("dining.in", "rt", stdin); freopen("dining.out", "wt", stdout); read_and_solve(); return 0; }

dining – ლევან გოდერძიშვილის თარგმანი

საქმე გვაქვს ქსელის სტანდარტულ ამოცანასთან. განვიხილოთ შემდეგი გრაფი, თავში სასმელები, შუაში ძროხები, ხოლო ბოლოში კერძები. ყველა წიბო ავიღოთ გამტარუნარიანობით 1: სათავე / | \ D1 D2 .. DD / \ / \ / \ / \ / \ (ჩავსვათ წიბო მხოლოდ იმ შემთხვევაში, თუ Ci-ს მოსწონს Dj) C1a C2a .. CNa | | | C1b C2b .. CNb \ / \ / \ / \ / \ / F1 F2 .. FF (ჩავსვათ წიბო მხოლოდ იმ შემთხვევაში, თუ Ci-ს მოსწონს Fj) \ | / ბოლო ყველა გზა სათავიდან ბოლომდე შეესაბამება ძროხას, რომელმაც მიიღო სასურველი საკვები - გამომდინარე იქიდან, რომ თითოეული გზა გაივლის სასმელში, ძროხასა და კერძში. ცხადია, შეუძლებელია რომელიმე სასმელი, ძროხა ან კერძი ეკუთვნოდეს ორ სხვადასხვა გზას, რადგან თითო წიბოს გამტარუნარიანობა 1-ია. აქედან გამომდინარე, ძროხების გამოკვების მაქსიმალური რაოდენობა ტოლია მაქსიმალური სიდიდის ნაკადისა. ქსელის სტრუქტურა რაღაცით გავს ორწილა გრაფს, ასე რომ საწყისი ხარბი გაშვება მოაგვარებს ქსელის უმეტესი ნაწილის საქმეს(ცხადია უნდა გავითვალისწინოთ პრეფერენციები). შემდეგ შეგვიძლია გავუშვათ სტანდარტული ფორდ-ფალკერსონის ალგორითმი რათა მივიღოთ საბოლოო ქსელი და მაქსიმალური ნაკადი. მიუხედავად იმისა, რომ ეს ალგორითმი ასიმპტოტურად ცოტა ნელია O(VE2), ის პრაქტიკაში საკმაოდ სწრაფად ეშვება, იმიტომ რომ ძირითადი სამუშაო უკვე შესრულებულია ხარბი გაშვების მიერ. ზემოთ აღნიშნულიდან გამომდინარე, მაქსიმალური ნაკადის საპოვნელად (რომელიც დადის ორწილა გრაფში მაქსიმალური შეწყვილების პოვნაზე) საკმარისია ფორდ-ფალკერსონის მეთოდის გამოყენება შესაბამის ქსელში. უფრო სწრაფია „წინარენაკადების გაშვების“ ალგორითმი, რომელიც O(V2E) დროში მუშაობს და ასევე მისაღებია, თუმცა ამ შემთხვევაში არ მოგვცემდა დიდ სხვაობას. კიდევ ერთი ალტერნატივა იქნებოდა ჰოპქროპთ-კარპის ალგორითმი, რომელიც უეარეს ემთხვევაში მუშაობს O(|E|√|V|) დროში და ვინაიდან ჩვენ შეწყვილებას ვახდენთ გარკვეული პრეფერენციების მიხედვით, ეს ალგოირითმიც საკმაოდ ეფექტური იქნება. სატესტო მონაცემები: თვდაპირველად 20 ტესტი შემთხვევით დაგენერირებულია, შემდეგ განხილულია ზოგიერთი ‘არასწორი’ ამოხსნა და შესაბამისი ტესტი წაშლილია რათა მოხდეს შემდეგი (ბაგების გაუთვალისწინებლად): მაქსიმალური ნაკადის ამოხსნა გადის 100%-ს ტესტებისა ვარიანტების სრული გადარჩევა გადის 30-40%-ს ტესტებისა რანდომ გამოცნობა გადის 40%-ს ტესტებისა ალგორითმები ფორდ-ფალკერსონი: მას შემდეგ, რაც ხარბი ალგორითმით აგებული გვაქვს საწყისი შეწყვილება, გავაკეთოთ შემდეგი - სანამ ქსელში არსებობს შემავსებელი გზა, ვიპოვოთ ეს გზა, გავზარდოთ ნაკადი. თუკი შემავსებელი გზა აღარ არის, ნაკადი მაქსიმალურია. წინარენაკადები: ამ ალგორითმის იმპლემენტაცია შედარებით რთულია დანარჩენ ორთან შედარებით, ქვემოთ მოცემულია ძირითადი იდეა, რომელზეც ის არის აგებული. ავირჩიოთ აქტიური წვერო i (წვერო აქტიურია თუ ნამატი e(i) > 0) ვცადოთ ნამატის მოშორება ნაკადის გაშვებით დასაშვებ წიბოში თუ აქტიურ წვეროს არ გააჩნია შესაძლო გასაშვები წიბოები, გავზარდოთ მისი დისტანციის ნიშნული შევწყვიტოთ, როცა აქტიური წვეროები აღარ არსებობს ჰოპქროპთ-კარპი: მას შემდეგ, რაც ხარბი ალგორითმით აგებული გვაქვს საწყისი შეწყვილება, გავაკეთოთ შემდეგი - 1) მოვძებნოთ ისეთი გზა ერთი ნაწილიდან მეორეში, რომელიც იწყება და მთავრდება თავისუფალი წვეროთი, ხოლო ამ გზაზე შეწყვილებაში შემავალი და თავისუფალი წიბოები მონაცვლეობენ. 2) ნაპოვნ გზაზე ყველა წიბოს შეფერილობა შევუცვალოთ საწინააღმდეგოთი: შეწყვილებაში შემავალი ყველა წიბო გავხადოთ თავისუფალი, ხოლო თავისუფალი წიბოები შეწყვილებაში შევიყვანოთ. 3) ვიდრე ასეთი გზა მოიძებნება, ყველაფერი გავიმეოროთ თავიდან.

Airinei Adrian-ის ამოხსნა:

#include <stdio.h>
#include <string.h>
#define MAXN 512 
int N, F, D;
int src, dest, Q[MAXN], viz[MAXN], from[MAXN];
char C[MAXN][MAXN];  

int bfs(void) {
	int inc, sf, x, i, ok = 1;	
	memset(viz, 0, sizeof(viz));	//ანულებს ნამყოფებს
	Q[inc = sf = 0] = src, viz[src] = 1, from[src] = -1;  
	while(inc <= sf && ok)
	{ 
		x = Q[inc++]; 
		for(i = src; i <= dest; i++) 
			if(!viz[i] && C[x][i] > 0)	//თუ უკვე ნამყოფი არ არის და შედის მის პრეფერენციებში
			{ 
				viz[i] = 1, Q[++sf] = i, from[i] = x; 
				if(i == dest) 	//ესეიგი უკვე ქსელის ბოლოში ვართ
				{ 
					x = dest, ok = 0;
					break ; 
				} 
			} 
	}  
	if(x != dest) return 0;  
	while(from[x] > -1)	//ათავისუფლებს წინა წვეროს და ბლოკავს ახალს
		C[from[x]][x]--, C[x][from[x]]++, x = from[x];
	
	return 1; 
}  
void read_and_solve(void) 
{ 
	int i, j, k, nrf, nrd, a, b, flow;  
	scanf("%d %d %d\n", &N, &F, &D);  
	src = 0;	//სათავე
	dest = F+2*N+D+1;	//ბოლო
	for(i = 1; i <= N; i++) 
	{ 
		scanf("%d %d ", &nrf, &nrd); 
		for(k = 1; k <= nrf; k++) 
			scanf("%d ", &j), C[j][i+F] = 1; 
		for(k = 1; k <= nrd; k++) 
			scanf("%d ", &j), C[F+N+i][F+2*N+j] = 1; 
	}  
	for(i = 1; i <= F; i++) 
		C[src][i] = 1; 
	for(i = 1; i <= N; i++) 
		C[F+i][F+N+i] = 1; 
	for(i = 1; i <= D; i++) 
		C[F+2*N+i][dest] = 1;	//ავსებს პრეფერენციების ცხრილს
	
	flow = 0; 
	while( bfs() )	//bfs-ის საშუალებით აკეთებს ფორდ-ფალკერსონის ალგორითმს
		flow++;  
	printf("%d\n", flow); 
}  

int main(void) { 
	freopen("dining.in", "rt", stdin); 
	freopen("dining.out", "wt", stdout); 
	read_and_solve(); 
	return 0; 
}