h1. USACO nov 2005, divizia GOLD

(Creat de ==user(user="DITzoneC" type="tiny")== la data de _2005-11-21_ categoria _Competitii_, autor(i) _Adrian Diaconu_)

(Categoria _Competitii_, autor(i) _Adrian Diaconu_)

Etapa din noiembria a fost una destul de usoara cu $17$ punctaje maxime printre care si $3$ romani:

"Teste si enunturile":http://www.infoarena.ro/downloads?action=download&file=usaco_nov05.zip problemelor sunt disponibile in sectiunea Download.

==Include(page="template/raw")==
 

h2. Asteroids
Vom rezolva aceasta problema folosind un algoritm de cuplaj maxim. Se va construi un graf bipartit in care vom avea pe o parte coloanele matricii ({$1..n$}) pe cealalta liniile matricii ({$1..m$}). Vom avea muchie de la o linie la o coloana daca in pozitia respectiva se afla un bolovan ce trebuie distrus. Graful astfel construit va avea $n+m$ noduri si $k$ muchii (locurile unde sunt plasati bolovanii). Problema se reduce astfel la determinarea unui suport minim pe un graf bipartit care este echivalenta cu gasirea cuplajului maxim pe acest graf. Suportul minim inseamna o multime de noduri de cardinal minim astfel incat fiecare muchie are cel putin un capat in multime.