分析性质+排列置换环+最小割：1024T4

http://cplusoj.com/d/senior/p/SS231024D

相当于各选一些置换环进行一次位移

我们考虑只对A进行置换。对于一个大小>1的环，如果对其进行位移，一定可以使这些位完全不同。

因此，如果我们置换B，置换的意义是什么？是把A中自环的位置统计掉，使这些位置不同。

但如果我们再置换B，可能会和之前已经置换的A在某些地方相同，这部分需要减去。这就提示我们要用网络流。

在此之前我们可以先证明一个结论，对于每个位置，我们总可以使其置换环A或置换环B至少有一个被换过。

所以要么A选，要么B选，要么AB同选。对于选东西的问题，直接用网络流很难维护，所以考虑最小割。

我们要用最小割。我们发现如果直接使相同位置最小有点难做，考虑反过来。我们先钦定所有位置不同，再使其变回相同。（也就是也开始全选）

我们发现这长得很像一个二分图形式。我们就考虑S->A，表示A不选。A->B，表示两个都选。B->T同理。

初始所有位置不同，我们直接令答案为 $\sum sze$，也就是A和B中所有置换环的大小（非自环）

但这显然有重，这样我们最小割才有意义。假如我们割A，代表只选B。割B，代表只选A，似乎对应上了？

割中间的代价，相当于两个都选，那么应该是重复部分大小+相同部分大小。

因为两个位移后相同也不应该计算。

#include
using namespace std;


namespace atcoder {

	namespace internal {
	
	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& t) { payload.push_back(t); }
	    T& front() { return payload[pos]; }
	    void clear() {
	        payload.clear();
	        pos = 0;
	    }
	    void pop() { pos++; }
	};
	
	}  // namespace internal

	template <class Cap> struct mf_graph {
	  public:
	    mf_graph() : _n(0) {}
	    explicit mf_graph(int n) : _n(n), g(n) {}
	
	    int add_edge(int from, int to, Cap cap) {
	        assert(0 <= from && from < _n);
	        assert(0 <= to && to < _n);
	        assert(0 <= cap);
	        int m = int(pos.size());
	        pos.push_back({from, int(g[from].size())});
//	        printf("%lld -> %lld | %lld\n", 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;
	    }
	
	    struct edge {
	        int from, to;
	        Cap cap, flow;
	    };
	
	    edge get_edge(int i) {
	        int m = int(pos.size());
	        assert(0 <= i && 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 && i < m);
	        assert(0 <= new_flow && new_flow <= new_cap);
	        auto& _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;
	    }
	
	    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 && s < _n);
	        assert(0 <= t && t < _n);
	        assert(s != t);
	
	        std::vector<int> level(_n), iter(_n);
	        internal::simple_queue<int> que;
	
	        auto bfs = [&]() {
	            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 = [&](auto self, int v, Cap up) {
	            if (v == s) return up;
	            Cap res = 0;
	            int level_v = level[v];
	            for (int& 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;
	        };
	
	        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;
	    }
	
	    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 && !visited[e.to]) {
	                    visited[e.to] = true;
	                    que.push(e.to);
	                }
	            }
	        }
	        return visited;
	    }
	
	  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'&&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("\n"); 
//	for(i=1; i<=n; ++i) printf("%d ", wb[i]); printf("\n"); 
	for(i=1; i<=n; ++i) {
		if(fa(i)==i && wa[i]>1) G.add_edge(S, i, wa[i]), ans+=wa[i]; 
		if(fb(i)==i && 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 &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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230