/* Umut Öztok -19.09.08- Soru: N (2 < N < 5000) adet durak var. Her duraktan metro geçecek şekilde ray döşenecek. Bunun için, en az maliyetle hangi duraklar arasına ray döşenmelidir ? Çözüm: Durakları köşe(node) ve duraklar arasındaki rayları da kenar(edge) olarak kabul edersek, girdiden gelen veriler bir çizge(graph) oluşturur. Bu çizge'den oluşturulacak olan "minimum spanning tree" de sorunun cevabını verir. Bu ağacı verimli bir şekilde oluşturmak için de, Prim ya da Kruskal'ın algoritmaları kullanılabilir. Ben Kruskal'ın algoritmasını uygulayacağım. Kruskal'ın algoritmasına göre, bütün köşeler en başta tek bir ağaç gibi düşünülür. Daha sonra, sırası ile en küçük kenar alınır ve bu kenarı oluşturan köşelerin döngü(cycle) oluşturup oluşturmadığına bakılır. Eğer döngü oluşmuyorsa, o kenar "minimum spanning tree"'de yer alacak demektir. Bu işlem toplam köşe(durak) sayısının bir eksiği kadar kenar bulana kadar devam eder ve sonunda elde edilen ağaç "minimum spanning tree"'dir. Bu algoritmayı uygulayabilmek için, öncelikle toplam kenar sayısı kadar veri tutacak olan bir dizi gereklidir. Dizinin tutacağı veri de, 2 durak ve o duraklar arasına ray döşemenin maliyetidir. Bunu "ray" adlı struct ile tanımlayabiliriz. Girdiden gelen veriler ile vektörü oluşturduktan sonra, vektörü maliyeti en düşük olan ray en başa gelecek şekilde sıralamak gerekir, çünkü bir sonraki aşamada sürekli en düşük maliyetli rayı alıp, döngü oluşturup oluşturmadığını kontrol edeceğiz. Vektörü sıralamak için bir çok farklı algoritma denenebilir; yazımı kolay fakat O(M^2) zaman alan seçmeli sıralama(selection sort), eklemeli sıralama(insertion sort) ya da yazımı biraz daha zahmetli ama O(MlogM) zaman alan çabuk sıralama(quicksort) gibi. Fakat, bunlar yerine hem yazımı kolay hem de O(MlogM) zaman alan bir yöntem kullanacağım. En başta oluşturduğumuz vektörü, bir heap'e çevireceğim, O(M) zamanda. Döngü kontrol sırasında ise, heap'den en düşük maliyetli rayı silip (dizini ilk elemanı) tekrar heap özelliğini sağlar hale getireceğim (yeni en düşük maliyetli rayı en başa koyma), O(MlogM) zamanda. Döngü kontrolü için, küme mantığını kullanacağım. Buna göre, en başta bütün köşeler farklı birer kümede yer alırlar. Seçilen kenarı oluşturan köşeler farklı kümelerde bulunuyorlarsa, döngü oluşturmuyorlardır, dolayısıyla o kenarı ağaca ekleyip, kenarları da aynı kümeye koyarız. Eğer aynı kümede bulunuyorlarsa da, o kenarı eleriz. Bu mantığı uygulayabilmek için, durak(köşe) sayısı kadar tamsayı değeri tutacak olan bir dizi gereklidir. Tabii, burada ufak bir sorun sözkonusu. Duraklar 1,2,3...,N , ya da 0,1,2,3..., N-1 şeklinde adlandırılmazlarsa program çakar. Çünkü küme dizisinin indeksleri duraklara tekabül edecektir.Mesela, 5 numaralı durağın hangi kümede yer aldığına bakmak için küme dizisinin 5.indeksine bakılacaktır. Ancak, dediğim gibi bir adlandırma yapılmazsa, bu mümkün olmayacağından program hata verecektir. Bunu önlemek için bir hash tablosu kullanılabilir, fakat adlandırma sistemi tam olarak belli olmadığından ve durak adları ayrı bir şekilde verilmediğinden ötürü, bu şekilde programı yazmak işi biraz uzatıyor. Problemin de asıl amacı burası olmadığı (tamam tamam zor geldi :) ) için hash tablosu kullanmıyorum. Böylece, küme dizisindeki tüm indeksler en başta -1 olacak. Eksi işareti o indeksteki durağın kök küme, yani kümeyi temsil eden indeks, olduğunu gösteriyor. 1 ise kümenin eleman sayısı oluyor. Kümenin eleman sayısı, kümeler birleştirilirken kullanılıyor. Diyelim 2 küme var, biri 3 elemanlı diğeri 4 elemanlı, bu iki kümeyi birleştirirken, eleman sayısı az olan kümeyi, fazla olan kümeye ekliyoruz. Yani 4 elemanlı kümenin kök kümesi -4'ü gösterirken -7'yi gösteriyor. 3 elemanlı kümenin kök kümesi ise, artık kök küme olmaktan çıkıyor ve eklenmiş olduğu kümenin kök kümesinin indeksini gösteriyor. Sonuç olarak, durak sayısı N ve kenar sayısı K ise, bu program: O(K) (girdiden gelen verileri durak adlı diziye aktarma) + O(K) (durak adlı diziyi heap'e çevirme) + O(KlogK) (Kruskal'ın algoritmasını uygulama, heap'teki en küçük rayı silme) + O(N) (çıktıyı oluşturmak) olmak üzere en kötü durumda O(KlogK) zaman ve alan gerektirmektedir. */ #include #include using namespace std; struct ray { int basla; int bitis; int fiyat; ray(int a, int b, int c): basla(a), bitis(b), fiyat(c) {}; }; void Asagi_In (vector & durak, int indeks) { int adet = durak.size() - 1; int cocuk; ray gecici = durak[indeks]; while(indeks * 2 <= adet) { cocuk = indeks * 2; if(cocuk != adet && durak[cocuk].fiyat > durak[cocuk + 1].fiyat) cocuk++; if(durak[cocuk].fiyat < gecici.fiyat) durak[indeks] = durak[cocuk]; else break; indeks = cocuk; } durak[indeks] = gecici; } ray Kucuk_Sil(vector & durak) { ray kucuk = durak[1]; durak[1] = durak[durak.size() - 1]; Asagi_In(durak, 1); return kucuk; } void Heap (vector & durak) { for(int k = durak.size() / 2; k > 0; k--) Asagi_In(durak, k); } void DosyaOku (vector & durak, vector & kume) { ifstream girdi; girdi.open("metro.gir"); int durak_sayi, satir, basla, bitis, fiyat; girdi >> durak_sayi >> satir; vector a (durak_sayi + 1,-1); kume = a; durak.push_back(ray(-1,-1,-1));//heap'teki işlemleri 1.indeksten itibaren yapabilmek için for(int k = 0; k < satir; k++) { girdi >> basla >> bitis >> fiyat; durak.push_back(ray(basla, bitis, fiyat)); } Heap(durak); } int Bul (int x, const vector & kume) { while(kume[x] > 0) x = kume[x]; return x; } void Birlestir(int kok1, int kok2, vector & kume) { if(kok1 < kok2) { kume[kok1]+= kume[kok2]; kume[kok2] = kok1; } else { kume[kok2]+= kume[kok1]; kume[kok1] = kok2; } } void Coz (vector & durak, vector & kume) { vector cozum; int adet = kume.size(); int kabul = 0; int maliyet = 0; while(kabul < adet - 2) { ray oyle = Kucuk_Sil(durak); int a = Bul(oyle.basla, kume); int b = Bul(oyle.bitis, kume); if(a != b || (a == -1 && b == -1)) { maliyet+= oyle.fiyat; cozum.push_back(oyle); kabul++; Birlestir(a, b, kume); } } ofstream cikti; cikti.open("metro.cik"); cikti << maliyet << endl; for(int k = 0; k < adet - 2; k++) cikti << cozum[k].basla << " " << cozum[k].bitis << endl; } int main () { vector durak; vector kume; DosyaOku (durak, kume); Coz (durak, kume); return 0; }