Solution to UVa 10462

second.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <utility>
#include <algorithm>
#include <climits>
using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); ++i)
#define forsn(i, s, n) for(int i=(s); i<(int)(n); ++i)
#define forall(it, X) for(typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)
#define all(X) (X).begin(), (X).end()
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int,int> pii;

struct UnionFind {
	vint boss, rank;
	UnionFind(int n) : boss(n), rank(n,0) {
		forn(i,n) boss[i]=i;
	}
	int root(int u) {
		if(u != boss[u])
			boss[u] = root(boss[u]);
		return boss[u];
	}
	bool join(int u, int v) {
		int a=root(u), b=root(v);
		if(a == b) return false;
		if(rank[a] > rank[b])
			boss[a] = b;
		else if(rank[a] < rank[b])
			boss[b] = a;
		else {
			boss[b] = a;
			rank[a]++;
		}
		return true;
	}
};
struct Edge {
	int u,v,w;
	bool operator<(const Edge& e) const {
		return w < e.w;
	}
};
int kruskal(int n, vector<Edge>& E, vector<list<pii> >& ady) {
	sort(all(E));
	UnionFind B(n);
	int totalw=0, num=0;
	vector<Edge>::iterator it = E.begin();
	while(num < n-1 && it != E.end()) {
		if(B.join(it->u,it->v)) {
			totalw += it->w;
			num++;
			ady[it->u].push_back(pii(it->v,it->w));
			ady[it->v].push_back(pii(it->u,it->w));
			it = E.erase(it);
		} else
			++it;
	}
	return (num==n-1) ? totalw : INT_MAX;
}

int main() {
	int T;
	cin >> T;
	forn(t,T) {
		int n,m;
		cin >> n >> m;
		vector<Edge> ejes;
		forn(i,m) {
			int u, v, w;
			cin >> u >> v >> w;
			u--; v--;
			Edge e = {u,v,w};
			ejes.push_back(e);
		}

		vector<list<pii> > ady(n);
		int totalw = kruskal(n,ejes,ady);
		cout << "Case #" << t+1 << " : ";
		if(totalw == INT_MAX) {
			cout << "No way" << endl;
			continue;
		} else if(n == m+1) {
			cout << "No second way" << endl;
			continue;
		}

		// maxw[u][v] = eje de max peso en el camino entre u y v (en T).
		vvint maxw(n, vint(n,INT_MIN));
		forn(u,n) {
			queue<int> Q;
			Q.push(u);
			while(!Q.empty()) {
				int x = Q.front(); Q.pop();
				forall(it,ady[x]) {
					int v = it->first;
					if(maxw[u][v]==INT_MIN && v!=u) {
						maxw[u][v] = max(it->second, maxw[u][x]);
						Q.push(v);
					}
				}
			}
		}
		// find (u,v)\notin T that minimizes w(u,v) - maxw[u,v]
		// return T - maxw[u,v] + (u,v)
		int minw = INT_MAX;
		forall(it,ejes) {
			minw = min(minw, it->w - maxw[it->u][it->v]);
		}
		cout << totalw + minw << endl;
	}
	return 0;
}