收回我以前对某些题的评论–这一道tmd才是最恶心的。

苟活者在淡红的WA中会依稀看见微茫的希望,真正的傻B会更奋然而AC。–某树人

耗时4.5个小时,手写180行代码,套用5种模板,定义16个数组,提交近10次,终于AC…


题意:

给定一个联通图,有2种操作,删边和询问两点之间有几条边去掉之后两点不再联通。保证图一直联通。(点数<=30000,边数<=100000,操作<=40000)

思路:

1.对于删边操作,我们不妨倒过来处理,变成加边。
2.如果图中有环,那么显然这个环上的每个边去掉之后图都是联通的,因此我们将环缩成点处理,这时两点间的距离就是每个询问的答案。而两点之间的距离就是dis(a,b)=dep(a)+dep(b)-2dep(lca)
3.每次添边时把形成的环缩成点,每个点显然只会缩一次,缩完了作为一个新点和别人一起缩,因此缩点的均摊复杂度是O(1)的。
4.每次把环上的点缩到深度最小的点上去,这样对点深度的维护很有利。
5.利用dfs序把每个点映射到一个线段树里去,每一棵子树代表的区间就是[a,b],a,b分别为子树中最小和最大节点编号。
6.每次将一个点缩点,就是将它和它的子树的深度降为缩点后的值。
7.LCA可以预处理出倍增的数组,每次logn询问LCA。
8.线段树可以标记永久化。

总结以上思路发现:

1.我们需要涉及到动态的缩点、联通性的判断、dfs序的维护、点集的维护。因此我们需要至少4个数组维护这些映射的信息。
2.光是并查集就要写两个。
3.我们还需要一个set判断边是否被删过。
4.我们也许需要用tarjan进行第一次缩点(分析发现可以不用)。
5.我们会套很多的模板,打很多的代码。
6.这是一道省选题。(你TM省选考这玩意)

不过我还是耐着性子打完了

然后狂WA(数组开小了TMD会WA)

AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>

#define MX 30002
#define ME 100001
#define ls (node<<1)
#define rs (node<<1|1)
#define mid ((l+r)>>1)

using namespace std;

int dp[MX];
int anc[MX][21];
int fst[MX],nxt[ME],v[ME],lnum=-1;
int srcu[ME],srcv[ME];
int n,m,q;

int fa[MX];
int color[MX];
int suoa[ME],suob[ME],suon;
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}

int ranks[MX],nowr;
int lranks[MX],rranks[MX];

int belong[MX],trefa[MX];
int findbel(int x){return x==belong[x]?x:belong[x]=findbel(belong[x]);}

typedef struct qurd
{
    int a,b,c,ans;
}requires;
typedef struct asdf
{
    int l,r,add,sum;
}segments;
typedef pair<int,int>pii;

requires qur[ME];
segments dep[MX<<2];
set<pii>isdel;

void addeg(int nu,int nv)
{
    nxt[++lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
}

void build(int node,int l,int r)
{
    dep[node].l=l,dep[node].r=r;
    dep[node].add=0;
    dep[node].sum=0;
    if(l==r)return;
    else build(ls,l,mid),build(rs,mid+1,r);
}

void add(int node,int ql,int qr,int x)
{
    int l=dep[node].l,r=dep[node].r;
    if(ql<=l&&r<=qr)dep[node].add+=x;
    else if(l>qr||r<ql)return;
    else add(ls,ql,qr,x),add(rs,ql,qr,x);
}

int qsm(int node,int p)
{
    int l=dep[node].l,r=dep[node].r;
    if(l==r)return dep[node].add+dep[node].sum;
    else if(p<=mid)return qsm(ls,p)+dep[node].add;
    else return qsm(rs,p)+dep[node].add;
}

void initdfs(int x,int fa,int nowd)
{
    dp[x]=nowd;
    trefa[x]=fa;
    anc[x][0]=fa;
    for(int i=1;i<=20;i++)anc[x][i]=anc[anc[x][i-1]][i-1];
    ranks[x]=++nowr;
    lranks[x]=rranks[x]=nowr;
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(v[i]==fa)continue;
        initdfs(v[i],x,nowd+1);
        rranks[x]=max(rranks[x],rranks[v[i]]);
    }
    add(1,lranks[x],rranks[x],1);
}

int getLCA(int a,int b)
{
    if(dp[a]<dp[b])swap(a,b);
    for(int i=20;i>=0;i--)
        if(dp[anc[a][i]]>=dp[b])
            a=anc[a][i];
    if(a==b)return a;
    for(int i=20;i>=0;i--)
        if(anc[a][i]!=anc[b][i])
            a=anc[a][i],b=anc[b][i];
    return anc[a][0];
}

void comb(int a,int b)
{
    int lca=findbel(getLCA(a,b));
    int bl=findbel(lca);
    a=findbel(a),b=findbel(b);
    for(int i=a;i!=bl;i=trefa[i])
    {
        i=findbel(i);
        if(i==bl)break;
        add(1,lranks[i],rranks[i],-1);
        belong[i]=bl;
    }
    for(int i=b;i!=bl;i=trefa[i])
    {
        i=findbel(i);
        if(i==bl)break;
        add(1,lranks[i],rranks[i],-1);
        belong[i]=bl;
    }
}

void graphinit()
{
    for(int i=1;i<=n;i++)fa[i]=i,belong[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(!isdel.count(make_pair(srcu[i],srcv[i])))
        {
            if(findfa(srcu[i])!=findfa(srcv[i]))addeg(srcu[i],srcv[i]),addeg(srcv[i],srcu[i]),fa[findfa(srcu[i])]=srcv[i];
            else suoa[++suon]=srcu[i],suob[suon]=srcv[i];
        }
    }
    build(1,1,n);
    initdfs(1,0,1);
    for(int i=1;i<=suon;i++)comb(suoa[i],suob[i]);
}

void input()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&srcu[i],&srcv[i]);
    while(1)
    {
        if(!(~scanf("%d%d%d",&c,&a,&b)))break;
        if(c==-1)break;
        q++;
        qur[q].a=a,qur[q].b=b,qur[q].c=c;
        if(c==0)isdel.insert(make_pair(a,b)),isdel.insert(make_pair(b,a));
    }
}

void work()
{
    for(int i=q;i>=1;i--)
    {
        if(qur[i].c==1)
        {
            int lca=getLCA(qur[i].a,qur[i].b);
            qur[i].ans=qsm(1,ranks[qur[i].a])+qsm(1,ranks[qur[i].b])-2*qsm(1,ranks[lca]);
        }
        else comb(qur[i].a,qur[i].b);
    }
    for(int i=1;i<=q;i++)if(qur[i].c==1)printf("%d\n",qur[i].ans);
}

int main()
{
    memset(fst,0xff,sizeof(fst));
    input();
    graphinit();
    work();
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

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

你是机器人吗? =。= *