二分套网络流：ABC320G

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

首先肯定先枚举数字

然后考虑二分答案

每个字符串向它合法的位置连边

然后易发现每个点出度最多为 nn ，不然没意义

所以最多 O(n2)O(n^2) 条边

然后跑网络流，看能不能流完，也就是能不能匹配成功即可

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
#define M 200010
//#define mo
#define N 510
int n, m, i, j, k, T, ans=2e9;
char s[M]; 
int le[N][11], l, r, mid, c, tot; 
vector<int>v[N][11]; 
map<int, int>mp; 

int check(int T) {
	mf_graph<int>G(N*N); mp.clear(); tot=n; 

	for(i=1; i<=n; ++i) G.add_edge(N*N-2, i, 1); 
	for(i=1; i<=n; ++i) {
		for(j=0, k=0; j<=n; ++j) {
			k=v[i][c][j%le[i][c]]+m*(j/le[i][c]); 
			if(k>T) break; 
			if(!mp[k+n]) 
				mp[k+n]=++tot, G.add_edge(tot, N*N-1, 1); 
			G.add_edge(i, mp[k+n], 1); 
		}
	}
	if(G.flow(N*N-2, N*N-1, n)==n) return 1; 
	return 0; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=n; ++i) {
		scanf("%s", s); 
		for(j=0; s[j]; ++j) v[i][s[j]-'0'].pb(j); 
	}
	for(c=0; c<=9; ++c) for(i=1; i<=n; ++i) 
		le[i][c]=v[i][c].size(); 
	for(c=0; c<=9; ++c) {
		for(i=1; i<=n; ++i) if(!le[i][c]) break; 
		if(i<=n) continue; 
		l=n-1; r=1e9; 
		while(l<r) {
			mid=(l+r)>>1; 
			if(check(mid)) r=mid; 
			else l=mid+1; 
		}
		ans=min(ans, l); 
	}
	if(ans==2e9) printf("-1"); 
	else printf("%d", ans); 
	return 0;
}