【二分图最大独立集】子集

二分图, 图论

传送门：LOJ526

思路：

将不能在同一子集中的点连边后，求最大独立集；

由于只有奇偶性不同的点间可以连边，所以图是二分图，

求完匹配以后用总点数减去即可。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define N 50000
#define INF 0x3fffffff
LL n,s,t,tot,a[N],level[N],head[N],iter[N],q[N];
struct edge{LL v,cap,rev,nxt;}e[N*2];
LL gcd(LL x,LL y){return y==0?x:gcd(y,x%y);}
void add(int x,int y,int z){
	e[++tot].v=y; e[tot].cap=z; e[tot].rev=tot+1; e[tot].nxt=head[x]; head[x]=tot;
	e[++tot].v=x; e[tot].cap=0; e[tot].rev=tot-1; e[tot].nxt=head[y]; head[y]=tot;
}
void bfs(LL s){
	LL tt=0,ww=1; level[s]=0; q[1]=s;
	while (tt<ww){
		LL v=q[++tt];
		for (LL i=head[v];i;i=e[i].nxt)
			if (e[i].cap>0 && level[e[i].v]==-1){
				level[e[i].v]=level[v]+1; q[++ww]=e[i].v;
			}
		}
}
			
LL dfs(LL v,LL t,LL flow){
	if (v==t) return flow;
	for (LL &i=iter[v];i;i=e[i].nxt)
		if (e[i].cap>0 && level[e[i].v]>level[v]){
			LL d=dfs(e[i].v,t,min(flow,e[i].cap));
			if (d>0){e[i].cap-=d; e[e[i].rev].cap+=d; return d;}
		}
	return 0;
}
LL dinic(LL s,LL t){
	LL flow=0;
	for(;;){
		memset(level,-1,sizeof level); bfs(s);
		if (level[t]<0) return flow;
		for (LL i=s;i<=t;i++) iter[i]=head[i];
		LL f=0;
		while ((f=dfs(s,t,INF))>0) flow+=f;
	}
}
int main(){
	scanf("%lld",&n); s=0; t=n+1;
	for (LL i=1;i<=n;i++){scanf("%lld",&a[i]); if (a[i]&1) add(s,i,1); else add(i,t,1);}
	for (LL i=1;i<=n;i++)
		for (LL j=i+1;j<=n;j++) if (gcd(a[i],a[j])*gcd(a[i]+1,a[j]+1)==1){if (a[i]&1) add(i,j,1); else add(j,i,1);}
		
	printf("%lld",n-dinic(s,t));
	
	return 0;
}