Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

09/10
20:54
最大流

[bzoj 4205] 卡牌配对

♦♦♦♦♦♦   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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

【提示】
样例中第一张X类卡牌和第一张Y类卡牌能配对,第二张X类卡牌和两张Y类卡牌都能配对。所以最佳方案是第一张X和第一张Y配对,第二张X和第二张Y配对。
另外,请大胆使用渐进复杂度较高的算法!

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

优化网络流

我好懒啊....直接搬黄学长的题解吧:http://hzwer.com/7428.html

c++:

 

pascal:

 

[bzoj 4205] 卡牌配对