[图论][生成树扩展][LCA] bzoj1977 次小生成树模板题

这个题确实是领悟到了不少东西,lca倍增的思想和用途,思维方法,构建生成树的逻辑,严格次小的要求。发现图论很重要的一个东西就是存储用的数据结构,我不怎么会写前向星于是就很难受了。。就这个题而言是要先求MST,再对MST做LCA,那么就会有两个图,一个是原始的用来求MST,另一个用来求LCA,第二个就是MST这个树本身。所以建了俩图,第二个图是在Kruskal的过程中建立的,与此同时还要记录下来不在MST上的边,以便之后的枚举操作。另外一个需要注意的点就是要求是严格次小,所以的就需要保存一个第二大这么一个数,这个又有很多情况,不同树上区间合并的时候根据两个区间最大的数的关系来处理。

错误的话,1 求LCA的时候应该swap 使得较深的为y,这里写错了                          2 数组容量开错,这个今天错了几次,主要是没看清m和n,而且总是蜜汁把m写成n。。                                                                                                                          3 数组下标写错(为什么经常做这种蠢事????                                                    4 跟LL比较大小却初始化为1<<29,,显然不够,改成1<<60就过了,也是最后一个错误

 


#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long LL;
const int maxn=2e5+5;

int fa[maxn][18],fst[maxn][18],sec[maxn][18];
int dep[maxn],n,m,used[3*maxn];
vector >G[maxn];
int e[3*maxn],u[3*maxn],v[3*maxn],w[3*maxn];
bool cmp(int i,int j){return w[i]Q;
    int u,v,w;
    Q.push(root);
    fa[root][0]=dep[root]=0;
    flag[root]=1;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        for (int i=0;i=(1<fst[fa[j][i-1]][i-1])
            sec[j][i]=max(sec[j][i],fst[fa[j][i-1]][i-1]);
        else if(fst[j][i-1]dep[v])swap(u,v);//order error
    int x=u,y=v;
    int lca,d=dep[y]-dep[x];
    for (int i=0;(1<=0;i--)//顺序
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
        lca=fa[x][0];
    }
    x=u,y=v;
    int ans=0;
    for (int i=17;i>=0;i--)
    {
        if(dep[x]-dep[lca]>=(1<=(1<

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据