BZOJ4205【FJ2015集训】卡牌配对 <网络流>

Posted on Symbols count in article: 1.2k Reading time ≈ 4 mins.

Problem

【FJ2015集训】卡牌配对

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

现在有一种卡牌游戏，每张卡牌上有三个属性值：A,B,CA,B,C。把卡牌分为X,YX,Y两类，分别有n1,n2n_1,n_2张。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
比如一张XX类卡牌属性值分别是225,233,101225,233,101，一张YY类卡牌属性值分别为115,466,99115,466,99。那么这两张牌是可以配对的，因为只有101101和9999一组属性互质。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。

Input

数据第一行两个数n1n_1，n2n_2，空格分割。
接下来n1n_1行，每行33个数，依次表示每张XX类卡牌的33项属性值。
接下来n2n_2行，每行33个数，依次表示每张YY类卡牌的33项属性值。

Output

输出一个整数：最多能够匹配的数目。

Sample Input

1
2
3
4
5
2 2
2 2 2
2 5 5
2 2 5
5 5 5

Sample Output

1
2

HINT

样例中第一张XX类卡牌和第一张YY类卡牌能配对，第二张XX类卡牌和两张YY类卡牌都能配对。所以最佳方案是第一张XX和第一张YY配对，第二张XX和第二张YY配对。
对于100%100\%的数据，n1,n2≤30000n_1,n_2\le 30000，属性值为不超过200200的正整数
请大胆使用渐进复杂度较高的算法！

标签：网络流

Solution

非常巧妙的一道二分图建模
首先考虑暴力建边，显然边数是 n2n^2 级别的，会同时MLEMLE和TLETLE
注意到值域只有200200，可以预处理出所有质数，并且可以发现可匹配的情况只有三种，即(A,B)(A,B)不互质,(B,C)(B,C)不互质,(C,A)(C,A)不互质（这里不互质只两张卡的两种同样属性不互质）。这样总共的不互质即可以匹配的情况共有46×46×346\times 46\times 3种（200200内共4646个质数）
对于一张XX类卡牌(A,B,C)(A,B,C)，如果一个点(a,b)(a,b)，aa是AA的质因子，bb是BB的质因子，那么就连一条由卡牌出发到那个点的流量为11的边。其他类的类似。YY类卡牌的话就连一条点到卡牌的边。源点向每个XX牌连一条流量为11的边，每个YY牌向汇点连一条流量为11的边。构图后跑最大流即可。

Code

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
#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 5000000
#define INF 0x7f7f7f7f
using namespace std;
int tot = 46, pri[46] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199};
int n, m, s, t, cnt, x[MAX_N+5], y[MAX_N+5], z[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5], d[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];    vector <int> p[205];
void init() {s = 0, t = n+m+tot*tot*3+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (!c || ~d[v]) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (!c || d[v] != d[u]+1) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;
    return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0;    cpy();	while (BFS()) ret += DFS(s, INF), rec();	return ret;}
int trans(int i, int j) {return i*tot+j+1;}
void build(int u) {
    int a = x[u], b = y[u], c = z[u];
    for (int i = 0; i < (int)p[a].size(); i++) for (int j = 0; j < (int)p[b].size(); j++)
        if (u <= n) addedge(u, n+m+trans(p[a][i], p[b][j]), 1);
        else addedge(n+m+trans(p[a][i], p[b][j]), u, 1);
    for (int i = 0; i < (int)p[a].size(); i++) for (int j = 0; j < (int)p[c].size(); j++)
        if (u <= n) addedge(u, n+m+trans(p[a][i], p[c][j])+tot*tot, 1);
        else addedge(n+m+trans(p[a][i], p[c][j])+tot*tot, u, 1);
    for (int i = 0; i < (int)p[b].size(); i++) for (int j = 0; j < (int)p[c].size(); j++)
        if (u <= n) addedge(u, n+m+trans(p[b][i], p[c][j])+tot*tot*2, 1);
        else addedge(n+m+trans(p[b][i], p[c][j])+tot*tot*2, u, 1);
}
int main() {
    scanf("%d%d", &n, &m), init();
    for (int i = 1; i <= 200; i++) for (int j = 0; j < tot; j++) if (i%pri[j] == 0) p[i].push_back(j);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", x+i, y+i, z+i), addedge(s, i, 1), build(i);
    for (int i = n+1; i <= n+m; i++) scanf("%d%d%d", x+i, y+i, z+i), addedge(i, t, 1), build(i);
    return printf("%d", Dinic()), 0;
}