4205: 卡牌配对
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 173 Solved: 76
[Submit][Status][Discuss]
Description
现在有一种卡牌游戏，每张卡牌上有三个属性值：A,B,C。把卡牌分为X,Y两类，分别有n1,n2张。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
比如一张X类卡牌属性值分别是225,233,101，一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的，因为只有101和99一组属性互质。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。
Input
数据第一行两个数n1，n2，空格分割。
接下来n1行，每行3个数，依次表示每张X类卡牌的3项属性值。
接下来n2行，每行3个数，依次表示每张Y类卡牌的3项属性值。
Output
输出一个整数：最多能够匹配的数目。
Sample Input
2 2
2 2 2
2 5 5
2 2 5
5 5 5
2 2 2
2 5 5
2 2 5
5 5 5
Sample Output
2
【提示】
样例中第一张X类卡牌和第一张Y类卡牌能配对，第二张X类卡牌和两张Y类卡牌都能配对。所以最佳方案是第一张X和第一张Y配对，第二张X和第二张Y配对。
另外，请大胆使用渐进复杂度较高的算法！
HINT
对于100%的数据，n1,n2≤ 30000，属性值为不超过200的正整数
Source
看到之后显然有个暴力建二分图，求最大匹配的想法，但显然N^2的复杂度难以接受，而最大匹配也是极慢的。
所以考虑在左右部点中间设立一些中转站，目的是将边按照一定的规律归并，减少复杂度。
因为至多只能有一组数互质，所以至少有两组数GCD不为1，每对数均含有至少一个相同的质因子。
而200以内的质因子只有46个，所以可以枚举第一、二组含有的相同质因子，以及这两组是AB,BC,还是CA。
所以中转站的个数为46*46*3；又因为200以内的数至多含有4个质因子，所以边数也是有保证的。
建图之后跑最大流即可，貌似需要一些优化，看自己的常数了，拼脸也可以。
#include <cstdio>
#include <cstring> inline int nextChar(void) {
const int siz = ;
static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz;
if (hd == tl)
fread(hd = buf, , siz, stdin);
return int(*hd++);
} inline int nextInt(void) {
register int ret = ;
register int neg = false;
register int bit = nextChar();
for (; bit < ; bit = nextChar())
if (bit == '-')neg ^= true;
for (; bit > ; bit = nextChar())
ret = ret * + bit - ;
return neg ? -ret : ret;
} const int pri[] = {
, , , , , , , , , , , , , ,
, , , , , , , , , , , , ,
, , , , , , , , , , ,
, , , , , , , ,
}; const int inf = 1e9;
const int siz = ; int s, t;
int edges;
int hd[siz];
int to[siz];
int nt[siz];
int fl[siz]; inline void add(int u, int v, int f) {
// printf("%d %d %d\n", u, v, f);
nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; hd[u] = edges++;
nt[edges] = hd[v]; to[edges] = u; fl[edges] = ; hd[v] = edges++;
} int dep[]; inline bool bfs(void) {
static int que[siz], head, tail;
memset(dep, , sizeof(dep));
dep[que[head = ] = s] = tail = ;
while (head != tail) {
int u = que[head++], v;
for (int i = hd[u]; ~i; i = nt[i])
if (fl[i] && !dep[v = to[i]])
dep[que[tail++] = v] = dep[u] + ;
}
return dep[t];
} int lst[]; int dfs(int u, int f) {
if (u == t || !f)return f;
int used = , flow, v;
for (int i = lst[u]; ~i; i = nt[i])
if (dep[v = to[i]] == dep[u] + ) {
flow = dfs(v, f - used < fl[i] ? f - used : fl[i]);
used += flow;
fl[i] -= flow;
fl[i^] += flow;
if (fl[i])lst[u] = i;
if (used == f)return f;
}
if (!used)dep[u] = ;
return used;
}; inline int maxFlow(void) {
int maxFlow = , newFlow;
while (bfs()) {
for (int i = s; i <= t; ++i)
lst[i] = hd[i];
while (newFlow = dfs(s, inf))
maxFlow += newFlow;
}
return maxFlow;
} int n, m; int fac[][]; int map[][][]; signed main(void) {
n = nextInt();
m = nextInt();
for (int i = ; i <= ; ++i)
for (int j = ; j <= ; ++j)
if (i % pri[j] == )
fac[i][++fac[i][]] = j;
for (int i = , c = n + m; i < ; ++i)
for (int j = ; j <= ; ++j)
for (int k = ; k <= ; ++k)
map[i][j][k] = ++c;
memset(hd, -, sizeof(hd));
s = , t = n + m + ** + ;
for (int i = ; i <= n; ++i) {
add(s, i, );
int a = nextInt();
int b = nextInt();
int c = nextInt();
for (int j = ; j <= fac[a][]; ++j)
for (int k = ; k <= fac[b][]; ++k)
add(i, map[][fac[a][j]][fac[b][k]], );
for (int j = ; j <= fac[b][]; ++j)
for (int k = ; k <= fac[c][]; ++k)
add(i, map[][fac[b][j]][fac[c][k]], );
for (int j = ; j <= fac[c][]; ++j)
for (int k = ; k <= fac[a][]; ++k)
add(i, map[][fac[c][j]][fac[a][k]], );
}
for (int i = ; i <= m; ++i) {
add(i + n, t, );
int a = nextInt();
int b = nextInt();
int c = nextInt();
for (int j = ; j <= fac[a][]; ++j)
for (int k = ; k <= fac[b][]; ++k)
add(map[][fac[a][j]][fac[b][k]], i + n, );
for (int j = ; j <= fac[b][]; ++j)
for (int k = ; k <= fac[c][]; ++k)
add(map[][fac[b][j]][fac[c][k]], i + n, );
for (int j = ; j <= fac[c][]; ++j)
for (int k = ; k <= fac[a][]; ++k)
add(map[][fac[c][j]][fac[a][k]], i + n, );
}
printf("%d\n", maxFlow());
}
@Author: YouSiki