费用流 #二分图最大权匹配 #dp
\(dp_{x,y}\) 表示以 \(x,y\) 为对应点的最大同构子树的大小
对于一对点，转移为将 \(x,y\) 中的点按照一定顺序对应
那么问题转化为如何求一组匹配，使得两两匹配的权值尽可能大，即一个二分图最大权匹配，可以费用流解决
然后枚举断开的每条边，对左右都做上述的 \(dp\) ，然后选择最大的贡献答案
// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 50 + 10;
namespace MCMF
{
const int MAXN = 105, MAXM = 100005, INF = 0x7fffffff;
int head[MAXN], cnt = 1;
struct Edge
{
int to, w, c, next;
} edges[MAXM * 2];
inline void add(int from, int to, int w, int c)
{
edges[++cnt] = {to, w, c, head[from]};
head[from] = cnt;
}
inline void addEdge(int from, int to, int w, int c)
{
add(from, to, w, c);
add(to, from, 0, -c);
}
int s, t, dis[MAXN], cur[MAXN];
bool inq[MAXN], vis[MAXN];
queue<int> Q;
bool SPFA()
{
while (!Q.empty())
Q.pop();
copy(head, head + MAXN, cur);
fill(dis, dis + MAXN, INF);
dis[s] = 0;
Q.push(s);
while (!Q.empty())
{
int p = Q.front();
Q.pop();
inq[p] = 0;
for (int e = head[p]; e != 0; e = edges[e].next)
{
int to = edges[e].to, vol = edges[e].w;
if (vol > 0 && dis[to] > dis[p] + edges[e].c)
{
dis[to] = dis[p] + edges[e].c;
if (!inq[to])
{
Q.push(to);
inq[to] = 1;
}
}
}
}
return dis[t] != INF;
}
int dfs(int p = s, int flow = INF)
{
if (p == t)
return flow;
vis[p] = 1;
int rmn = flow;
for (int eg = cur[p]; eg && rmn; eg = edges[eg].next)
{
cur[p] = eg;
int to = edges[eg].to, vol = edges[eg].w;
if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c)
{
int c = dfs(to, min(vol, rmn));
rmn -= c;
edges[eg].w -= c;
edges[eg ^ 1].w += c;
}
}
vis[p] = 0;
return flow - rmn;
}
int maxflow, mincost;
inline void run(int s, int t)
{
MCMF::s = s, MCMF::t = t;
while (SPFA())
{
int flow = dfs();
maxflow += flow;
mincost += dis[t] * flow;
}
}
void init()
{
maxflow = mincost = 0;
mms(head, 0);
// mms(edges, 0);
cnt = 1;
}
} // namespace MCMF
int n;
pii eg[N];
vector<int> g[N], vec[N];
int dp[N][N];
bool vis[N];
void tagvis(int x)
{
vis[x] = true;
for (auto v : vec[x])
{
if (!vis[v])
tagvis(v);
}
}
void buildtree(int x, int fa)
{
g[x].clear();
for (auto v : vec[x])
{
if (v == fa)
continue;
g[x].push_back(v);
buildtree(v, x);
}
}
void calc(int x, int y)
{
if (dp[x][y] != -1)
return;
for (auto u : g[x])
{
for (auto v : g[y])
calc(u, v);
}
MCMF::init();
for (auto u : g[x])
{
MCMF::addEdge(n + 1, u, 1, 0);
}
for (auto v : g[y])
MCMF::addEdge(v, n + 2, 1, 0);
for (auto u : g[x])
{
for (auto v : g[y])
{
MCMF::addEdge(u, v, 1, -dp[u][v]);
}
}
MCMF::run(n + 1, n + 2);
dp[x][y] = (-MCMF::mincost) + 1;
}
void solve()
{
cin >> n;
rep(i, 1, n)
{
cin >> eg[i].first;
eg[i].first++;
}
cin >> n;
rep(i, 1, n)
{
cin >> eg[i].second;
eg[i].second++;
}
n++;
int res = 0;
rep(i, 1, n - 1)
{
rep(j, 1, n)
{
vec[j].clear();
g[j].clear();
vis[j] = false;
}
rep(j, 1, n - 1)
{
if (i == j)
continue;
vec[eg[j].first].push_back(eg[j].second);
vec[eg[j].second].push_back(eg[j].first);
}
tagvis(1);
buildtree(1, 0);
rep(j, 1, n)
{
if (vis[j])
continue;
mms(dp, -1);
buildtree(j, 0);
rep(k, 1, n)
{
if (vis[k])
{
calc(k, j);
res = max(res, dp[k][j]);
}
}
}
}
cout << res << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}