网络流+先跑一遍确保正确性：ARC156F

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135209595

https://www.luogu.com.cn/problem/AT_arc156_f

可以很显然建一个流：

在这里插入图片描述

然而它最大流是对的，但构造方案可能会假，因为存在最左边的边没流，相当于某个数没选。

一定有解是怎样？全选 aia_i ，所以我们可以先全选 aia_i 跑。然后我们再加入 bi,cib_i,c_i 来跑，那样反悔一定不会反悔到最左边的边上。

1
2
3
4
5
pre coding at 21:01
st coding at 21:11
st bugging at 21:18
passing at 21:25
fn blogging at 21:33
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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#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
#define fi first
#define se second
//srand(time(0));
#define N 400010
//#define M
//#define mo
namespace Flow {
	#define int long long
	struct mf_graph {
		struct node {
			int x, y, z, n; 
		}; 
		vector<node>d; 
		vector<int>h, H, dep; 
		queue<int>q; 
		int k; 
		int u, v, w, S, T, ans=0; 
		void reset(int n) {
			h.resize(n+5); k=1; d.resize(2); 
			H.resize(n+5); dep.resize(n+5); 
		}
		void cun(int x, int y, int z) {
			++k; d.pb({x, y, z, h[x]}); 
			d[k].n=h[x]; h[x]=k;
		}
		int add_edge(int x, int y, int z) {
        	// debug("%lld -> %lld %lld\n", x, y, z); 
			cun(x, y, z); cun(y, x, 0); 
			return k-1; 
		}
		int get_edge(int k) { return d[k].z; }
		int bfs() {
			while(!q.empty()) q.pop(); 
			fill(dep.begin(), dep.end(), -1); 
			h=H; 
			dep[S]=1; q.push(S); 
			while(!q.empty()) {
				u=q.front(); q.pop(); 
				for(int g=h[u]; g; g=d[g].n) {
					v=d[g].y; w=d[g].z; 
					if(w<=0 || dep[v]!=-1) continue; 
					dep[v]=dep[u]+1; q.push(v); 
				}
			}
			return dep[T]!=-1; 
		}
		int dfs(int x, int w) {
			if(x==T) return w;
			if(!w) return 0; 
			int ans=0, s; 
			for(int &i=h[x]; i; i=d[i].n) {
				int y=d[i].y, z=d[i].z;  
				if(dep[y]!=dep[x]+1) continue; 
				if(z<=0) continue; 
				s=dfs(y, min(w, z)); ans+=s; w-=s; 
				d[i].z-=s; d[i^1].z+=s; 
				if(!w) break;  
			}
			return ans; 
		}
		int flow(int SS, int TT) {
			S=SS; T=TT; H=h; ans=0; 
			while(bfs()) ans+=dfs(S, 1e18); 
			return ans; 
		}
	}; 	
	#undef int
}
using namespace Flow; 
int n, m, i, j, k, T, S, tot;
int ans, L[N], R[N], a[N], p1[N], p2[N], qr[N]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	mf_graph G; G.reset(4e5); 
	n = read(); S = 1; T = tot = 2; 
	for(i=1; i<=1e5; ++i) L[i]=++tot, R[i]=++tot, qr[i]=G.add_edge(L[i], R[i], 1); 
	for(i=1; i<=n; ++i) {
		p1[i]=++tot, p2[i]=++tot; 
		G.add_edge(S, p1[i], 1); 
		G.add_edge(p2[i], T, 1); 
	}
	for(i=1; i<=n; ++i) {
		a[i]=read(); 
		G.add_edge(p1[i], L[a[i]], 1); 
		G.add_edge(R[a[i]], p2[i], 1); 
	}
	ans = G.flow(S, T); 
//	debug("%d\n", ans); 
	for(i=1; i<=n; ++i) {
		a[i]=read(); 
		G.add_edge(p1[i], L[a[i]], 1); 
//		G.add_edge(R[a[i]], p2[i], 1); 
	}
	for(i=1; i<=n; ++i) {
		a[i]=read(); 
//		G.add_edge(p1[i], L[a[i]], 1); 
		G.add_edge(R[a[i]], p2[i], 1); 
	}
	ans += G.flow(S, T); 
	printf("%d\n", ans); 
	for(i=1; i<=1e5; ++i) {
		k = G.get_edge(qr[i]); 
		if(!k) printf("%d ", i); 
	}
	return 0;
}