Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- ifstream f("zapada.in");
- ofstream g("zapada.out");
- const int NMax=105;
- const int MMax=100000;
- int n, m;
- int numar_arbore[NMax];
- int cost_total;
- int k;
- struct muchie
- {
- int nod1, nod2;
- int cost;
- }v[MMax];
- void citire()
- {
- f>>n>>m;
- for(int i=1; i<=m; i++)
- f>>v[i].nod1>>v[i].nod2>>v[i].cost;
- int drumuri, poz;
- f>>drumuri;
- for(int i=1; i<=drumuri; i++)
- {
- f>>poz;
- muchie aux=v[++k];
- v[k]=v[poz];
- v[poz]=aux;
- }
- }
- void sortare(int pozitie)
- {
- int ok;
- do
- {
- ok=1;
- for(int i=pozitie; i<m; i++)
- {
- int c1=v[i].cost;
- int c2=v[i+1].cost;
- if(c1>c2)
- {
- ok=0;
- muchie aux=v[i];
- v[i]=v[i+1];
- v[i+1]=aux;
- }
- }
- }while(ok==0);
- }
- void schimbare_numar_arbore(int a, int b)
- {
- for(int i=1; i<=n; i++)
- if(numar_arbore[i]==b)
- numar_arbore[i]=a;
- }
- void Kruskal()
- {
- sortare(k+1);
- for(int i=1; i<=n; i++)
- numar_arbore[i]=i;
- for(int i=1; i<=n; i++)
- {
- int nod1=v[i].nod1;
- int nod2=v[i].nod2;
- if(numar_arbore[nod1]!=numar_arbore[nod2])
- {
- cost_total+=v[i].cost;
- schimbare_numar_arbore(numar_arbore[nod1], numar_arbore[nod2]);
- }
- }
- }
- int main()
- {
- citire();
- Kruskal();
- g<<cost_total;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement