首页 > 代码库 > BZOJ 4205: 卡牌配对
BZOJ 4205: 卡牌配对
4205: 卡牌配对
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 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配对。
另外，请大胆使用渐进复杂度较高的算法！
【提示】
样例中第一张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个质因子，所以边数也是有保证的。
建图之后跑最大流即可，貌似需要一些优化，看自己的常数了，拼脸也可以。
1 #include <cstdio> 2 #include <cstring> 3 4 inline int nextChar(void) { 5 const int siz = 1024; 6 static char buf[siz]; 7 static char *hd = buf + siz; 8 static char *tl = buf + siz; 9 if (hd == tl) 10 fread(hd = buf, 1, siz, stdin); 11 return int(*hd++); 12 } 13 14 inline int nextInt(void) { 15 register int ret = 0; 16 register int neg = false; 17 register int bit = nextChar(); 18 for (; bit < 48; bit = nextChar()) 19 if (bit == ‘-‘)neg ^= true; 20 for (; bit > 47; bit = nextChar()) 21 ret = ret * 10 + bit - 48; 22 return neg ? -ret : ret; 23 } 24 25 const int pri[50] = { 26 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 27 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 28 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 29 163, 167, 173, 179, 181, 191, 193, 197, 199 30 }; 31 32 const int inf = 1e9; 33 const int siz = 5000005; 34 35 int s, t; 36 int edges; 37 int hd[siz]; 38 int to[siz]; 39 int nt[siz]; 40 int fl[siz]; 41 42 inline void add(int u, int v, int f) { 43 // printf("%d %d %d\n", u, v, f); 44 nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; hd[u] = edges++; 45 nt[edges] = hd[v]; to[edges] = u; fl[edges] = 0; hd[v] = edges++; 46 } 47 48 int dep[100000]; 49 50 inline bool bfs(void) { 51 static int que[siz], head, tail; 52 memset(dep, 0, sizeof(dep)); 53 dep[que[head = 0] = s] = tail = 1; 54 while (head != tail) { 55 int u = que[head++], v; 56 for (int i = hd[u]; ~i; i = nt[i]) 57 if (fl[i] && !dep[v = to[i]]) 58 dep[que[tail++] = v] = dep[u] + 1; 59 } 60 return dep[t]; 61 } 62 63 int lst[100000]; 64 65 int dfs(int u, int f) { 66 if (u == t || !f)return f; 67 int used = 0, flow, v; 68 for (int i = lst[u]; ~i; i = nt[i]) 69 if (dep[v = to[i]] == dep[u] + 1) { 70 flow = dfs(v, f - used < fl[i] ? f - used : fl[i]); 71 used += flow; 72 fl[i] -= flow; 73 fl[i^1] += flow; 74 if (fl[i])lst[u] = i; 75 if (used == f)return f; 76 } 77 if (!used)dep[u] = 0; 78 return used; 79 }; 80 81 inline int maxFlow(void) { 82 int maxFlow = 0, newFlow; 83 while (bfs()) { 84 for (int i = s; i <= t; ++i) 85 lst[i] = hd[i]; 86 while (newFlow = dfs(s, inf)) 87 maxFlow += newFlow; 88 } 89 return maxFlow; 90 } 91 92 int n, m; 93 94 int fac[205][15]; 95 96 int map[3][50][50]; 97 98 signed main(void) { 99 n = nextInt();100 m = nextInt();101 for (int i = 2; i <= 200; ++i)102 for (int j = 1; j <= 46; ++j)103 if (i % pri[j] == 0)104 fac[i][++fac[i][0]] = j;105 for (int i = 0, c = n + m; i < 3; ++i)106 for (int j = 1; j <= 46; ++j)107 for (int k = 1; k <= 46; ++k)108 map[i][j][k] = ++c;109 memset(hd, -1, sizeof(hd));110 s = 0, t = n + m + 46*46*3 + 1;111 for (int i = 1; i <= n; ++i) {112 add(s, i, 1); 113 int a = nextInt();114 int b = nextInt();115 int c = nextInt();116 for (int j = 1; j <= fac[a][0]; ++j)117 for (int k = 1; k <= fac[b][0]; ++k)118 add(i, map[0][fac[a][j]][fac[b][k]], 1);119 for (int j = 1; j <= fac[b][0]; ++j)120 for (int k = 1; k <= fac[c][0]; ++k)121 add(i, map[1][fac[b][j]][fac[c][k]], 1);122 for (int j = 1; j <= fac[c][0]; ++j)123 for (int k = 1; k <= fac[a][0]; ++k)124 add(i, map[2][fac[c][j]][fac[a][k]], 1);125 }126 for (int i = 1; i <= m; ++i) {127 add(i + n, t, 1);128 int a = nextInt();129 int b = nextInt();130 int c = nextInt();131 for (int j = 1; j <= fac[a][0]; ++j)132 for (int k = 1; k <= fac[b][0]; ++k)133 add(map[0][fac[a][j]][fac[b][k]], i + n, 1);134 for (int j = 1; j <= fac[b][0]; ++j)135 for (int k = 1; k <= fac[c][0]; ++k)136 add(map[1][fac[b][j]][fac[c][k]], i + n, 1);137 for (int j = 1; j <= fac[c][0]; ++j)138 for (int k = 1; k <= fac[a][0]; ++k)139 add(map[2][fac[c][j]][fac[a][k]], i + n, 1);140 }141 printf("%d\n", maxFlow());142 }
@Author: YouSiki
BZOJ 4205: 卡牌配对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。