Problemy z algorytmem podobne jak w 'problem liszaja’ [ https://www.youtube.com/watch?v=4pdBHJYf3Hw ] – setki rozwiązań w internecie. Tylko, że na ASD zamiast tablicy 2-wymiarowej mamy graf.
Chodzi o to, że mamy jakieś wierzchołki grafu 'zarażone’ [założone sztaby wyborcze] i one zarażają te z którymi mają kontakt [miasta sąsiedzkie]. Jednak, żeby nie było za łatwo, wszystko trzeba podzielić na tury. Wierzchołki zarażone w danej turze zaczynają zarażać dopiero w następnej. Jak już się zrozumie o co chodzi to napisanie programu jest bardzo proste.
Jeśli uda mi się na jutro dokończyć artykuł o list/vector/map w C++ to wrzucę, żeby trochę rozjaśnić temat dlaczego korzystam z tylu 'map’ i jakie cudowne właściwości one mają.
Jednak dla osób które mają problem udostępniam pseudokod/trochę jak C++. Do niedzieli, do północy, jest jeszcze czas na przerobienie tego na działający program.
Jeśli kod poniżej jest kiepsko wyświetlany, to można też go obejrzeć na pełnej szerokości okna z kolorowaniem składni [głównie komentarzy]:
http://hastebin.com/kodekiwita.php
klasa Kandydat
{
- id
- koszt kampanii metoda A
- koszt kampanii metoda B
};
klasa Miasto
{
- id
- zwyciezca metoda A
- zwyciezca metoda B
- lista sasiadow
};
funckja wczytajLiczbe()
{
// wczytuje liczbe z wejscia do zmiennej
}
int main()
{
// 1. tworzymy liste/tablice zawierajaca wszystkie miasta
var iloscMiast;
wczytajLiczbe >> iloscMiast;
// musi byc mozliwosc latwego zaladowania miasta o numerze X
var listaMiast = (lista miast o wielkosci 'iloscMiast');
for(i < iloscMiast, i++)
{
// dodajemy do listy miasta, zapamietujac w miastach ich ID
listaMiast[i] = new Miasto(i);
}
// 2. wczytujemy sasiadow miast
var sasiad_1;
var sasiad_2;
wczytajLiczbe >> sasiad_1;
wczytajLiczbe >> sasiad_2;
// do czasu az wystapi koniec listy sasiadow
while(sasiad_1 != -1)
{
// oba miasta sasiedzkie musza miec dodane siebie nawzajem do list sasiadow
listaMiast[sasiad_1]->lista_sasiadow->dodaj(sasiad_2);
listaMiast[sasiad_2]->lista_sasiadow->dodaj(sasiad_1);
wczytajLiczbe >> sasiad_1;
wczytajLiczbe >> sasiad_2;
}
// 3. tworzymy liste/tablice kandydatow od razu wczytujac ich startowe miasto
var iloscKandydatow;
wczytajLiczbe >> iloscKandydatow;
// musi byc mozliwosc latwego zaladowania kandydata o numerze X
var listaKandydatow = (lista kandydatow o wielkosci 'iloscKandydatow');
map<Miasto*, char> listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda; // bez powtorzen = 'map', klucz musi byc unikalny, a wartosc moze byc dowolna
for(i < iloscKandydatow, i++)
{
var miastoStartoweKandydata;
wczytajLiczbe >> miastoStartoweKandydata;
for(sasiad in listaMiast[miastoStartoweKandydata])
{
// przeprowadz wybory u kazdego sasiada startowego miasta
listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda[miastoStartoweKandydata] = ' ';
}
// dodajemy do listy kandydatow, zapamietujac w kandydatach ich ID
listaKandydatow[i] = new Kandydat(i);
// w miescie startowym zapamietujemy kto jest zwyciezca
listaMiast[miastoStartoweKandydata]->zwyciezcaKampaniiMetodaA = listaKandydatow[i];
listaMiast[miastoStartoweKandydata]->zwyciezcaKampaniiMetodaB = listaKandydatow[i];
// w kandydacie zapisujemy zmiane kosztu kampanii, zalozenie sztabu w startowym miescie
listaKandydatow[i]->kosztKampaniiMetodaA++;
listaKandydatow[i]->kosztKampaniiMetodaB++;
}
// 4. tworzymy 'mapy' do przechowywania wielu danych
// tak samo jak 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda', lista bez powtorzen miast do przeprowadzenia wyborow
map<Miasto*, char> listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda;
// dla kazdego miasta bedziemy potrzebowac tymczasowa liste kandydatow na zwyciezce i ilosc glosow na nich oddanych [przez sasiednie miasta]
map<Kandydat*, short int> glosyNaKandydataMetodaA;
map<Kandydat*, short int> glosyNaKandydataMetodaB;
// zwyciezcow wyborow mozemy zapisac dopiero po przeprowadzeniu wszystkich glosowan w 'danej rundzie'
// inaczej glosowania z danej rundy mogly by wplywac na wyniki glosowan w tej samej rundzie
map<Miasto*, Kandydat*> zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA;
map<Miasto*, Kandydat*> zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB;
// 5. mielimy dane (przegladamy graf)
while(nie pusta 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda')
{
// przepisujemy miasta z 'nastepnej rundy' do 'aktualnej rundy'
wyczysc 'listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda';
listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda = listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda;
wyczysc 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda';
// przeprowadzamy wybory w kazdym
for(miasto in listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda)
{
// sprawdzamy czy w miescie nie ma jeszcze zwyciezcy
// po poczatkowym dodawaniu kandydatow do miast startowych na liscie moga byc miasta w ktorych juz sa zwyciezcy
if(czy nie ma zwyciezcy w 'miasto')
{
// czyscimy glosy oddane przy poprzednim liczeniu
wyczysc 'glosyNaKandydataMetodaA';
wyczysc 'glosyNaKandydataMetodaB';
// dla kazdego miasta w sasiedztwie
for(miastoSasiedzkie in miasto->lista_sasiadow)
{
if(czy jest zwyciezca w 'miastoSasiedzkie')
{
// jesli jest zwyciezca to oddaje on glosy metoda A i B
// korzystamy z 'magicznej' wlasciwosci 'map',
// operator ++: dla elementu ktory nie istnieje w mapie ustawia jego wartosc na 1 (startowa wartosc int to 0)
// a dla elementu ktory juz jest w mapie zwieksza wartosc powiazanego 'inta'
// nie musimy sie martwic o to czy cos jest w mapie itp., wszystko dziala tak jak bysmy chcieli
// glos metoda A oddaje zwyciezca metoda A
glosyNaKandydataMetodaA[miastoSasiedzkie->zwyciezcaKampaniiMetodaA]++;
// glos metoda B oddaje zwyciezca metoda B
glosyNaKandydataMetodaB[miastoSasiedzkie->zwyciezcaKampaniiMetodaB]++;
}
else
{
// jesli w miescie nie ma zwyciezcy to znaczy, ze w nastepnej rundzie nalezy w tym miescie przeprowadzic wybory
listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda[miastoSasiedzkie] = ' ';
}
}
// glosy przez wszystkich sasiadow zostaly oddane, teraz trzeba ustalic ktory kandydat wygral metoda A i B
// Metoda A: kandydat ma miec najmniej glosow, a dla tych o takiej samej ilosci glosow wybieramy tego z wyzszym ID
int minimalnaIloscGlosow = 100000; // ustawiamy jakas wartosc wieksza, niz maksymalna ilosc glosow [ilosc miast]
Kandydat* zwyciezajacyKandydatMetodaA;
for(map<Kandydat*, short int>::iterator it in glosyNaKandydataMetodaA)
{
if(it->second < minimalnaIloscGlosow ||
(it->second == minimalnaIloscGlosow && it->first->id > zwyciezajacyKandydatMetodaA->id))
{
zwyciezajacyKandydatMetodaA = it->first;
minimalnaIloscGlosow = it->second;
}
}
// zapamietujemy kto wygral, ale nie zapisujemy w miescie, to zrobimy po zakonczeniu wyborow we wszystkich miastach w tej rundzie
zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA[miasto] = zwyciezajacyKandydatMetodaA;
// zwiekszamy koszt kampanii metoda A
zwyciezajacyKandydatMetodaA->kosztKampaniiMetodaA++;
// Metoda B: kandydat ma miec najwiecej glosow, a dla tych o takiej samej ilosci glosow wybieramy tego z nizszym ID
int maksymalnaIloscGlosow = 0;
Kandydat* zwyciezajacyKandydatMetodaB;
for(map<Kandydat*, short int>::iterator it in glosyNaKandydataMetodaB)
{
if(it->second > maksymalnaIloscGlosow ||
(it->second == maksymalnaIloscGlosow && it->first->id < zwyciezajacyKandydatMetodaB->id))
{
zwyciezajacyKandydatMetodaB = it->first;
maksymalnaIloscGlosow = it->second;
}
}
// zapamietujemy kto wygral, ale nie zapisujemy w miescie, to zrobimy po zakonczeniu wyborow we wszystkich miastach w tej rundzie
zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB[miasto] = zwyciezajacyKandydatMetodaB;
// zwiekszamy koszt kampanii metoda B
zwyciezajacyKandydatMetodaB->kosztKampaniiMetodaB++;
}
}
// skonczyly sie wybory tej rundy, pora przypisac zwyciezcow do miast
for(map<Miasto*, Kandydat*>::iterator it in zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA)
{
// metoda A
it->first->zwyciezcaKampaniiMetodaA = it->second;
}
for(map<Miasto*, Kandydat*>::iterator it in zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB)
{
// metoda B
it->first->zwyciezcaKampaniiMetodaB = it->second;
}
wyczysc 'zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA';
wyczysc 'zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB';
// mozna zaczac kolejna ture wyborow
}
// wszystkie wybory sie skonczyly, pora wypisac koszty kampanii
for(i < iloscKandydatow, i++)
{
wyswietl << listaKandydatow[i]->kosztKampaniiMetodaA;
wyswietl << "spacja";
wyswietl << listaKandydatow[i]->kosztKampaniiMetodaB;
wyswietl << "znak nowej linii :) ";
}
}