Cerința

Orașul Kruskal are n intersecții unite prin m străzi bidirecționale. Datorită ninsorii de peste noapte, străzile sunt acoperite cu zăpadă. Administratorul orașului, Gigel, a determinat cu mari eforturi pentru fiecare stradă costul deszăpezirii ei și acum dorește deszăpezirea unor străzi astfel încât costul total al deszăpezirii lor să fie minim, și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Maleficul Costel îl forțează pe Gigel să deszăpezească anumite străzi, din motive doar de el știute. Ajutați-l pe Gigel să determine costul minim pentru deszăpezirea orașului, astfel încât să fie deszăpezite străzile dorite de Costel și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Date de intrare

Fișierul de intrare zapada.in conține pe prima linie numerele n m, iar pe următoarele m linii câte un triplet i j c, cu semnificația: există stradă între intersecțiile i j și are costul deszăpezirii egal cu c. Urmează o linie care conține numărul k de străzi pe care Costel le dorește deszăpezite, iar următoarea linie conține k numere distincte între 1 și m, reprezentând numărul de ordine al străzilor care vor fi obligatoriu deszăpezite.

Date de ieșire

Fișierul de ieșire zapada.out va conține pe prima linie costul total minim al deszăpezirii orașului, în condițiile precizate.

Restricții și precizări

1 ≤ n ≤ 100
1 ≤ k < m ≤ n*(n-1)/2
costurile deszăpezirii străzilor sunt numere naturale nenule cel mult egale cu 1000
numerele celor k străzi care trebuie deszăpezite sunt dintre numerele de ordine ale celor m străzi date

Exemplu

zapada.in

zapada.out

Explicație

Alături de străzile 1-7 și 6-7 care trebuie obligatoriu deszăpezite, se mai deszăpezesc străzile: 1-2, 2-5, 4-5 și 3-4. Costul total al deszăpezirii acestor străzi este 4+5+2+2+1+1=15

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Zapada:

#include <iostream>
#include <fstream>
#define INFINIT 1000000000
using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

struct muchie{
    int obl , i , j , cost;
};

int n , m , t[105];

muchie x[5000];

int main()
{
    fin >> n >> m;
    
    for(int i = 0 ; i < m ; ++i)
        fin >> x[i].i >> x[i].j >> x[i].cost;
    int k;
    fin >> k;
    for( ; k ; --k)
    {
        int i;
        fin >> i;
        x[i - 1].obl = 1;
    }
    for(int i = 0 ; i < m - 1; i ++)
        for(int j = i + 1 ; j < m ; ++j)
            if(x[i].obl < x[j].obl)
            {
                muchie aux = x[i];
                x[i] = x[j];
                x[j] = aux;
            }
            else
                if(x[i].obl == x[j].obl)
                    if(x[i].cost > x[j].cost)
                    {
                        muchie aux = x[i];
                        x[i] = x[j];
                        x[j] = aux;
                    }
    for(int i =1 ; i <= n ; ++i)
        t[i] = i;
    int S = 0;
        
    for(int i = 0 ; i < m ; i ++)
        if(x[i].obl == 1 || t[x[i].i] != t[x[i].j])
        {
            S += x[i].cost;
            if(t[x[i].i] != t[x[i].j])
            {
                int ai = t[x[i].i], aj = t[x[i].j];
                for(int j =1 ; j <= n ; ++j)
                    if(t[j] == aj)
                        t[j] = ai;
            }
        }
    fout << S << "
";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #616 Zapada

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #616 Zapada de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #616 Zapada