[TIOJ] 1445. 機器人組裝大賽

題目連結:http://tioj.infor.org/problems/1445

---

不難發現本題就是是一題裸次小生成樹題，那次小生成樹該怎麼寫呢？先求一棵最小生成樹後，枚舉所有不在最小生成樹上的邊，把它塞到最小生成樹上，此時必定會產生一個環，而把在環上且在最小生成樹上的最大邊拔掉後就得到了另一個生成樹，不難證明枚舉完這些樹後得到的答案就會是次小生成樹。不過要怎麼有效率的求一個路徑上的最大值呢？不難想到可以樹練剖分，不過礙於記憶體限制，我不太確定會不會MLE。不過想想後如果你是用倍增法求LCA的話，在跑上去的過程中似乎就可以順便算最大值，所以就先求LCA後，再對兩個點倍增到LCA，並同時算最大值就可以解決這問題了。複雜度：$O(E log E)$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PB push_back
typedef long long lld;
typedef pair<lld,lld> pll;

#define N 1000
#define logN 15
#define INF 2147483647777

struct Edge{
	int s,e;
	lld v;
};

int djs[N+5];
inline int Query(int);
inline void Merge(int,int);
vector<Edge> Tree;
vector<pll> MST[N+5];
pll ff[N+5][logN+5];
int timer=0,time_in[N+5],time_out[N+5];
void dfs(lld,lld,lld);
inline bool anc(int,int);
inline int lca(int,int);
inline lld walk(int,int);

int main(){
	cin.tie(0);ios_base::sync_with_stdio();
	int n,m;
	cin>>n>>m;
	for(int i=0;i<N+5;i++) djs[i]=i;
	for(int i=0;i<N+5;i++)for(int j=0;j<logN+5;j++)ff[i][j]={i,0};
	for(int i=0;i<m;i++){
		int a,b;lld c;
		cin>>a>>b>>c;
		Tree.PB({a,b,c});
	}
	sort(Tree.begin(),Tree.end(),[](const Edge& a,const Edge& b){return a.v<b.v;});
	queue<Edge> noMST;
	lld sumMST=0,countMST=0;
	for(auto i:Tree){
		if(Query(i.s)!=Query(i.e)){
			sumMST+=i.v;
			countMST++;
			Merge(i.s,i.e);
			MST[i.s].PB({i.e,i.v});
			MST[i.e].PB({i.s,i.v});
		}else noMST.push(i);
	}
	if(countMST!=n-1)cout<<"-1 -1"<<endl;
	else if(noMST.empty()) cout<<sumMST<<" -1"<<endl;
	else{
		dfs(1,1,0);
		for(int j=1;j<=logN;j++){
			for(int i=1;i<=n;i++){
				ff[i][j].first = ff[ ff[i][j-1].first ][j-1].first;
				ff[i][j].second = max(ff[ff[i][j-1].first][j-1].second, ff[i][j-1].second);
			}
		}
		lld smst=INF;
		while(!noMST.empty()){
			auto tp=noMST.front();noMST.pop();
			int LCA = lca(tp.s,tp.e);
			lld tt = walk(tp.s,LCA);
			tt = max(tt, walk(tp.e,LCA));
			smst=min(smst, sumMST-tt+tp.v);
		}
		cout<<sumMST<<' '<<smst<<endl;
	}
	return 0;
}
inline int Query(int x){
	if(djs[x]!=x) djs[x]=Query(djs[x]);
	return djs[x];
}
inline void Merge(int a,int b){
	djs[Query(a)]=Query(b);
}

void dfs(lld w,lld f,lld v){
	time_in[w]=++timer;
	ff[w][0]={f,v};
	for(auto i:MST[w])
		if(i.first!=f) dfs(i.first,w,i.second);
	time_out[w]=++timer;
}
inline bool anc(int x,int y){
	return time_in[x]<=time_in[y]&&time_out[y]<=time_out[x];
}
inline int lca(int x,int y){
	if(anc(y,x))return y;
	for(int j=logN;j>=0;j--)
		if(!anc(ff[y][j].first, x)) y=ff[y][j].first;
	return ff[y][0].first;
}

inline lld walk(int x,int y){
	if(x==y)return 0;
	if(anc(y,x)) swap(x,y);
	lld rr=0;
	for(int i=logN;i>=0;i--){
		if(!anc(ff[y][i].first,x)){
			rr=max(rr, ff[y][i].second);
			y=ff[y][i].first;
		}
	}
	rr=max(rr, ff[y][0].second);
	return rr;
}