spider.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
// #define INF (int)2e9
#define EPS 1e-9
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
#define MAXN 2100
#define MAXM 1100000
#define LOGMAXN 20
struct Vrchol{
Vrchol* parent;
int rank;
};
struct Hrana{
int z, d, cena;
bool operator<(const Hrana&h)const{
return cena<h.cena;
}
};
Vrchol* root(Vrchol*v){
Vrchol* r = v;
while(r->parent!=0)
r = r->parent;
while(v!=r){
Vrchol*n=v->parent;
v->parent = r;
v = n;
}
return r;
}
bool join(Vrchol* a, Vrchol* b){
a=root(a);
b=root(b);
if(a==b)
return false;
else{
if(a->rank>b->rank)
b->parent=a;
else if(a->rank<b->rank)
a->parent = b;
else
b->parent = a, a->rank++;
}
return true;
}
int N, M;
vector<int> tree[MAXN];
vector<int> ceny[MAXN];
int sum;
int nejd;
int T[MAXN];
int L[MAXN];
int P[MAXN][LOGMAXN];
int E[MAXN];
int H[MAXN][LOGMAXN];
int X;
void dfs(int v, int p, int e, int l) {
T[v] = p;
L[v] = l;
E[v] = e;
FOR (i, 0, tree[v].size()) {
if (tree[v][i]!=p)
dfs(tree[v][i], v, ceny[v][i], l+1);
}
}
void process() {
int i, j;
for (i=0; i<N; i++)
for (j=0; 1<<j<N; j++) {
P[i][j] = -1;
H[i][j] = 0;
}
for (i=0; i<N; i++) {
P[i][0] = T[i];
H[i][0] = E[i];
}
for (j=1; 1<<j < N; j++)
for (i=0; i<N; i++)
if (P[i][j-1]!=-1) {
P[i][j] = P[P[i][j-1]][j-1];
H[i][j] = max(H[i][j-1], H[P[i][j-1]][j-1]);
}
}
int query(int p, int q) {
int lo, i;
int ret = 0;
if (L[p] < L[q]) {
swap(p, q);
}
for (lo=1; 1<<lo <=L[p]; lo++);
lo--;
for (i=lo; i>=0; i--)
if (L[p] - (1<<i) >=L[q]) {
ret = H[p][i];
p = P[p][i];
}
if (p==q)
return ret;
for (i=lo; i>=0; i--)
if (P[p][i] != -1 && P[p][i] != P[q][i]) {
ret = max(ret, H[p][i]);
ret = max(ret, H[q][i]);
p = P[p][i];
q = P[q][i];
}
return max(ret, max(E[p], E[q]));
}
Hrana hrany[MAXM];
Vrchol vrcholy[MAXN];
bool solve() {
X=0;
if (scanf("%d%d",&N,&M)<0) return false;
for(int i=0;i<N;++i){
vrcholy[i].rank= 0;
vrcholy[i].parent= 0;
}
for(int i=0;i<M;++i){
scanf("%d%d%d",&hrany[i].z,&hrany[i].d,&hrany[i].cena);
hrany[i].z--, hrany[i].d--;
}
sort(hrany, hrany+M);
sum = 0;
nejd = 0;
for(int i=0;i<M;++i){
if(join(vrcholy+hrany[i].z, vrcholy+hrany[i].d)){
tree[hrany[i].z].push_back(hrany[i].d);
ceny[hrany[i].z].push_back(hrany[i].cena);
tree[hrany[i].d].push_back(hrany[i].z);
ceny[hrany[i].d].push_back(hrany[i].cena);
sum+=hrany[i].cena;
nejd = max(nejd, hrany[i].cena);
X++;
}
}
if (X<N-1) {
printf("disconnected\n");
return true;
}
dfs(0, -1, 0, 0);
process();
int ret = INT_MAX;
FOR (i, 0, M) {
ret = min(ret, sum-query(hrany[i].z, hrany[i].d)-hrany[i].cena);
}
printf("%d\n", ret);
return true;
}
int main() {
while(solve());
return 0;
}