Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SPIN_PL - Minimalne drzewo spinające

Dla podanego grafu G znajdź jego drzewo spinające o minimalnej sumie wag.

Wejście

Pierwsza linia zawiera liczbę całkowitą określającą liczbę przypadków testowych. Każdy przypadek testowy to jeden graf, który jest opisany w dwóch kolejnych liniach. Pierwsza linia jest postaci n=x,m=y gdzie x i y są liczbami określającymi liczbę wierzchołków i krawędzi grafu. Druga linia opisująca graf zawiera listę krawędzi oddzielonych spacjami. Każda krawędź jest postaci {u,v}w gdzie u,v to wierzchołki należące do krawędzi, natomiast w jest liczbą całkowitą będącą wagą krawędzi. Wierzchołki numerujemy liczbami 0,...,n-1.

Wyjście

Dla każdego przypadku testowego należy w osobnej linii wypisać liczbę będącą sumą wag krawędzi należących do minimalnego drzewa spinającego.

Przykład

Wejście:
2
n=6,m=9
{0,1}1 {0,5}3 {1,2}9 {1,3}7 {1,5}5 {2,3}8 {3,4}5 {3,5}2 {4,5}4
n=7,m=12
{0,1}2 {0,2}1 {0,3}2 {0,4}1 {0,5}2 {0,6}1 {1,2}4 {1,6}4 {2,3}3 {3,4}4 {4,5}6 {5,6}8


Wyjście:
18
9

Uwagi

Szkic algorytmów można znaleźć tutaj

Przykładowe dane testowe


Dodane przez:Darek Dereniowski
Data dodania:2006-04-12
Limit czasu wykonania programu:2.545s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6

ukryj komentarze
2013-06-14 04:07:41 Lupus Nocawy

scanf("%d ", &t);
while(t--){
scanf("n=%d,m=%d ", &n, &m);
for(int i=0; i<m; ++i){
scanf("{%d,%d}%d ", &u, &v, &w);
}
}

Ostatnio edytowany: 2013-06-14 04:53:16
2011-07-30 18:19:51 Piotr KÄ…kol
Nie tylko jedno wejście jest dobre, Twoje może również być ok. Ale jeśli jesteś pewien, że Twój algo jest ok, możesz spróbować mojego:
scanf("%d",&t);
while(t--)
{
  getchar();
  scanf("n=%d,m=%d",&n,&m);
  for(i=0;i<m;++i)
  {
    getchar();
    scanf("{%d,%d}%d",&a,&b,&c);
  }getchar();
}


Ostatnio edytowany: 2011-07-30 18:20:53
2010-08-12 13:13:57 Jakub Stanecki
Warto wspomnieć, że krawędzie są nieskierowane :).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.