spider.cpp
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;
struct edge {
int x, y, w;
edge() {}
edge(int x, int y, int w) : x(x), y(y), w(w) {}
bool operator < (const edge &e) const {
return w < e.w;
}
};
vector<int> parent;
void init(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int i) {
if (parent[i] == i) return i;
parent[i] = find(parent[i]);
return parent[i];
}
void merge(int i, int j) {
parent[find(i)] = find(j);
}
edge kruskal(vector<edge> &g, vector<vector<pair<int, int> > > &tree, int n, bool &connected) {
init(n);
tree.assign(n, vector<pair<int, int> > ());
sort(g.begin(), g.end());
edge emax(-1, -1, 0);
int cnt = 0;
for(int i = 0; i < (int) g.size(); ++i) {
if (find(g[i].x) != find(g[i].y)) {
merge(g[i].x, g[i].y);
tree[g[i].x].push_back(make_pair(g[i].y, g[i].w));
tree[g[i].y].push_back(make_pair(g[i].x, g[i].w));
++cnt;
} else
emax = g[i];
}
connected = (cnt == n - 1);
return emax;
}
int bfs(vector<vector<pair<int, int> > > &t, int u, int v) {
vector<bool> mark(t.size(), false);
queue<pair<int, int> > q;
q.push(make_pair(u, 0));
mark[u] = true;
while(not q.empty()) {
int x = q.front().first;
int l = q.front().second;
q.pop();
//printf("%d %d\n", x, l); fflush(stdout);
if (x == v) return l;
for (int i = 0; i < (int) t[x].size(); ++i) {
int y = t[x][i].first;
if (not mark[y]) {
mark[y] = true;
int nl = max(l, t[x][i].second);
q.push(make_pair(y, nl));
}
}
}
return -1;
}
int sum(vector<vector<pair<int, int> > > &t) {
int s = 0;
for (int x = 0; x < (int) t.size(); ++x)
for (int i = 0; i < (int) t[x].size(); ++i) {
s += t[x][i].second;
//printf("%d %d %d\n", x, t[x][i].first, t[x][i].second);
}
return s / 2;
}
int main() {
int n, m;
while(scanf("%d %d", &n, &m) == 2) {
vector<edge> g;
vector<vector<pair<int, int> > > t;
for (int i = 0; i < m; ++i) {
int u,v,l;
scanf("%d %d %d", &u, &v, &l);
--u; --v;
g.push_back(edge(u, v, l));
}
bool connected = true;
edge e = kruskal(g, t, n, connected);
int cost = sum(t) - e.w;
if (e.x < 0)
cost -= e.w;
else
cost -= bfs(t, e.x, e.y);
if (not connected)
printf("disconnected\n");
else
printf("%d\n", cost);
}
}