[BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条(树Hash,二分图)

发布于 2018-05-25  107 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条(树Hash,二分图)

Description

故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师,他不仅是个身手敏捷的武林高手,飞檐走壁擅长各种暗杀术。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。
曾经有一次,为了寻找Altair 留下的线索和装备,Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室,且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记,他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室,Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印,他需要通过改变某些刺客标记的启动情况,使得所有刺客标记与封印密码“看起来一样”。
在这里,“看起来一样”的定义是:存在一种“标记”密室与“密码”密室之间一一对应的关系,使得密室间的连接情况和启动情况相同(提示中有更详细解释)。幸运的是,在Ezio 来到刺客墓穴之前,在Da Vinci 的帮助下,Ezio 已经得知了打开储藏室所需要的密码。
而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

Tag

树Hash,二分图

解决思路

首先知道,一棵树如果重新编号后与自身同构,一定有重心不变,若重心有两个,则新建一个点连接两个重心,使得只有一个重心。
这样我们就可以确定以重心个点为根进行匹配。子树同构判断可以用树$$Hash$$来做。
预处理出任意一棵子树的$$Hash$$值后,设$$F[i][j]$$表示编号为$$i$$的点新编号为$$j$$后的最小代价,前提是$$i$$与$$j$$同构。那么,就需要把$$i$$和$$j$$的儿子进行匹配,由于保证儿子的值现在已经求出来了,所以对$$Hash$$值相同的连边,作二分图最小权匹配。这里采用费用流的形式实现。

代码

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

#define ll long long
#define ull unsigned long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const ull base1=20020729;
const ull base2=170524;
const int inf=2147483647;

class SortData
{
public:
    int depth,id;
    ull hash;
};

int n;
int Val1[maxN],Val2[maxN];
ull Hash[maxN];
int Depth[maxN],Fa[maxN];
SortData Sorter[maxN];
int F[maxN][maxN];

bool cmp1(SortData A,SortData B);
bool cmp2(int a,int b);
int DP(int u,int v);

namespace Tree
{
    const int maxN=1010;
    const int maxM=maxN*2;

    int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
    int Size[maxN],mxSon[maxN];
    int root;
    ull Sorter[maxN];

    void Init();
    void Add_Edge(int u,int v);
    void GetRoot();
    void dfs_root(int u,int fa);
    void GetHash(int u,int fa);
}

namespace Flow
{
    const int maxN=1510;
    const int maxM=maxN*maxN*30;

    class Edge
    {
    public:
        int u,v,flow,w;
    };

    int S,T;
    int edgecnt,Head[maxN],Next[maxM];
    Edge E[maxM];
    int Dist[maxN],Flow[maxN],Path[maxN];
    queue<int> Queue;
    bool inqueue[maxN];

    void Init();
    void Add_Edge(int u,int v,int flow,int w);
    int GetMxFlow();
    bool Spfa();
}

int main()
{
    Tree::Init();
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        Tree::Add_Edge(u,v);Tree::Add_Edge(v,u);
    }

    for (int i=1;i<=n;i++) scanf("%d",&Val1[i]);
    for (int i=1;i<=n;i++) scanf("%d",&Val2[i]);

    Tree::GetRoot();//得到重心
    Tree::GetHash(Tree::root,0);//预处理出Hash值

    for (int i=1;i<=n;i++) Sorter[i]=((SortData){Depth[i],i,Hash[i]});
    sort(&Sorter[1],&Sorter[n+1],cmp1);//将Hash值排序,按深度从大到小,Hash值从小到大
    for (int i=1,j;i<=n;i=j)
    {
        j=i+1;
        while ((j<=n)&&(Sorter[i].depth==Sorter[j].depth)&&(Sorter[i].hash==Sorter[j].hash)) j++;
        for (int k=i;k<j;k++)
            for (int l=i;l<j;l++)//对于Hash值相同的,说明子树同构,匹配求解出最小代价
                F[Sorter[k].id][Sorter[l].id]=DP(Sorter[k].id,Sorter[l].id);
    }
    printf("%d\n",F[Tree::root][Tree::root]);
}

bool cmp1(SortData A,SortData B)
{
    if (A.depth!=B.depth) return A.depth>B.depth;
    return A.hash<B.hash;
}

bool cmp2(int a,int b)
{
    return Hash[a]<Hash[b];
}

int DP(int u,int v)
{
    int st1[maxN],st2[maxN],top1=0,top2=0;
    for (int i=Tree::Head[u];i!=-1;i=Tree::Next[i])
        if (Tree::V[i]!=Fa[u]) st1[++top1]=Tree::V[i];
    for (int i=Tree::Head[v];i!=-1;i=Tree::Next[i])
        if (Tree::V[i]!=Fa[v]) st2[++top2]=Tree::V[i];
    sort(&st1[1],&st1[top1+1],cmp2);
    sort(&st2[1],&st2[top2+1],cmp2);
    Flow::Init();
    Flow::S=top1+top2+1;Flow::T=Flow::S+1;
    for (int i=1;i<=top1;i++) Flow::Add_Edge(Flow::S,i,1,0);
    for (int i=1;i<=top2;i++) Flow::Add_Edge(i+top1,Flow::T,1,0);
    for (int i=1,j;i<=top1;i=j)
    {
        j=i+1;
        while ((j<=top1)&&(Hash[st1[i]]==Hash[st1[j]])) j++;
        for (int k=i;k<j;k++)
            for (int l=i;l<j;l++)
                Flow::Add_Edge(k,top1+l,1,F[st1[k]][st2[l]]);
    }
    return Flow::GetMxFlow()+(Val1[u]^Val2[v]);
}

namespace Tree
{
    void Init()
    {
        edgecnt=0;mem(Head,-1);
        return;
    }

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

    void GetRoot()
    {
        root=0;mxSon[0]=inf;
        dfs_root(1,0);

        if ((mxSon[root]<<1)==n)
        {
            int node1=root;
            root=0;dfs_root(node1,0);
            for (int i=Head[node1],last=-1;i!=-1;last=i,i=Next[i])
                if ((Size[V[i]]<<1)==n)
                {
                    ++n;
                    if (i==Head[node1]) Head[node1]=Next[i];
                    else Next[last]=Next[i];
                    for (int j=Head[V[i]],last2=-1;j!=-1;last2=j,j=Next[j])
                        if (V[j]==node1)
                        {
                            if (j==Head[V[i]]) Head[V[i]]=Next[j];
                            else Next[last2]=Next[j];
                            break;
                        }

                    Add_Edge(node1,n);Add_Edge(n,node1);Add_Edge(V[i],n);Add_Edge(n,V[i]);
                    root=n;
                    break;
                }
        }

        return;
    }

    void dfs_root(int u,int fa)
    {
        Size[u]=1;mxSon[u]=0;
        for (int i=Head[u];i!=-1;i=Next[i])
            if (V[i]!=fa)
            {
                dfs_root(V[i],u);
                Size[u]+=Size[V[i]];
                mxSon[u]=max(mxSon[u],Size[V[i]]);
            }
        mxSon[u]=max(mxSon[u],n-Size[u]);
        if (mxSon[u]<mxSon[root]) root=u;
        return;
    }

    void GetHash(int u,int fa)
    {
        Depth[u]=Depth[fa]+1;Fa[u]=fa;
        for (int i=Head[u];i!=-1;i=Next[i])
            if (V[i]!=fa) GetHash(V[i],u);
        int cnt=0;
        for (int i=Head[u];i!=-1;i=Next[i])
            if (V[i]!=fa) Sorter[++cnt]=Hash[V[i]];
        sort(&Sorter[1],&Sorter[cnt+1]);
        Hash[u]=base2;
        for (int i=1;i<=cnt;i++) Hash[u]=((Hash[u]*base1)^Sorter[i])+Sorter[i];
        return;
    }
}

namespace Flow
{
    void Init()
    {
        edgecnt=-1;mem(Head,-1);
        return;
    }

    void Add_Edge(int u,int v,int flow,int w)
    {
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].u=u;E[edgecnt].v=v;E[edgecnt].flow=flow;E[edgecnt].w=w;
        edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].u=v;E[edgecnt].v=u;E[edgecnt].flow=0;E[edgecnt].w=-w;
        return;
    }

    int GetMxFlow()
    {
        int Ans=0;
        int flowsum=0;
        while (Spfa())
        {
            Ans=Ans+Flow[T]*Dist[T];flowsum+=Flow[T];
            int now=T;
            while (now!=S)
            {
                E[Path[now]].flow-=Flow[T];
                E[Path[now]^1].flow+=Flow[T];
                now=E[Path[now]].u;
            }
        }
        return Ans;
    }

    bool Spfa()
    {
        for (int i=1;i<=T;i++) Dist[i]=inf;
        while (!Queue.empty()) Queue.pop();
        mem(inqueue,0);
        Dist[S]=0;Queue.push(S);Flow[S]=inf;inqueue[S]=1;
        do
        {
            int u=Queue.front();Queue.pop();
            for (int i=Head[u];i!=-1;i=Next[i])
                if ((E[i].flow>0)&&(Dist[E[i].v]>Dist[u]+E[i].w))
                {
                    Dist[E[i].v]=Dist[u]+E[i].w;Flow[E[i].v]=min(Flow[u],E[i].flow);Path[E[i].v]=i;
                    if (inqueue[E[i].v]==0)
                    {
                        Queue.push(E[i].v);
                        inqueue[E[i].v]=1;
                    }
                }
            inqueue[u]=0;
        }
        while (!Queue.empty());
        if (Dist[T]==inf) return 0;
        return 1;
    }
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条(树Hash,二分图)


HNCJ OIer 一枚