BZOJ 1977([BeiJing2010组队]次小生成树 Tree-LCA的位运算)

1977: [BeiJing2010组队]次小生成树 Tree

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1176  Solved: 234
[Submit][Status][Discuss]

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

11

HINT

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

Source

这题的关键就在于求Lca,记录路径上的最小与严格次小值.

用f[i][j]表示i的第2^j个儿子(0 表示 不存在)

那么f[i][j]=f[ f[i][ j-1] ][j-1]

dp[i][j]和dp0[i][j]表示点i到f[i][j]的最小和严格次小值(不存在=-1),那么只需特判即可.

int lca(int x,int y,int &nowdp,int &nowdp0)
{
    if (deep[x]<deep[y]) swap(x,y);
    int t=deep[x]-deep[y]; //差的数量
    for (int i=0;t;i++) 
        if (t&bin[i])   //转化为位运算 bin[i]表示2<<i 把t看成2进制
        {
            x=f[x][i];
            t-=bin[i];
        }
    int i=Li-1; //Li 表示 最高存到2^(Li-1)个父亲
    while (x^y) //x和y不相等时
    {
        while (f[x][i]==f[y][i]&&i) i--; //当i==0时只能向上跳
        x=f[x][i];y=f[y][i];
    }
}