Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 1 KB
using System;
namespace Kruskal
{
struct El : IComparable
{
public int Csucs1, Csucs2, Suly;
public int CompareTo(object obj)
{
return Suly - ((El) obj).Suly;
}
}
class Program
{
const string InputFile = "halozat1.be",
OutputFile = "halozat1.ki";
int csucsokSzama, elekSzama;
int osszSuly = 0;
El[] elek;
int[] szulo;
private void Beolvas()
{
System.IO.StreamReader sr = new System.IO.StreamReader(InputFile);
string[] sor;
csucsokSzama = int.Parse(sr.ReadLine());
elekSzama = csucsokSzama * (csucsokSzama - 1) / 2;
elek = new El[elekSzama];
szulo = new int[csucsokSzama];
for (int i = 0; i < elekSzama; i++) {
sor = sr.ReadLine().Split();
elek[i].Csucs1 = int.Parse(sor[0]) - 1;
elek[i].Csucs2 = int.Parse(sor[1]) - 1;
elek[i].Suly = int.Parse(sor[2]);
}
sr.Close();
}
private void Rendez()
{
Array.Sort(elek);
}
private int Os(int csucs)
{
while (szulo[csucs] != csucs)
csucs = szulo[csucs];
return csucs;
}
private bool VanUt(int csucs1, int csucs2)
{
return Os(csucs1) == Os(csucs2);
}
private void Felvesz(El el)
{
szulo[Os(el.Csucs1)] = Os(el.Csucs2);
}
private void FatKeszit()
{
int felvettDb = 0;
for (int i = 0; i < csucsokSzama; i++)
szulo[i] = i;
for (int i = 0; i < elekSzama && felvettDb < csucsokSzama - 1; i++)
if (!VanUt(elek[i].Csucs1, elek[i].Csucs2)) {
osszSuly += elek[i].Suly;
felvettDb++;
Felvesz(elek[i]);
}
}
private void Kiir()
{
System.IO.StreamWriter sw = new System.IO.StreamWriter(OutputFile);
sw.WriteLine(osszSuly);
sw.Close();
}
private void Indit()
{
Beolvas();
Rendez();
FatKeszit();
Kiir();
}
public static void Main(string[] args)
{
Program program = new Program();
program.Indit();
}
}
}
