二次联通门 : LibreOJ #526. 「LibreOJ β Round #4」子集
/*
LibreOJ #526. 「LibreOJ β Round #4」子集 考虑一下，若两个数奇偶性相同
若同为奇数, 那加1后就是偶数, gcd的乘积就一定不是1
偶数相同 那么我们把原数中的偶数分为一个集合，奇数分为一个集合
把互相之间不符合要求的连边 那么问题就转化为了二分图求最大独立集
*/
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring> const int BUF = ;
char Buf[BUF], *buf = Buf;
#define INF 1e9
inline void read (long long &now)
{
for (now = ; !isdigit (*buf); ++ buf);
for (; isdigit (*buf); now = now * + *buf - '', ++ buf);
} #define Max 600
struct E { E *n, *r; int v, f; };
E *list[Max], poor[Max * ], *Ta = poor;
int S, T; class Flow_Type
{
private : int d[Max]; bool Bfs (int S, int T)
{
memset (d, -, sizeof d); d[S] = ;
std :: queue <int> Queue; int now; E *e;
for (Queue.push (S); !Queue.empty (); Queue.pop ())
{
now = Queue.front ();
for (e = list[now]; e; e = e->n)
if (d[e->v] == - && e->f)
{
d[e->v] = d[now] + ;
if (e->v == T) return true;
Queue.push (e->v);
}
}
return d[T] != -;
} int Flowing (int now, int F)
{
if (now == T || !F) return F;
int res = , pos; E *e;
for (e = list[now]; e; e = e->n)
{
if (d[e->v] != d[now] + || !e->f) continue;
pos = Flowing (e->v, e->f < F ? e->f : F);
if (pos)
{
F -= pos, res += pos, e->f -= pos, e->r->f += pos;
if (!F) return res;
}
}
if (res != F) d[now] = -;
return res;
} public : inline void In (int u, int v)
{
++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta, Ta->f = ;
++ Ta, Ta->v = u, Ta->n = list[v], list[v] = Ta, Ta->f = ;
list[u]->r = list[v], list[v]->r = list[u];
} int Dinic (int S, int T)
{
int Answer = ;
for (; Bfs (S, T); Answer += Flowing (S, INF));
return Answer;
}
}; Flow_Type F;
long long key[Max];
long long Gcd (long long a, long long b) { return !b ? a : Gcd (b, a % b); }
int Main ()
{
fread (buf, , BUF, stdin);
long long N; read (N); S = N + , T = N + ;
register int i, j;
for (i = ; i <= N; ++ i)
{
read (key[i]);
if (key[i] & ) F.In (i, T);
else F.In (S, i);
}
for (i = ; i <= N; ++ i)
{
if ((key[i] & ) == )
for (j = ; j <= N; ++ j)
if (key[j] & )
if (Gcd (key[i], key[j]) == && Gcd (key[i] + , key[j] + ) == )
F.In (i, j);
} printf ("%d", N - F.Dinic (S, T)); return ;
} int ZlycerQan = Main ();
int main (int argc, char *argv[]) {;}