TopCoder SRM 578 Div1 Hard DeerInZooDivOne

問題

無向木Gが与えられる。
Gの部分誘導グラフの木H, Iであって、HとIは同型かつdisjointであるものについて、

H

+

I

の最大値を求めよ。

制約条件

G

≦50

部分誘導グラフは、部分グラフのうち辺を勝手に削除してはダメなやつ
（元のグラフにあった辺の両端の頂点が部分グラフに含まれるなら、部分グラフもその辺を含まなければならない）

方針

二つの木について、サイズ最大の部分グラフで互いに同型（の連結なやつ）を求めるのは、
再帰をすればいい。
rec(v1, p1, v2, p2) := 一つの木はv1を根として、もう一つはv2を根としているときの、サイズ最大値。

子iと子jを対応させるときのサイズはrec(childL[v1][i], v1, childR[v2][j], v2)で求まる。
これが求まれば、あとはどの子とどの子を対応させるのがベストかは、二部グラフの重み最大マッチングをすればよい。

で、元のグラフをどこかの辺で切断して二つの木にしてから、部分グラフを探すと考えればよい。
計算量がとても謎O(n^6)とかに見えてだめだと思ってチュートリアル見たんだけど、解法そのままで、何故か1.1sくらいで通る。

二つの木に分けたりすると結構実際のサイズは小さくなるっぽいけど見積もりが非常にしにくい。

ソースコード

class DeerInZooDivOne {
	public:
	
	int n;
	int dp[51][51][51][51];
	vector<vi> e;
	
	int rec(int v1, int p1, int v2, int p2){
		
		int &res = dp[v1][p1][v2][p2];
		if(res >= 0) return res;
		
		int l = 0, r = 0, ls[50], rs[50];
		each(i, e[v1]) if(*i != p1) ls[l++] = *i;
		each(i, e[v2]) if(*i != p2) rs[r++] = *i;
		
		int s = l + r, t = s + 1;
		costflowGraph<int> g(l + r + 2);
		
		
		rep(i, l) g.add(s, i, 1, 0);
		rep(i, r) g.add(i + l, t, 1, 0);
		
		rep(i, l) rep(j, r){
			g.add(i, j + l, 1, 100 - rec(ls[i], v1, rs[j], v2));
		}
		
		int f = min(l, r);
		return 100 * f - g.min_cost_flow(s, t, f) + 1;
	}
	
	int getmax(vector <int> a, vector <int> b) {
		
		n = a.size() + 1;
		int ans = 0;
		
		rep(notuse, n - 1){
			e.clear(); e.resize(n);
			
			rep(i, n - 1) if(i != notuse){
				e[a[i]].pb(b[i]);
				e[b[i]].pb(a[i]);
			}
			
			vi x, y;
			dfs(x, a[notuse], b[notuse]);
			dfs(y, b[notuse], a[notuse]);
			
			rep(i, x.size()) rep(j, x.size()) rep(k, y.size()) rep(l, y.size())
				dp[x[i]][x[j]][y[k]][y[l]] = -1;
			
			
			rep(i, x.size()) rep(j, y.size())
				ans = max(ans, rec(x[i], x[i], y[j], y[j]));
		}
		return ans;
	}
	
	void dfs(vi &v, int c, int p){
		v.pb(c);
		each(i, e[c]) if(*i != p) dfs(v, *i, c);
	}
};