Bzoj3197/洛谷3296 [SDOI2013]刺客信条assassin（树的重心+树Hash+树形DP+KM）

题面

题解

（除了代码均摘自喻队的博客，可是他退役了）

首先固定一棵树,枚举另一棵树,显然另一棵树只有与这棵树同构才有可能产生贡献如果固定的树以重心为根,那么另一棵树最多就只有重心为根才有可能同构了(可能有两个) 然后就是求改动次数最小值,设$f[x][y]$表示以第一棵树$x$为根的子树内和第二棵树内$y$为根的子树内,达到目标最少需要改动的次数我们发现只有同构的子树需要决策,我们把同构的子树分别拿出来,我们要做的就是做一个匹配,跑一遍$KM$或者费用流就好了。因为要最小化$f[x][y]$，所以是跑最小完美匹配。 $f[x][y]$要记忆化一下,判断同构用树哈希即可

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

using std::sort; using std::vector;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 1.4e3 + 10, Inf = 1e9 + 7;

void upt0(int &x, int y) { if(x < y) x = y; }

void upt1(int &x, int y) { if(x > y) x = y; }

namespace KM {

	int n, w[N][N], match[N], ret, lx[N], ly[N];

	bool visx[N], visy[N];

	bool Hungary(int x) {

		visx[x] = 1;

		for(int y = 1; y <= n; ++y)

			if(!visy[y] && lx[x] + ly[y] == w[x][y]) {

				visy[y] = true;

				if(!match[y] || Hungary(match[y])) { match[y] = x; return 1; }

			}

		return 0;

	}

	int main(int opt) {

	    for(int i = 1; i <= n; ++i)

	        for(int j = 1; j <= n; ++j)

	            w[i][j] = opt * w[i][j];

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

			lx[i] = -Inf, ly[i] = 0;

			for(int j = 1; j <= n; ++j) upt0(lx[i], w[i][j]);

		}

		memset(match, 0, sizeof match);

		for(int x = 1; x <= n; ++x)

			while(1) {

				memset(visx, 0, sizeof visx), memset(visy, 0, sizeof visy);

				if(Hungary(x)) break;

				int inc = Inf;

				for(int i = 1; i <= n; ++i)

					if(visx[i])

						for(int j = 1; j <= n; ++j)

							if(!visy[j]) upt1(inc, lx[i] + ly[j] - w[i][j]);

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

					if(visx[i]) lx[i] -= inc;

					if(visy[i]) ly[i] += inc;

				}

			}

		for(int i = 1; i <= n; ++i)

			if(match[i]) ret += w[match[i]][i];

		return opt * ret;

	}

}//KM模板

int n, rt, fir[N], sec[N], f[N][N], c[N][N]; ll hash[N];

int from[N], cnt, to[N << 1], nxt[N << 1];

inline void addEdge(int u, int v) {

	to[++cnt] = v, nxt[cnt] = from[u], from[u] = cnt;

}

int tmp, siz[N];

vector<int> v1[N], v2[N];

inline bool cmp(const int &i, const int &j) { return hash[i] < hash[j]; }

void getrt(int u, int fa) {

	int max_part = 0; siz[u] = 1;

	for(int i = from[u]; i; i = nxt[i]) {

		int v = to[i]; if(v == fa) continue;

		getrt(v, u), siz[u] += siz[v], upt0(max_part, siz[v]);

	} upt0(max_part, n - siz[u]);

	if(max_part < tmp) tmp = max_part, rt = u;

}//寻找树的重心

void dfs(int u, int fa, vector<int> *V) {

	siz[u] = 1, hash[u] = 0, V[u].clear();

	for(int i = from[u]; i; i = nxt[i]) {

		int v = to[i]; if(v == fa) continue;

		dfs(v, u, V), siz[u] += siz[v], V[u].push_back(v);

	} sort(V[u].begin(), V[u].end(), cmp);

	for(int i = V[u].size() - 1; ~i; --i)

		hash[u] = hash[u] * N + hash[V[u][i]];

	hash[u] = hash[u] * N + siz[u];

}//处理各子树hash值以及儿子（将儿子放进一个vector里面）

int dp(int x, int y) {

	if(f[x][y] != -1) return f[x][y];

	f[x][y] = fir[x] ^ sec[y]; int lim = v1[x].size() - 1;

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

		int j = i;

		while(j < lim && hash[v1[x][j + 1]] == hash[v1[x][i]]) ++j;

		for(int k = i; k <= j; ++k)

			for(int l = i; l <= j; ++l)

				dp(v1[x][k], v2[y][l]);

		for(int k = i; k <= j; ++k)

			for(int l = i; l <= j; ++l)

				KM::w[k - i + 1][l - i + 1] = dp(v1[x][k], v2[y][l]);

        //初始化边权

		KM::ret = 0, KM::n = j - i + 1, f[x][y] += KM::main(-1), i = j;

        //最小化f[x][y]

	} return f[x][y];

}

int main () {

	read(n);

	for(int i = 1, u, v; i < n; ++i)

		read(u), read(v), addEdge(u, v), addEdge(v, u);

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

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

	tmp = Inf, getrt(1, 0), dfs(rt, 0, v2); ll tmp = hash[rt];

	int ans = Inf;

	for(int i = 1; i <= n; ++i) {//暴力枚举重心

		dfs(i, 0, v1);

		if(hash[i] == tmp) memset(f, -1, sizeof f), upt1(ans, dp(i, rt));

	} printf("%d\n", ans);

	return 0;

}

巴特西

Bzoj3197/洛谷3296 [SDOI2013]刺客信条assassin（树的重心+树Hash+树形DP+KM）

题面

题解

最新文章

热门文章