http://cplusoj.com/d/senior/p/SS231024D
It is equivalent to selecting some replacement rings to perform a displacement.
We consider only replacing A. For a ring of size > 1, if you shift it, you can definitely make the bits completely different.
So if we permute B, what is the significance of the permutation? It counts the positions of self-loops in A to make these positions different.
But if we replace B again, it may be the same as the previously replaced A in some places, and this part needs to be subtracted. This prompts us to use network streaming.
Before that, we can first prove a conclusion. For each position, we can always have at least one of its replacement ring A or replacement ring B replaced.
So either A is chosen, B is chosen, or AB is chosen together. For the problem of selecting things, it is difficult to maintain directly using network streams, so consider the minimum cut.
We’re going to use the minimum cut. We found that it is a bit difficult to minimize the same position directly, so consider the reverse. We first make all positions different and then make them the same. (That is, start selecting all)
We found that this looks like a bipartite graph. Let’s consider S->A, which means A is not selected. A->B means to choose both. B->T is the same.
All initial positions are different, we directly let the answer be
∑
s
z
e
\sum sze
∑sze, which is the size of all substitution rings in A and B (non-self rings)
But this obviously has weight, so it only makes sense for us to minimize it. If we cut A, it means we can only choose B. Cutting B means that you can only choose A. It seems to correspond?
The cost of cutting in the middle is equivalent to choosing both, so it should be the size of the repeated part + the size of the same part.
It should not be calculated because the two displacements are the same.
#include<bits/stdc + + .h>
using namespace std;
namespace atcoder {<!-- -->
namespace internal {<!-- -->
\t
template <class T> struct simple_queue {<!-- -->
std::vector<T> payload;
int pos = 0;
void reserve(int n) {<!-- --> payload.reserve(n); }
int size() const {<!-- --> return int(payload.size()) - pos; }
bool empty() const {<!-- --> return pos == int(payload.size()); }
void push(const T & amp; t) {<!-- --> payload.push_back(t); }
T & amp; front() {<!-- --> return payload[pos]; }
void clear() {<!-- -->
payload.clear();
pos = 0;
}
void pop() {<!-- --> pos + + ; }
};
\t
} // namespace internal
template <class Cap> struct mf_graph {<!-- -->
public:
mf_graph() : _n(0) {<!-- -->}
explicit mf_graph(int n) : _n(n), g(n) {<!-- -->}
\t
int add_edge(int from, int to, Cap cap) {<!-- -->
assert(0 <= from & amp; & amp; from < _n);
assert(0 <= to & amp; & amp; to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({<!-- -->from, int(g[from].size())});
// printf("%lld -> %lld | %lld\\
", from, to, cap);
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id + + ;
g[from].push_back(_edge{<!-- -->to, to_id, cap});
g[to].push_back(_edge{<!-- -->from, from_id, 0});
return m;
}
\t
struct edge {<!-- -->
int from, to;
Cap cap, flow;
};
\t
edge get_edge(int i) {<!-- -->
int m = int(pos.size());
assert(0 <= i & amp; & amp; i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{<!-- -->pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {<!-- -->
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i + + ) {<!-- -->
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {<!-- -->
int m = int(pos.size());
assert(0 <= i & amp; & amp; i < m);
assert(0 <= new_flow & amp; & amp; new_flow <= new_cap);
auto & amp; _e = g[pos[i].first][pos[i].second];
auto & _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
\t
Cap flow(int s, int t) {<!-- -->
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {<!-- -->
assert(0 <= s & amp; & amp; s < _n);
assert(0 <= t & amp; & amp; t < _n);
assert(s != t);
\t
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int>que;
\t
auto bfs = [ & amp;]() {<!-- -->
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {<!-- -->
int v = que.front();
que.pop();
for (auto e : g[v]) {<!-- -->
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [ & amp;](auto self, int v, Cap up) {<!-- -->
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int & amp; i = iter[v]; i < int(g[v].size()); i + + ) {<!-- -->
_edge & e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap + = d;
g[e.to][e.rev].cap -= d;
res + = d;
if (res == up) return res;
}
level[v] = _n;
return res;
};
\t
Cap flow = 0;
while (flow < flow_limit) {<!-- -->
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow + = f;
}
return flow;
}
\t
std::vector<bool> min_cut(int s) {<!-- -->
std::vector<bool> visited(_n);
internal::simple_queue<int>que;
que.push(s);
while (!que.empty()) {<!-- -->
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {<!-- -->
if (e.cap & amp; & amp; !visited[e.to]) {<!-- -->
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
\t
private:
int _n;
struct _edge {<!-- -->
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
} // namespace atcoder
using namespace atcoder;
//#define int long long
inline int read(){<!-- -->int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){<!-- -->if(ch=='-')f=-1;ch=getchar();}while(ch>='0' & amp; & amp;ch<='9'){<!-- -->
x=(x<<1) + (x<<3) + (ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
//#define mo
int n, m, i, j, k, T;
int S, a[N], b[N], ans;
int A[N], B[N], wa[N], wb[N];
map<pair<int, int>, int>mp;
int fa(int x) {<!-- -->
if(A[x]==x) return x;
return A[x]=fa(A[x]);
}
int fb(int x) {<!-- -->
if(B[x]==x) return x;
return B[x]=fb(B[x]);
}
signed main()
{<!-- -->
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
freopen("permutation.in", "r", stdin);
freopen("permutation.out", "w", stdout);
// T=read();
// while(T--) {<!-- -->
//
// }
n=read(); ans=0;
mf_graph<int>G(2*n + 10); S=2*n + 1; T=2*n + 2;
for(i=1; i<=n; + + i) A[i]=B[i]=i;
for(i=1; i<=n; + + i) a[i]=read(), A[fa(i)]=fa(a[i]);
for(i=1; i<=n; + + i) b[i]=read(), B[fb(i)]=fb(b[i]);
for(i=1; i<=n; + + i) wa[fa(i)] + + , wb[fb(i)] + + ;
// for(i=1; i<=n; + + i) printf("%d ", wa[i]); printf("\\
");
// for(i=1; i<=n; + + i) printf("%d ", wb[i]); printf("\\
");
for(i=1; i<=n; + + i) {<!-- -->
if(fa(i)==i & amp; & amp; wa[i]>1) G.add_edge(S, i, wa[i]), ans + =wa[i];
if(fb(i)==i & amp; & amp; wb[i]>1) G.add_edge(i + n, T, wb[i]), ans + =wb[i];
}
for(i=1; i<=n; + + i) {<!-- -->
+ + mp[{<!-- -->fa(a[i]), fb(b[i])}];
if(a[i]==b[i]) + + mp[{<!-- -->fa(a[i]), fb(b[i])}];
}
for(i=1; i<=n; + + i) {<!-- -->
auto & amp;k = mp[{<!-- -->fa(a[i]), fb(b[i])}];
if(k)
G.add_edge(fa(a[i]), fb(b[i]) + n, k), k=0;
}
k=G.flow(S, T); ans-=k;
printf("%d", n-ans);
return 0;
}