相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/12/DeerInZooDivOne.html
中文题面：http://paste.ubuntu.com/23693088/
官方题解：https://apps.topcoder.com/wiki/display/tc/SRM+578
解题报告
给定一棵树，让你求两个没有重叠部分的连通块，使得这个连通块同构
这样的话，真的是不会啊！
直接说正解吧！
枚举将两个连通块分开的那条边
定义 \(f(i,j)\) 为以i的子树和j的子树最大同构部分有多大
不难发现答案就是 \(\max (f(i,j))\)
考虑如何求 \(f(i,j)\)：
递归处理的话，实际上就是将两个节点的儿子进行配对
于是搞在这里搞二分图带权匹配就可以啦！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 60;
const int M = 100000;
const int INF = 1e9;
int n,m,S,T;
class Minimum_Cost_Flow{
int head[N],nxt[M],to[M],flow[M],cost[M];
int E,vout,dis[N],sur[N],inq[N];
queue<int> que;
public:
inline void init() {
E = 1; S = 0; T = N - 1;
memset(head,0,sizeof(head));
}
inline void Add_Edge(int u, int v, int f, int c) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}
inline int MaxFlow() {
vout = 0;
for (int f=INF,w;SPFA();f=INF) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
vout += dis[T] * f;
}
return vout;
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;
class DeerInZooDivOne {
int ret,t1,t2,q1[N],q2[N],fa[N],f[N][N];
int E,head[N],to[M],nxt[M],vis[N];
public:
int getmax(vector<int> a, vector<int> b) {
n = a.size(); init();
for (int i=0;i<n;i++)
Add_Edge(a[i]+1, b[i]+1);
for (int i=0;t1=t2=0,i<n;i++) {
DFS(a[i]+1, b[i]+1, q1, t1);
DFS(b[i]+1, a[i]+1, q2, t2);
vis[i*2+1] = vis[(i+1)*2] = 1;
for (int p1=1;p1<=t1;p1++) {
Make_Root(q1[p1], q1[p1]);
for (int p2=1;p2<=t2;p2++) {
Make_Root(q2[p2], q2[p2]);
memset(f,-1,sizeof(f));
ret = max(ret, F(q1[p1], q2[p2]));
}
}
vis[i*2+1] = vis[(i+1)*2] = 0;
}
return ret;
}
private:
inline void init() {
E = 0; ret = 1;
memset(head,0,sizeof(head));
}
inline void Add_Edge(int u, int v) {
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
void DFS(int w, int f, int *arr, int &cnt) {
arr[++cnt] = w;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
DFS(to[i], w, arr, cnt);
}
}
}
void Make_Root(int w, int f) {
fa[w] = f;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[i]) {
Make_Root(to[i], w);
}
}
}
inline int F(int a, int b) {
if (a > b) swap(a, b);
if (~f[a][b]) return f[a][b];
else {
for (int i=head[a];i;i=nxt[i]) {
if (to[i] != fa[a] && !vis[i]) {
for (int j=head[b];j;j=nxt[j]) {
if (to[j] != fa[b] && !vis[j]) {
F(to[i], to[j]);
}
}
}
}
MCMF.init();
for (int i=head[a];i;i=nxt[i]) {
if (to[i] != fa[a] && !vis[i]) {
MCMF.Add_Edge(S, to[i], 1, 0);
for (int j=head[b];j;j=nxt[j]) {
if (to[j] != fa[b] && !vis[j]) {
MCMF.Add_Edge(to[i], to[j], 1, -F(to[i], to[j]));
}
}
}
}
for (int i=head[b];i;i=nxt[i]) {
if (to[i] != fa[b] && !vis[i]) {
MCMF.Add_Edge(to[i], T, 1, 0);
}
}
f[a][b] = -MCMF.MaxFlow();
return ++f[a][b];
}
}
};
Hello, Neat post. There is a problem with your site in web explorer, would test this?
IE nonetheless is the marketplace leader and a good section of other people will miss your fantastic writing because
of this problem.
I read this post fully about the resemblance of most recent and earlier technologies, it’s awesome article.
What’s up, all the time i used to check blog posts here
in the early hours in the morning, for the reason that i
love to gain knowledge of more and more.
Having read this I thought it was very informative.
I appreciate you spending some time and effort to put this informative article together.
I once again find myself spending a significant amount of time both reading and commenting.
But so what, it was still worth it!
After exploring a few of the blog posts on your web page, I seriously appreciate your technique of writing a blog.
I bookmarked it to my bookmark webpage list
and will be checking back soon. Please check out my website too
and tell me your opinion.
Piece of writing writing is also a excitement, if you be acquainted with
after that you can write if not it is complex to write.
You should be a part of a contest for one of the greatest blogs on the web.
I am going to recommend this web site!
WOW just what I was looking for. Came here by searching
for coconut oil
I got this web site from my pal who told me regarding this website and now this time I am visiting this site and reading very informative
articles at this time.
I am constantly invstigating online for posts that can help me. Thanks!
Everything is very open with a very clear description of the issues.
It was truly informative. Your website is useful.
Many thanks for sharing!
Hello, i read your blog from time to time and i own a
similar one and i was just curious if you get a lot of spam responses?
If so how do you protect against it, any plugin or anything you can recommend?
I get so much lately it’s driving me mad so any assistance is very much appreciated.
Keep on working, great job!
hi!,I really like your writing so so much! percentage we be in contact extra about your article on AOL?
I require a specialist on this house to unravel my problem.
Maybe that’s you! Looking ahead to peer you.
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my
newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to
your new updates.
Hello, yes this paragraph is really good and I have learned lot of things from it regarding blogging.
thanks.
My brother suggested I might like this web site.
He was totally right. This post actually made my day. You can not
imagine just how much time I had spent for this information! Thanks!
Superb, what a weblog it is! This web site presents
useful data to us, keep it up.
Hmm is anyone else experiencing problems with the pictures on this blog loading? I’m trying to figure out if its a problem on my end or if it’s the blog. Any feedback would be greatly appreciated.