Det är både lätt och elegant att göra
om problemet till en flödesgraf. Jag beskriver här en metod:
Börja med en startnod s varifrån det utgår tre bågar,
vardera med kapaciteten N / 3 avrundat uppåt, till noderna
K, M och S. Skapa sedan en nod för varje person och dra en båge
från K till varje kvinnlig forskare, från M till varje manlig
forskare och från S till varje studierektor. Skapa sedan en nod för
varje institution och dra en båge från en person till en institution
om personen arbetar där. Skapa till sist en slutnod t och dra en båge
från varje institution till t. Låt alla kapaciteter utom s-K,
s-M och s-S vara 1 och kör maxflödesalgoritmen (gärna förenklad
eftersom grafen är så regelbunden och w alltid är 1). Om
flödet = N så är det möjligt, annars omöjligt.
Tillbaka