【bzoj4205】【FJ2015集训】卡牌配对

2015年7月5日2,6463

卡牌配对

【问题描述】

现在有一种卡牌游戏,每张卡牌上有三个属性值:A,B,C。把卡牌分为X,Y两类,分别有n1,n2张。

两张卡牌能够配对,当且仅当,存在至多一项属性值使得两张卡牌该项属性值互质,且两张卡牌类别不同。

比如一张X类卡牌属性值分别是225,233,101,一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的,因为只有101和99一组属性互质。

游戏的目的是最大化匹配上的卡牌组数,当然每张卡牌只能用一次。

【输入】

数据第一行两个数n1,n2,空格分割。

接下来n1行,每行3个数,依次表示每张X类卡牌的3项属性值。

接下来n2行,每行3个数,依次表示每张Y类卡牌的3项属性值。

【输出】

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

【样例输入】

2 2

2 2 2

2 5 5

2 2 5

5 5 5

【样例输出】

2

【提示】

样例中第一张X类卡牌和第一张Y类卡牌能配对,第二张X类卡牌和两张Y类卡牌都能配对。所以最佳方案是第一张X和第一张Y配对,第二张X和第二张Y配对。

另外,请大胆使用渐进复杂度较高的算法!

【数据规模与约定】

对于10%的数据,n1,n2≤ 10;

对于50%的数据,n1,n2≤ 3000。

对于100%的数据,n1,n2≤ 30000,属性值为不超过200的正整数

题解

算法1:很明显的匹配,暴力构图+匈牙利算法复杂度O(nm)可以得到10分,dinic可以拿到60分。

算法2:考虑到按照匹配建图边数过多,我们采用将边分类的方法优化。考虑a项属性值能被x整除且b项能力值能被y整除的所有点,只要是在两侧一定能够匹配,所以我们在匹配的网络流模型中间增加一排这样的点,满足要求的左右点分别与它相连,边权为正无穷。考虑到x和y只需是质数,这样的点共有至多3*46*46个(1~200质数共46个),而200<2*3*5*7,所以两侧每个点至多连出3*3*3条边。于是我们构成了一个70000个点,2000000条边的网络流,依然是分层图,所以dinic有极佳的速度优势,通过100分数据。

匈牙利算法

网络流

 

 

  • fans2016年3月22日 下午7:05 回复

    黄学长神犇,%%%%

    #1  
  • debuggg2016年5月29日 下午8:11 回复

    %%%codeforces

    #2  
  • Bzoj4205卡牌配对 – CodingBlog2017年5月2日 下午10:21 回复

    […] 原题网址:http://www.lydsy.com/JudgeOnline/problem.php?id=4205 大致模型是二分图最大匹配,但暴力建边会T,考虑建中间节点,至少要有两项属性值不互质,但这样中间点数还是爆炸和边数,然而看了题解才知道中间点只要质数即可。(一开始反向边流量又忘记设为0了。。。 %hzwer http://hzwer.com/7428.html […]

    #3