11.04T3 次小生成树

3232 -- 【BJOI2010】次小生成树

Description

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

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

Input

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

Output

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

Sample Input

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

Sample Output

Hint

【数据规模】
　　数据中无向图无自环；
　　50%的数据 N≤2000 M≤3000；
　　80%的数据 N≤50000 M≤100000；
　　100%的数据 N≤100000 M≤300000，边权值非负且不超过 10^9。

Source

xinyue

分析：最小生成树，倍增法

首先考虑不严格的次小生成树

我们先求出最小生成树,然后对每条不在最小生成树的边(x,y)，求出x->y路径上的最大的边，把它替换这条边之后的树就可能是次小生成树

用倍增思想记录max[x][i]表示x的第2^i的祖先到ｘ的边上的最大值就可以做到Ｏ（nlogn）

严格次小稍微有些区别，如果路径最大边和边(x,y)权值相同，就不能替换，而要换严格次大的边,所以多记一个secmax[x][i]表示x的第2^i的祖先到ｘ的边上的严格最大值即可

code：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #define N 300005
  6 using namespace std;
  7 struct node {
  8     int u,v,w,tag;
  9 } t[N],e[N];
 10 int first[N],nxt[N],cnt;
 11 void add(int u,int v,int w) {
 12     e[++cnt].u=u;
 13     e[cnt].v=v;
 14     e[cnt].w=w;
 15     nxt[cnt]=first[u];
 16     first[u]=cnt;
 17 }
 18 int fa[N];
 19 int find(int x) {
 20     if(x!=fa[x])return fa[x]=find(fa[x]);
 21     return fa[x];
 22 }
 23 void merge(int x,int y) {
 24     int f1=find(x),f2=find(y);
 25     if(f1!=f2)fa[f1]=f2;
 26 }
 27 long long sum=0;
 28 int n,m;
 29 void kruskal() {
 30     int cnt_=0;
 31     for(int i=1; i<=m; i++) {
 32         int u=t[i].u,v=t[i].v;
 33         if(find(u)!=find(v)) {
 34             merge(u,v);
 35             add(u,v,t[i].w);
 36             add(v,u,t[i].w);
 37             t[i].tag=1;
 38             sum+=t[i].w;
 39             cnt_++;
 40             if(cnt_==n-1)return;
 41         }
 42     }
 43 }
 44 int f[N][30],dep[N],mx[N][30],smx[N][30];
 45 void dfs(int x) {
 46     for(int i=first[x]; i; i=nxt[i]) {
 47         int v=e[i].v;
 48         if(v==f[x][0])continue;
 49         mx[v][0]=e[i].w;
 50         smx[v][0]=-1;
 51         dep[v]=dep[x]+1;
 52         f[v][0]=x;
 53         dfs(v);
 54     }
 55 }
 56 pair<int,int> lca(int x,int y) {
 57     int max0=-1;
 58     int smax0=-1;
 59     if(dep[x]<dep[y])swap(x,y);
 60     for(int i=19; i>=0; i--) {
 61         if(dep[f[x][i]]>=dep[y]) {
 62             if(max0<mx[x][i]) {
 63                 smax0=max0;
 64                 max0=mx[x][i];
 65             }
 66             smax0=max(smax0,smx[x][i]);
 67             max0=max(max0,mx[x][i]);
 68             x=f[x][i];
 69         }
 70         if(x==y)return make_pair(max0,smax0);
 71     }
 72     for(int i=19; i>=0; i--) {
 73         if(f[x][i]==f[y][i]) continue;
 74         if(mx[x][i]>max0) {
 75             smax0=max0;
 76             max0=mx[x][i];
 77         } else if(mx[x][i]<max0) {
 78             smax0=max(smax0,mx[x][i]);
 79         }
 80         if(mx[y][i]>max0) {
 81             smax0=max0;
 82             max0=mx[y][i];
 83         } else if(mx[y][i]<max0) {
 84             smax0=max(smax0,mx[y][i]);
 85         }
 86         smax0=max(smax0,max(smx[x][i],smx[y][i]));
 87         max0=max(max0,max(mx[x][i],mx[y][i]));
 88         x=f[x][i];
 89         y=f[y][i];
 90     }
 91     max0=max(mx[x][0],max(max0,mx[y][0]));
 92     if(mx[x][0]<max0) {
 93         smax0=max(smax0,mx[x][0]);
 94     }
 95     if(mx[y][0]<max0) {
 96         smax0=max(smax0,mx[y][0]);
 97     }
 98     return make_pair(max0,smax0);
 99 }
100 bool cmp(const node&a,const node&b) {
101     return a.w<b.w;
102 }
103 int main() {
104     ios::sync_with_stdio(false);
105     cin>>n>>m;
106     for(int i=1; i<=n; i++)fa[i]=i;
107     for(int i=1; i<=m; i++) {
108         int u,v,w;
109         cin>>t[i].u>>t[i].v>>t[i].w;
110     }
111     sort(t+1,t+m+1,cmp);
112     kruskal();
113     memset(smx,-1,sizeof f);
114     memset(mx,-1,sizeof mx);
115     f[1][0]=1;
116     dfs(1);
117     for(int i=1; i<=19; i++) {
118         for(int j=1; j<=n; j++) {
119             f[j][i]=f[f[j][i-1]][i-1];
120             mx[j][i]=max(mx[j][i-1],mx[f[j][i-1]][i-1]);
121             if(mx[j][i-1]!=mx[f[j][i-1]][i-1]) {
122                 smx[j][i]=max(smx[j][i],min(mx[j][i-1],mx[f[j][i-1]][i-1]));
123                 smx[j][i]=max(smx[j][i],max(smx[j][i-1],smx[f[j][i-1]][i-1]));
124             } else {
125                 smx[j][i]=max(smx[j][i-1],smx[f[j][i-1]][i-1]);
126             }
127         }
128     }
129     int delta=999999;
130     for(int i=1; i<=m; i++) {
131         if(t[i].tag)continue;
132         pair<int,int> now=lca(t[i].u,t[i].v);
133         if(t[i].w==now.first) {
134             delta=min(delta,t[i].w-now.second);
135             continue;
136         }
137         delta=min(delta,t[i].w-now.first);
138     }
139     cout<<sum+delta;
140     return 0;
141 }

over