Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits//stdc++.h>
- using namespace std;
- const int inf = 16843009;
- int par[1005], taken[1005], idx;
- struct edge
- {
- int u, v, w;
- edge(int u, int v, int w): u(u), v(v), w(w) {}
- bool operator<(const edge &p)const
- {
- return w<p.w;
- }
- };
- void makeset(int n)
- {
- for(int i = 0; i <n; i++) par[i] = i;
- }
- int find_par(int n)
- {
- if (par[n]==n) return n;
- par[n]=find_par(par[n]);
- return par[n];
- }
- vector<edge> E;
- int kruskal(int n)
- {
- sort(E.begin(), E.end());
- makeset(n);
- int sum = 0;
- idx = 0;
- for(int i = 0; i < E.size(); i++)
- {
- int u = find_par(E[i].u);
- int v = find_par(E[i].v);
- if(u != v)
- {
- par[u] = v;
- taken[idx++] = i;
- sum += E[i].w;
- if(idx == n-1) break;
- }
- }
- return sum;
- }
- int main()
- {
- int n, m, u, v, w, mini, cnt, sum;
- cin>>n>>m;
- E.clear();
- memset(taken, 0, sizeof(taken));
- for(int i = 0; i < m; i++)
- {
- cin>>u>>v>>w;
- E.push_back(edge(u, v, w));
- }
- int res = kruskal(n);
- mini = inf;
- for(int j=0; j<idx; j++)
- {
- makeset(n);
- cnt=0;
- sum=0;
- for(int i = 0; i < E.size(); i++)
- {
- if(taken[j] != i)
- {
- int u = find_par(E[i].u);
- int v = find_par(E[i].v);
- if(u!=v)
- {
- par[u] = v;
- cnt++;
- sum += E[i].w;
- if(cnt==n-1) break;
- }
- }
- }
- if(cnt == n-1) mini = min(mini, sum);
- }
- if(mini == inf) puts("No Second Best MST");
- else printf("%d\n", mini);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement