记录编号	96866	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.171 s
提交时间	2014-04-15 20:57:22	内存使用	0.37 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 510
#define M 2510
struct treap{
	int ff,tt,ww;
	int l,r;
	int ran;
}t[M];
int n,m;
int f[N];
int root = 0,size = 0;
void right(int &x){
	int tem = t[x].r;
	t[x].r = t[tem].l;
	t[tem].l = x;
	x = tem;
	return;
}
int ans = 0;
void left(int &x){
	int tem = t[x].l;
	t[x].l = t[tem].r;
	t[tem].r = x;
	x = tem;
	return;
}

void insert(int &x,int a,int b,int c){
	if (!x){
		x = ++ size;
		t[x].l = t[x].r = 0;
		t[x].ran = rand() * rand();
		t[x].ff = a;
		t[x].tt = b;
		t[x].ww = c;
		return;
	}
	else{
		if (t[x].ww <= c){
			insert(t[x].r,a,b,c);
			if (t[t[x].r].ran < t[x].ran) right(x);
		}
		else{
			insert(t[x].l,a,b,c);
			if (t[t[x].l].ran < t[x].ran) left(x);
		}
	}
	return;
}
int sum = 0,temp = 0;
int get(int x){
	return f[x] == x?x: f[x] = get(f[x]);
}

void midsearch(int x){
	if (!x) return;
	midsearch(t[x].l);
	int fx = get(t[x].ff);
	int fy = get(t[x].tt);
	if (fx != fy){
		f[fx] = fy;
		sum ++;
		temp += t[x].ww;
	}
	midsearch(t[x].r);
	return;
}

void kruscal(){
	for (int i = 1; i <= n; i++) f[i] = i;
	sum = 0,temp = 0;
	midsearch(root);
	if (sum == n - 1 && ans == 0) ans = temp;
	else
		if (sum == n - 1) ans = min(ans,temp);
}


int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,z;
	for (int i = 1; i <= m; i++){
		scanf("%d%d%d",&x,&y,&z);
		insert(root,x,y,z);
		kruscal();
		if (ans == 0) puts("0");
		else{
			double ss = ans * 0.5;
			printf("%.1lf\n",ss);
		}
	}
	return 0;
}