洛谷P3296 刺客信条
2024-10-07 23:35:49
题意：
给你一棵树，有两组01权值a[]和b[]。n <= 700
你要构造一个自己到自己的映射，使得整棵树的形态不变，且映射后的a[]和映射之前的b[]中不同元素尽量少。
解：
发现这个整棵树形态不变......我们可能要用到树hash。
有个结论就是两棵树同构，当且仅当以它们重心为根的时候hash值相同。有两个重心就新建一个虚重心。
于是我们把重心搞出来当根，考虑映射之后的树，如果a映射到了b，那么a和b一定深度相同且hash值相同。
于是我们就按照深度分层，每层枚举点对，用f[a][b]来表示把点a映射到点b，子树内最少的不同元素。
于是如何求f[a][b]？发现我们要给a和b的若干个子节点进行匹配，要求权值最小。二分图匹配即可。我采用费用流实现。
复杂度：O(n³ + n * 网络流)，这个复杂度是我猜的...
#include <bits/stdc++.h>
const int N = , MO = , INF = 0x3f3f3f3f;
struct Edge {
int nex, v;
bool del;
}edge[N << ]; int tp = ;
int f[N][N], n, e[N], siz[N], val[N], h[N], aim[N], p[], top, small, root, root2, in_e[N], lm, in[N], d[N];
bool vis[];
std::vector<int> v[N];
inline void getp(int n) {
for(int i = ; i <= n; i++) {
if(!vis[i]) {
p[++top] = i;
}
for(int j = ; j <= top && i * p[j] <= n; j++) {
vis[i * p[j]] = ;
if(i % p[j] == ) {
break;
}
}
}
return;
}
inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].del = ;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void getroot(int x, int f) {
int large = ;
siz[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) {
continue;
}
in_e[y] = i;
getroot(y, x);
siz[x] += siz[y];
large = std::max(large, siz[y]);
}
large = std::max(large, n - siz[x]);
if(large < small) {
root = x;
root2 = ;
small = large;
}
else if(large == small) {
root2 = x;
}
return;
}
void DFS_1(int x, int f) {
d[x] = d[f] + ;
v[d[x]].push_back(x);
lm = std::max(lm, d[x]);
h[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f || edge[i].del) {
continue;
}
DFS_1(y, x);
siz[x] += siz[y];
h[x] = (h[x] + 1ll * h[y] * p[siz[y]] % MO) % MO;
}
return;
}
namespace fl {
struct Edge {
int nex, v, c, len;
Edge(int N = , int V = , int C = , int L = ) {
nex = N;
v = V;
c = C;
len = L;
}
}edge[]; int tp = ;
int e[N], d[N], vis[N], Time, pre[N], flow[N], n, tot;
std::queue<int> Q;
inline void add(int x, int y, int z, int w) {
//printf("addedge : x = %d y = %d z = %d w = %d \n", x, y, z, w);
edge[++tp] = Edge(e[x], y, z, w);
e[x] = tp;
edge[++tp] = Edge(e[y], x, , -w);
e[y] = tp;
return;
}
inline bool SPFA(int s, int t) {
vis[s] = Time;
memset(d + , 0x3f, tot * sizeof(int));
flow[s] = INF;
d[s] = ;
Q.push(s);
while(Q.size()) {
int x = Q.front();
Q.pop();
vis[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(d[y] > d[x] + edge[i].len && edge[i].c) {
d[y] = d[x] + edge[i].len;
flow[y] = std::min(edge[i].c, flow[x]);
pre[y] = i;
if(vis[y] != Time) {
vis[y] = Time;
Q.push(y);
}
}
}
}
return d[t] < INF;
}
inline void update(int s, int t) {
int f = flow[t];
while(s != t) {
int i = pre[t];
edge[i].c -= f;
edge[i ^ ].c += f;
t = edge[i ^ ].v;
}
return;
}
inline int solve(int x, int y) {
int ans = , cost = ;
n = in[x] - (x != root);
int s = * n + , t = tot = s + ;
//printf("solve : x = %d y = %d n = %d \n", x, y, n);
memset(e + , , tot * sizeof(int));
tp = ;
for(int i = ::e[x], cnt1 = ; i; i = ::edge[i].nex, ++cnt1) {
int u = ::edge[i].v;
//printf("u = %d \n", u);
if(::d[u] < ::d[x] || ::edge[i].del) {
--cnt1;
continue;
}
add(s, cnt1, , );
add(cnt1 + n, t, , );
for(int j = ::e[y], cnt2 = ; j; j = ::edge[j].nex, ++cnt2) {
int v = ::edge[j].v;
//printf(" v = %d \n", v);
if(::d[v] < ::d[y] || ::edge[j].del) {
--cnt2;
continue;
}
/// u v
if(f[u][v] > -INF) {
add(cnt1, n + cnt2, , f[u][v]);
}
}
}
++Time;
while(SPFA(s, t)) {
//printf("inside --------------------- \n");
ans += flow[t];
cost += flow[t] * d[t];
update(s, t);
++Time;
}
//printf("ans = %d cost = %d \n", ans, cost);
if(ans != n) {
return -INF;
}
else {
return cost + (val[x] != aim[y]);
}
}
}
int main() {
scanf("%d", &n);
for(int i = , x, y; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
in[x]++;
in[y]++;
}
for(int i = ; i <= n; i++) {
scanf("%d", &val[i]);
}
for(int i = ; i <= n; i++) {
scanf("%d", &aim[i]);
}
root = root2 = ;
small = N;
getroot(, );
//printf("root 1 = %d root 2 = %d \n", root, root2);
if(root2) {
++n;
int i;
if(edge[in_e[root] ^ ].v == root2) {
i = in_e[root];
}
else {
i = in_e[root2];
}
edge[i].del = edge[i ^ ].del = ;
add(n, root);
add(n, root2);
root = n;
in[n] = ;
}
///
//printf("root = %d \n", root);
DFS_1(root, );
for(int d = lm; d >= ; d--) {
int len = v[d].size();
for(int i = ; i < len; i++) {
int x = v[d][i];
for(int j = ; j < len; j++) {
int y = v[d][j];
if(in[x] != in[y] || h[x] != h[y]) {
f[x][y] = -INF;
//printf("1 : ");
}
else {
//f[x][y] = KM::solve(x, y);
f[x][y] = fl::solve(x, y);
//printf("2 : ");
}
//printf("f %d %d = %d \n", x, y, f[x][y]);
}
}
}
printf("%d\n", f[root][root]);
return ;
}
AC代码
最新文章
- com.panie 项目开发随笔（NoF）_环境搭建（2016.12.29）
- Centos7上启动vpn客户端失败问题处理
- Android Saving Data(二)
- 2016.8.16 JQuery学习记录
- python走起之第三话
- 炫酷的时钟--canvas初体验
- 推荐一款超强大的基于Angularjs的自动完成(Autocomplete)标签及标签组插件–ngTagsInput
- 使用ASIHttoRequest需要导入的framework
- Win7 “Bluetooth设置”对话框无法打开，及无法查找到设备
- 利用alias在Linux下设置命令别名
- Java的数组，栈，队列
- VS2015秘钥
- CodeForces 509C Sums of Digits（贪心乱搞）题解
- 【OData】使用Odata获取数据之后再次获取可能得不到最新的数据问题记录
- 深度学习在CTR预估中的应用
- fc26 url
- 版本号控制-git(二)
- iOS开发ApplePay的介绍与实现
- 主存和cache的地址映射
- iOS:图片上传时两种图片压缩方式的比较