弱省互测#2 t2

题意

给两个树，大小分别为n和m，现在两棵树各选一些点（包括1），使得这棵树以1号点为根同构（同构就是每个点的孩子数目相同），求最大的同构树。（n, m<=500）

分析

我们从两棵树中各取出一个点，考虑以这两个点为根能得到的最大同构数。

题解

容易得到：

设\(d(i, j)\)表示第一棵树选\(i\)号点，第二棵树选\(j\)号点所能得到的最大同构数。

那么\(d(i, j)\)就是等于从\(i\)这个点的子树选一些点，从\(j\)这个点的子树选一些点，选出的点数目相同，一一匹配，则答案就是这些点的\(\sum d(x, y)\)。

计算这个我们用最大费用流来计算。

同时我们从深度深的向深度浅的进行计算。

#include <bits/stdc++.h>

using namespace std;

const int N=505, M=N*2;

int ed[2][N][N], ecnt[2][N], n[2], ihead[M], cnt=1;

struct E {

	int next, from, to, cap, w;

}e[M*M];

void add(int x, int y, int cap, int w) {

	e[++cnt]=(E){ihead[x], x, y, cap, w}; ihead[x]=cnt;

	e[++cnt]=(E){ihead[y], y, x, 0,	 -w}; ihead[y]=cnt;

}

int d[M], p[M];

bool spfa(int s, int t, int n) {

	static bool vis[M];

	static int q[M], fr, ta;

	fr=ta=0;

	q[ta++]=s;

	memset(d, 0x7f, sizeof(int)*(n+1));

	d[s]=0;

	while(ta!=fr) {

		int x=q[fr++];

		vis[x]=0;

		fr=fr==M?0:fr;

		for(int i=ihead[x]; i; i=e[i].next) {

			if(!e[i].cap) {

				continue;

			}

			int y=e[i].to;

			if(d[y]>d[x]+e[i].w) {

				d[y]=d[x]+e[i].w;

				p[y]=i;

				if(!vis[y]) {

					vis[y]=1;

					if(d[y]<d[q[fr]]) {

						fr=fr==0?M:fr;

						q[--fr]=y;

					}

					else {

						q[ta++]=y;

						ta=ta==M?0:ta;

					}

				}

			}

		}

	}

	return d[t]!=0x7f7f7f7f;

}

void tadd(int x, int y, int w) {

	ed[w][x][ecnt[w][x]++]=y;

	ed[w][y][ecnt[w][y]++]=x;

}

int st[2][N][N], scnt[2][N], mxdep;

void dfs(int w, int x, int f, int dep) {

	st[w][dep][scnt[w][dep]++]=x;

	mxdep=max(dep, mxdep);

	int sz=0;

	for(int i=0; i<ecnt[w][x]; ++i) {

		int y=ed[w][x][i];

		if(y==f) {

			continue;

		}

		dfs(w, y, x, dep+1);

		ed[w][x][sz++]=y;

	}

	ecnt[w][x]=sz;

}

int f[N][N];

void work(int x, int y) {

	int c1=ecnt[0][x], c2=ecnt[1][y];

	int s=c1+c2+1, t=s+1;

	memset(ihead, 0, sizeof(int)*(t+1));

	cnt=1;

	for(int i=1; i<=c1; ++i) {

		add(s, i, 1, 0);

	}

	for(int i=1; i<=c2; ++i) {

		add(c1+i, t, 1, 0);

	}

	for(int i=0; i<c1; ++i) {

		for(int j=0; j<c2; ++j) {

			int y1=ed[0][x][i], y2=ed[1][y][j];

			add(i+1, c1+j+1, 1, -f[y1][y2]);

		}

	}

	int &now=f[x][y];

	now=1;

	while(spfa(s, t, t)) {

		int f=0x7f7f7f7f;

		for(int x=t; x!=s; x=e[p[x]].from) f=min(f, e[p[x]].cap);

		for(int x=t; x!=s; x=e[p[x]].from) e[p[x]].cap-=f, e[p[x]^1].cap+=f;

		now+=-f*d[t];

	}

}

void dfs(int dep) {

	if(dep<0) {

		return;

	}

	int c1=scnt[0][dep], c2=scnt[1][dep];

	for(int i=0; i<c1; ++i) {

		for(int j=0; j<c2; ++j) {

			work(st[0][dep][i], st[1][dep][j]);

		}

	}

	dfs(dep-1);

}

int main() {

	scanf("%d", &n[0]);

	for(int i=1; i<n[0]; ++i) {

		int x, y;

		scanf("%d%d", &x, &y);

		tadd(x, y, 0);

	}

	scanf("%d", &n[1]);

	for(int i=1; i<n[1]; ++i) {

		int x, y;

		scanf("%d%d", &x, &y);

		tadd(x, y, 1);

	}

	dfs(0, 1, 0, 0);

	dfs(1, 1, 0, 0);

	dfs(mxdep);

	printf("%d\n", f[1][1]);

	return 0;

}

巴特西

弱省互测#2 t2

题意

分析

题解

最新文章

热门文章