[BZOJ3563/BZOJ3569]DZY Loves Chinese/DZY Loves Chinese II(线性基,随机化)

发布于 2018-03-29  72 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3563/BZOJ3569]DZY Loves Chinese/DZY Loves Chinese II(线性基,随机化)

Description

神校XJ之学霸兮,Dzy皇考曰JC。
摄提贞于孟陬兮,惟庚寅Dzy以降。
纷Dzy既有此内美兮,又重之以修能。
遂降临于OI界,欲以神力而凌♂辱众生。

今Dzy有一魞歄图,其上有N座祭坛,又有M条膴蠁边。
时而Dzy狂WA而怒发冲冠,神力外溢,遂有K条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。(可视为立即复原)
然若有祭坛无法相互到达,Dzy之神力便会大减,于是欲知其是否连通。

Tag

线性基,随机化

解决思路

考虑对整个图构一棵生成树,那么图不连通当且仅当有一条树边断开且跨越这条边的所有非树边也都断开。
如何判断一条树边断开的同时跨越它的所有非树边也都断开呢?可以给每一个非树边随机一个权值,树边的权值则为所有跨越了它的非树边的权值异或和。
那么,对于每一个询问,如果边的异或和为0,则说明有一组树边和所有覆盖它的非树边都被删除,所以不连通。
求树边的权值可以用树上差分,而求是否存在异或和为0可以用线性基。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=500100*2;
const int maxM=500100*2;
const int inf=2147483647;

class Edge
{
public:
    int val;
    int u,v;
    bool path;
};

int n,m;
int edgecnt=-1,Head[maxN],Next[maxM],V[maxM];
Edge E[maxM];
int Val[maxN];
bool vis[maxN];
int Base[31];

void Add_Edge(int u,int v);
void dfs1(int u,int fa);
void dfs2(int u,int fa);

int main()
{
    srand(141404^170524);mem(Head,-1);
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf("%d%d",&E[i].u,&E[i].v);
        Add_Edge(E[i].u,E[i].v);Add_Edge(E[i].v,E[i].u);
    }

    dfs1(1,1);//随机生成树
    for (int i=0;i<m;i++)//给非树边随机一个权值
        if (E[i].path==0)
        {
            E[i].val=rand()%(1<<30);
            Val[E[i].u]^=E[i].val;//打上差分标记
            Val[E[i].v]^=E[i].val;
        }
    mem(vis,0);
    dfs2(1,1);//求树边权值

    int Q;scanf("%d",&Q);
    int Ans=0;
    while (Q--)
    {
        int K;scanf("%d",&K);
        mem(Base,0);//线性基求是否有异或和为0的
        bool flag=1;
        while (K--)
        {
            int e;scanf("%d",&e);e^=Ans;e=E[e-1].val;
            for (int i=30;i>=0;i--)
                if ((e&(1<<i))!=0)
                {
                    if (Base[i]==0){
                        Base[i]=e;break;
                    }
                    else e^=Base[i];
                }
            if (e==0) flag=0;
        }
        if (flag==1) printf("Connected\n"),Ans++;
        else printf("Disconnected\n");
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void dfs1(int u,int fa)//随便构出一棵生成树
{
    vis[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            E[i>>1].path=1;
            dfs1(V[i],u);
        }
    return;
}

void dfs2(int u,int fa)//求出树边上的权值
{
    vis[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            dfs2(V[i],u);
            E[i>>1].val^=Val[V[i]];
            Val[u]^=Val[V[i]];
        }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3563/BZOJ3569]DZY Loves Chinese/DZY Loves Chinese II(线性基,随机化)


HNCJ OIer