Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #208 - UPGRANET
Ngày: 21-04-2011
Cập nhật: 21-04-2011
Người gửi: doremon
Ngôn ngữ: C++
Xem: 845

Điểm: 4.2/5 (13 Phiếu)


// Author: Bùi Thị Liên - FPT University
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <utility>
#include <bitset>
//#include <hash_map>
//#include <hash_set>
 
#define MP make_pair
#define F first
#define S second
#define PB push_back
 
template<typename T> T gcd(T a,T b){return (a>b?(gcd(b,a)):(a==0?b:(gcd(b%a,a))));};
template<typename T> inline T sqr(T a){return a*a;};
template<typename T> inline T gmax(T a,T b){return (a>b?a:b);};
template<typename T> inline T gmin(T a,T b){return (a<b?a:b);};
 
using namespace std;
//using namespace __gnu_cxx;
 
const int maxn=100000+5;
const int maxm=100000+5;
const double esp=1e-3;
const int BASE=0;
 
struct edge{
	int u,v,c;
};
struct next{
	int v,c;
};
int i,j;
int n,m;
int base[18];
edge e[maxm];
bool in_use[maxm];
list<next> lis[maxn];
list<next> query[maxn];
long long result;
//
inline bool compare(const edge &a,const edge &b){
	return a.c>b.c;
}
void enter(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
	}
	base[0]=1;
	for (i=1;i<18;i++) base[i]=base[i-1]*2;
}
//
int lab[maxn];
int d[maxn];
bool visited[maxn];
int f[maxn][18];
int dad[maxn][18];
void calculate(int u){
	visited[u]=true;
	//
	for (int i=1;i<18;i++){
		if (base[i]>d[u]) break;
		f[u][i]=gmin(f[u][i-1],f[dad[u][i-1]][i-1]);
		dad[u][i]=dad[dad[u][i-1]][i-1];
	}
	//
	list<next>::iterator it;
	int v;
	for (it=lis[u].begin();it!=lis[u].end();it++){
		v=it->v;
		if (visited[v]) continue;
		d[v]=d[u]+1;
		dad[v][0]=u;
		f[v][0]=it->c;
		calculate(v);
	}
}
inline void connect(int u,int v){
	if (lab[u]<lab[v]){
		lab[u]+=lab[v];
		lab[v]=u;
	}else{
		lab[v]+=lab[u];
		lab[u]=v;
	}
}
inline void combine(int u,int v){
	if (u==v) return;
	lab[u]+=lab[v];
	lab[v]=u;
}
int trace(int u){
	if (lab[u]<0) return u;
	lab[u]=trace(lab[u]);return lab[u];
}
inline next make_next(int &v,int &c){
	next temp;
	temp.v=v;temp.c=c;
	return temp;
}
void init(){
	sort(e+1,e+1+m,compare);
	memset(lab,255,sizeof(lab));
	int count_e=0;
	int u,v;
	for (int i=1;i<=m;i++){
		if (count_e==n-1) break;
		u=trace(e[i].u);v=trace(e[i].v);
		if (u==v) continue;
		count_e++;
		in_use[i]=true;
		lis[e[i].u].PB(make_next(e[i].v,e[i].c));
		lis[e[i].v].PB(make_next(e[i].u,e[i].c));
		connect(u,v);
	}
	for (int i=1;i<=m;i++) if (!in_use[i]){
		query[e[i].u].PB(make_next(e[i].v,e[i].c));
		query[e[i].v].PB(make_next(e[i].u,e[i].c));
	}
	calculate(1);
}
//
inline int get_min(int u,int len){
	int lv=17;
	int res=1e9;
	while (len>0){
		if (base[lv]<=len){
			res=gmin(res,f[u][lv]);
			u=dad[u][lv];
			len-=base[lv];
		}
		lv--;
	}
	return res;
}
inline int get_min_change(int &u,int len){
	int lv=17;
	int res=1e9;
	while (len>0){
		if (base[lv]<=len){
			res=gmin(res,f[u][lv]);
			u=dad[u][lv];
			len-=base[lv];
		}
		lv--;
	}
	return res;
}
inline void analyze(int u,int v,int &pipe_len){
	int r=1e9;
	int t=gmin(d[u],d[v])-d[trace(v)];
	if (d[u]<d[v]){
		r=get_min_change(v,d[v]-d[u]);
	}else{
		r=get_min_change(u,d[u]-d[v]);
	}
	r=gmin(r,gmin(get_min(u,t),get_min(v,t)));
	if (pipe_len<r) result+=r-pipe_len;
}
void process(int u){
	visited[u]=true;
	list<next>::iterator it;
	list<next>::iterator loop;
	int v;
	for (loop=query[u].begin();loop!=query[u].end();loop++){
		v=loop->v;
		if (visited[v]) analyze(u,v,loop->c);
	}
	for (it=lis[u].begin();it!=lis[u].end();it++){
		v=it->v;
		if (visited[v]) continue;
		process(v);
		combine(trace(u),trace(v));
	}
}
void solve(){
	memset(visited,false,sizeof(visited));
	memset(lab,255,sizeof(lab));
	process(1);
	cout<<result;
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	enter();
	init();
	solve();
	//cout<<endl<<clock()<<" ms";
	return 0;
}