【BZOJ4205】卡牌配对
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的正整数
题解：这个建模题有点难想~
先只考虑A和B都不互质的情况，因为200以内的质数只有46个，并且每个数所含的不同的质因子不超过3个，所以建46*46个点，每个A中的卡牌向所有自己包含的质数对连边，最多3*3条边。然后在分别考虑其他情况，只需要对A和B，A和C，B和C都建46*46个点即可。然后跑最大流既是答案。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define P(A,B,C) ((A)*num*num+(B-1)*num+C+T)
using namespace std;
int n1,n2,S,T,cnt,ans,num;
int v[3][10],tp[3];
int pri[210],np[210];
int head[70000],d[70000],to[2000000],next[2000000],val[2000000];
queue<int> q;
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void work(int a,int val)
{
tp[a]=0;
for(int i=1;pri[i]*pri[i]<=val;i++)
{
if(val%pri[i]==0)
{
v[a][++tp[a]]=i;
while(val%pri[i]==0) val/=pri[i];
}
}
if(val!=1) v[a][++tp[a]]=np[val];
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int dfs(int x,int mf)
{
if(x==T) return mf;
int i,k,temp=mf;
for(i=head[x];i!=-1;i=next[i])
{
if(d[to[i]]==d[x]+1&&val[i])
{
k=dfs(to[i],min(temp,val[i]));
if(!k) d[to[i]]=0;
val[i]-=k,val[i^1]+=k,temp-=k;
if(!temp) break;
}
}
return mf-temp;
}
int bfs()
{
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
q.push(S),d[S]=1;
int i,u;
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u];i!=-1;i=next[i])
{
if(!d[to[i]]&&val[i])
{
d[to[i]]=d[u]+1;
if(to[i]==T) return 1;
q.push(to[i]);
}
}
}
return 0;
}
int main()
{
n1=rd(),n2=rd(),S=n1+n2+1,T=n1+n2+2;
int i,j,a,b,c;
for(i=2;i<=200;i++)
{
if(!np[i]) pri[++num]=i,np[i]=num;
for(j=1;j<=num&&i*pri[j]<=200;j++)
{
np[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
memset(head,-1,sizeof(head));
for(i=1;i<=n1;i++)
{
a=rd(),b=rd(),c=rd();
work(0,a),work(1,b),work(2,c),add(S,i,1);
for(a=1;a<=tp[0];a++) for(b=1;b<=tp[1];b++) add(i,P(0,v[0][a],v[1][b]),1);
for(a=1;a<=tp[0];a++) for(b=1;b<=tp[2];b++) add(i,P(1,v[0][a],v[2][b]),1);
for(a=1;a<=tp[1];a++) for(b=1;b<=tp[2];b++) add(i,P(2,v[1][a],v[2][b]),1);
}
for(i=1;i<=n2;i++)
{
a=rd(),b=rd(),c=rd();
work(0,a),work(1,b),work(2,c),add(i+n1,T,1);
for(a=1;a<=tp[0];a++) for(b=1;b<=tp[1];b++) add(P(0,v[0][a],v[1][b]),i+n1,1);
for(a=1;a<=tp[0];a++) for(b=1;b<=tp[2];b++) add(P(1,v[0][a],v[2][b]),i+n1,1);
for(a=1;a<=tp[1];a++) for(b=1;b<=tp[2];b++) add(P(2,v[1][a],v[2][b]),i+n1,1);
}
while(bfs()) ans+=dfs(S,1<<30);
printf("%d",ans);
return 0;
}