[Beijing2010组队]次小生成树Tree

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) \sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)∑e∈EMvalue(e)<∑e∈ESvalue(e)

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入输出格式

输入格式：

第一行包含两个整数N 和M，表示无向图的点数与边数。接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

输出格式：

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

输入输出样例

输入样例#1：

5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6

输出样例#1：复制

说明

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

跑个最小生成树然后LCA维护路径最大和次大(严格)边即可，利用了最小生成树的环性质。

(我就想请问出题人忘了给边排序是怎么能过样例hhhh，mdzz查错了一个点最后发现没给边排序)

code:

#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
ll base=0;
struct lines{
int u,v,w;
bool operator <(const lines &U)const{
return w<U.w;
}
}l[maxn*3];
struct node{
int m,cm;
node operator +(const node &u)const{
node r;
r.m=max(m,u.m);
r.cm=max(cm,u.cm);
if(m<r.m) r.cm=max(r.cm,m);
if(u.m<r.m) r.cm=max(r.cm,u.m);
return r;
}
};
const int inf=1e9;
bool choose[maxn*3];
int ci[30],ans=inf;
int to[maxn*2],ne[maxn*2];
int val[maxn*2],cnt=0,n,m;
int f[maxn][20];
node g[maxn][20];
int hd[maxn],p[maxn],dep[maxn];int ff(int x){
return p[x]==x?x:(p[x]=ff(p[x]));
}inline void add(lines e){
to[++cnt]=e.v,ne[cnt]=hd[e.u],val[cnt]=e.w,hd[e.u]=cnt;
to[++cnt]=e.u,ne[cnt]=hd[e.v],val[cnt]=e.w,hd[e.v]=cnt;
}inline void kruscal(){
for(int i=1;i<=n;i++) p[i]=i;
int fa,fb,tot=0;
sort(l+1,l+m+1);n--;
for(int i=1;i<=m;i++){
fa=ff(l[i].u),fb=ff(l[i].v);
if(fa!=fb){
tot++,choose[i]=1;
base+=(ll)l[i].w;
add(l[i]),p[fa]=fb;
if(tot==n) break;
}
}
n++;
}void dfs(int x,int fa){
for(int i=1;ci[i]<=dep[x];i++){
g[x][i]=g[x][i-1]+g[f[x][i-1]][i-1];
f[x][i]=f[f[x][i-1]][i-1];
}for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa){
dep[to[i]]=dep[x]+1;
f[to[i]][0]=x;
g[to[i]][0]=(node){val[i],0};
dfs(to[i],x);
}
}inline node LCAMAX(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int dt=dep[x]-dep[y];
node an=(node){0,0};
for(int i=0;ci[i]<=dt;i++) if(ci[i]&dt){
an=an+g[x][i];
x=f[x][i];
}if(x==y) return an;int s=log(dep[x])/log(2)+1;
for(;s>=0;s--){
if(ci[s]>dep[x]) continue;
if(f[x][s]!=f[y][s]){
an=an+g[x][s]+g[y][s];
x=f[x][s],y=f[y][s];
}
}return an+g[x][0]+g[y][0];
}inline void solve(){
dep[1]=0;
dfs(1,0);node tmp;
for(int i=1;i<=m;i++) if(!choose[i]){
tmp=LCAMAX(l[i].u,l[i].v);
//printf("%d %d %d\n",i,tmp.m,tmp.cm);
if(tmp.m<l[i].w) ans=min(ans,l[i].w-tmp.m);
else ans=min(ans,l[i].w-tmp.cm);
}
}int main(){
ci[0]=1;
for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&l[i].u,&l[i].v,&l[i].w);kruscal();
solve();cout<<(ll)ans+base<<endl;
return 0;
}