Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define nax 102
- using namespace std;
- ifstream f("kruskal.in");
- ofstream g("kruskal.out");
- int n, m;
- int L[2*nax];
- vector<int> ans;
- struct muchie
- {
- int x, y, cost;
- }u[2*nax];
- void init()
- {
- int i;
- for(i = 1; i <= n; ++i)
- L[i] = i;
- }
- void Read()
- {
- int x, y, cost, i = 0;
- f >> n >> m;
- while(f >> x >> y >> cost)
- {
- ++i;
- u[i].x = x;
- u[i].y = y;
- u[i].cost = cost;
- }
- sort(u+1, u+1+m, [&](muchie m1, muchie m2){return (m1.cost < m2.cost);});
- }
- int main()
- {
- int i = 1, j, k = 0, x, y, cost = 0;
- Read();
- init();
- // g << "APM este format din muchiile: ";
- while(k < n - 1)
- {
- if(L[u[i].x] != L[u[i].y])
- {
- ++k;
- cost += u[i].cost;
- x = L[u[i].y];
- y = L[u[i].x];
- ans.push_back(u[i].x);
- ans.push_back(u[i].y);
- for(j = 1; j <= n; ++j)
- if(L[j] == x)
- L[j] = y;
- }
- ++i;
- }
- ans.shrink_to_fit();
- g << cost << "\n";
- for(i = 0; i < ans.size()-1; i += 2)
- g << ans[i] << " " << ans[i+1] << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement