【BZOJ3197】[Sdoi2013]assassin树同构+动态规划+KM

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef unsigned long long ull;
const int maxn=710;
int n,m,cnt,rt,rt1,rt2,temp;
int f[maxn][maxn],la[15],lb[15],va[15],vb[15],map[15][15],from[15],siz[maxn],p[maxn];
int dep[maxn],to[maxn<<1],next[maxn<<1],head[maxn],a1[maxn],a2[maxn],vis[maxn];
ull hs[maxn];
vector ch[maxn];
bool cmp1(int a,int b)
{
return hs[a]}
bool cmp2(int a,int b)
{
return (dep[a]==dep[b])?(hs[a]dep[b]);
}
void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
inline int rd()
{
int ret=0,f=1;char gc=getchar();
while(gc<'0'||gc>'9'){if(gc=='-')f=-f;gc=getchar();}
while(gc>='0'&&gc<='9')ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void getrt(int x,int fa)
{
siz[x]=1;
int flag=0;
for(int i=head[x];i!=-1;i=next[i])if(to[i]!=fa)getrt(to[i],x),siz[x]+=siz[to[i]],flag|=(siz[to[i]]>(n/2));
flag|=(n-siz[x]>(n/2));
if(!flag&&rt1)rt2=x;
if(!flag&&!rt1)rt1=x;
}
void geths(int x)
{
for(int i=head[x];i!=-1;i=next[i])if(!vis[to[i]])vis[to[i]]=1,ch[x].push_back(to[i]);
hs[x]=ch[x].size()+1;
if(!ch[x].size())return ;
for(int i=0;i<(int)ch[x].size();i++)dep[ch[x][i]]=dep[x]+1,geths(ch[x][i]);
sort(ch[x].begin(),ch[x].end(),cmp1);
for(int i=0,j;i<(int)ch[x].size();i++)j=ch[x][i],hs[x]=hs[x]*131+hs[j]*hs[j]*hs[j];
}
int dfs(int x)
{
va[x]=1;
for(int i=0;i{
vb[i]=1;
if(from[i]==-1||dfs(from[i]))
{
from[i]=x;
return 1;
}
}
return 0;
}
int KM()
{
int i,j,k,ret=0;
for(i=0;i{
while(1)
{
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
if(dfs(i))break;
temp=1<<30;
for(j=0;jtemp=min(temp,la[j]+lb[k]-map[j][k]);
for(j=0;jfor(j=0;j}
}
for(i=0;ireturn ret;
}
int main()
{
n=rd();
int i,j,k,l,a,b;
memset(head,-1,sizeof(head));
for(i=1;igetrt(1,0);
for(i=1;i<=n;i++)a1[i]=rd();
for(i=1;i<=n;i++)a2[i]=rd();
if(rt2)rt=++n,add(rt,rt1),add(rt,rt2);
elsert=rt1;
vis[rt]=1,dep[rt]=1,geths(rt);
for(i=1;i<=n;i++)p[i]=i;
sort(p+1,p+n+1,cmp2);
memset(f,-1,sizeof(f));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(dep[p[i]]!=dep[p[j]]||hs[p[i]]!=hs[p[j]])continue;
m=ch[p[i]].size(),f[p[i]][p[j]]=(a1[p[i]]==a2[p[j]]);
if(!m)continue;
memset(la,0,sizeof(la)),memset(lb,0,sizeof(lb));
memset(from,-1,sizeof(from)),memset(map,-1,sizeof(map));
for(k=0;k{
for(l=0;l{
a=ch[p[i]][k],b=ch[p[j]][l];
if(hs[a]==hs[b])map[k][l]=f[a][b],la[k]=max(la[k],f[a][b]);
}
}
f[p[i]][p[j]]+=KM();
}
}
printf("%d",n-f[rt][rt]);
return 0;
}