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);
	}
}