省流：不看题导致我瞎搓出来了这个题。所以别问咋想到的，我也不知道。
题意：有三个长度为 \(n\) 的序列 \(a,b,c\)，你需要对于 \(i=1\to n\)，从 \(a_i,b_i\) 中必须选一个数加入 \(S\)，从 \(a_i,c_i\) 中必须选一个数加入 \(T\)，要求最后 \(S=T\)，这里集合是去重的，不是可重集。最大化 \(|S|\) 且给出构造。
做法：
首先看完题，我直接忽略了有构造这个事情。然后直接考虑，这大概就是每个位置要选一个出来，那就左侧源点对每个位置连 \(1\) 流量，然后对 \(a_i,b_i\) 分别连，右侧汇点对称对 \(a_i,c_i\) 连，中间对应的值连起来，边权都为 \(1\)，然后感觉自己已经做完了，翻开题解看了一圈，怎么都这么长。
跟 FLY_lai 讲了这个做法之后他震惊我是怎么直接跳到这一步来的，问了他我才知道这个东西存在一些问题，比如对于一个流，有些 \(i\) 是没有选定的，但是题目要求必须选，这样就爆炸了。根本没有意识到要构造且必须选这个事情直接让我意外搓出了正解的重要一步吗，有点意思。
那么最后怎么做呢？我们考虑调整一下这个解的形态。假设我现在答案的集合为 \(S\)，我们把 \(a_i,b_i,c_i\) 中属于 \(S\) 的可以直接确定选择哪一个，剩下一些没有确定的。假设 \(a_i,b_i\not\in S\)，那么这里 \(c_i\) 一定属于 \(S\)，否则我两边同时选 \(a_i\) 可以得到一个更大的集合。我们考虑把这个位置的 \(c_i\) 直接替换成在两个集合中都选择 \(a_i\)，然后把 \(c_i\) 扔掉。那么此时 \(c_i\) 就被我们从 \(S\) 中清除掉，我们也删掉那些选了值为 \(c_i\) 点。然后重复这个先加入，再强制交换的过程。首先这样做一定是合法的，不会影响答案的。其次，我们注意到这样调整完之后，\(S,T\) 中 \(i\) 对两个集合都选 \(a_i\) 的个数会越来越多，显然是不能超过 \(n\) 的，所以我们只会调整最多 \(n\) 轮，而一次调整是 \(O(n)\) 的，所以复杂度 \(O(n^2)\)，可以通过。
好像有厉害的通过先跑出一个解再跑网络流的做法，没太学会，求看懂的大佬教教。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 5, N = 1e4;
struct Edge {int to, fl, rev;
};
struct Graph {vector<Edge> e[maxn];void add(int x, int y, int f) {e[x].push_back(Edge{y, f, e[y].size()});e[y].push_back(Edge{x, 0, e[x].size() - 1});}int dis[maxn], s, t;bool bfs() {queue<int> q;q.push(s);memset(dis, 0x3f, sizeof(dis));dis[s] = 0;while(!q.empty()) {int u = q.front(); q.pop();//cout << u << endl;for (int i = 0; i < e[u].size(); i++) {Edge v = e[u][i];//cout << u << " " << v.to << " " << v.fl << " " << dis[v.to] << " " << endl;if(v.fl && dis[v.to] > dis[u] + 1)dis[v.to] = dis[u] + 1, q.push(v.to);}}return dis[t] != dis[t + 1];}int maxflow, cur[maxn];int dfs(int u, int flow) {if(!flow || u == t)return flow;int use = 0;for (cur[u]; cur[u] < e[u].size(); cur[u]++) {Edge v = e[u][cur[u]];if(dis[v.to] == dis[u] + 1) {int f = dfs(v.to, min(flow - use, v.fl));e[u][cur[u]].fl -= f, e[v.to][v.rev].fl += f, use += f;if(use == flow)break;}}return use;}int dinic(int S, int T) {s = S, t = T;while(bfs())memset(cur, 0, sizeof(cur)), maxflow += dfs(s, 2e9);return maxflow;}
} G;
int n, a[maxn], b[maxn], c[maxn], p1[maxn], p2[maxn], use[maxn][2];
bool chk() {for (int i = 1; i <= n; i++)if(!p1[i] || !p2[i])return 0;return 1;
}
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 1; i <= n; i++)cin >> c[i];int s = 0, t = 2 * n + 2 * N + 1;for (int i = 1; i <= n; i++)G.add(s, i, 1), G.add(i, a[i] + n, 1), G.add(i, b[i] + n, 1);for (int i = 1; i <= N; i++)G.add(i + n, i + n + N, 1);for (int i = 1; i <= n; i++)G.add(i + n + 2 * N, t, 1), G.add(n + N + a[i], i + n + 2 * N, 1), G.add(n + N + c[i], i + n + 2 * N, 1);cout << G.dinic(s, t) << endl;for (int i = 1; i <= n; i++) {int pos = i;for (int j = 0; j < G.e[i].size(); j++) {Edge v = G.e[i][j];if(v.to != 0 && !v.fl)p1[i] = (v.to == a[i] + n ? 0 : 1) + 1;}pos = i + 2 * N + n;for (int j = 0; j < G.e[pos].size(); j++) {Edge v = G.e[pos][j];if(v.to != t && v.fl)p2[i] = (v.to == a[i] + n + N ? 0 : 1) + 1;}if(p1[i])use[(p1[i] == 1 ? a[i] : b[i])][0]++;if(p2[i])use[(p2[i] == 1 ? a[i] : c[i])][1]++;// cout << p1[i] << " " << p2[i] << endl;}while(!chk()) {for (int i = 1; i <= n; i++) {if(!p1[i]) {if(use[a[i]][1])use[a[i]][0]++, p1[i] = 1;else if(use[b[i]][1])use[b[i]][0]++, p1[i] = 2;}if(!p2[i]) {if(use[a[i]][0])use[a[i]][1]++, p2[i] = 1;else if(use[c[i]][0])use[c[i]][1]++, p2[i] = 2;}}for (int i = 1; i <= n; i++) {if(!p1[i]) {p1[i] = p2[i] = 1;use[a[i]][0]++, use[a[i]][1]++, use[c[i]][1]--;if(!use[c[i]][1]) {for (int j = 1; j <= n; j++) {if(!p1[j])continue;int t = (p1[j] == 1 ? a[j] : b[j]);if(!use[t][1])p1[j] = 0, use[t][0]--;}}break;}if(!p2[i]) {p1[i] = p2[i] = 1;use[a[i]][0]++, use[a[i]][1]++, use[b[i]][0]--;if(!use[b[i]][0]) {for (int j = 1; j <= n; j++) {if(!p2[j])continue;int t = (p2[j] == 1 ? a[j] : c[j]);if(!use[t][0])p2[j] = 0, use[t][1]--;}}break;}}}for (int i = 1; i <= N; i++)if(use[i][0])cout << i << " ";cout << endl;return 0;
}