题面
思路
二分图匹配
这道题模型显然就是个二分图匹配嘛
那我们两两判断一下然后连边匹配.....就只有30分了
因为点数是30000，建的边太多了
这张二分图，如果用dinic跑网络流的话，因为是分层图，所以优势很大，但是也不可能支撑9亿条边
所以我们要优化边的数量
优化建边
观察题目条件，发现每个数字都不大于200，而200以下的只有46个质数，且235*7=210>200
也就是说，每个数最多有3个不同的质因数，且只能从46个里面选
再看题目要求的匹配关系，发现其实等价于至少两个属性之间有共同的质因数
那么我们可以把匹配关系转化为共同质因数关系
如何转化呢？
先考虑把AB两个属性转化一下
我们需要的是让在AB两个属性上都有相同质因数的点，能够通过边连接起来
那么我们建立46*46个点，第$(i,j)$个点代表A属性有第$i$个质因数，B属性有第$j$个质因数
这样，我们把每个X卡牌连到它对应的点，从每个Y卡牌对应的点连向这个Y卡牌，即可完成转化
例如，一张X卡牌的AB属性为$(30,35)$，2,3,5,7的编号分别为1,2,3,4
因为$30=235,35=5*7$
那么它就应该连向这些点：
$(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)$
这样，我们就把AB上能够有共同质因数的点，通过中间这46*46个“跳板”连接了起来
因为最多有3个不同的质因数，所以这时的边数最大是2334646，在合理范围内
同样地，我们对于BC、AC也这么做一下
最后，我们从超级源点S连到每一个X卡片，流量为1
Y卡片连向超级汇点T，流量为1
此时S-T最大流就是最大匹配对数
总边数不会大于$n1+n2+32334646$，点数则不会大于$n1+n2+346*46$，都在合理范围内，用当前弧优化的dinic可以轻松过掉
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define id(i,j) (i-1)*46+j
using namespace std;
inline int read(){
int re=0,flag=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
int n,m,cnt=-1,first[200010],dep[200010],cur[200010];
int pri[210],cntp,vis[210],fac[210][10];//我就是不喜欢vector!
struct edge{
int to,next,w;
}a[2000010];
inline void add(int u,int v,int w){
a[++cnt]=(edge){v,first[u],w};first[u]=cnt;
a[++cnt]=(edge){u,first[v],0};first[v]=cnt;
}
void init(){//初始化质因数表
int i,j,k,tmp;
for(i=2;i<=200;i++){
if(!vis[i]) pri[++cntp]=i;
for(j=1;j<=cntp;j++){
k=i*pri[j];
if(k>200) break;
vis[k]=1;
if(i%pri[j]==0) break;
}
}
for(k=2;k<=200;k++){
tmp=k;i=1;
while(tmp>1){
j=pri[i];
if(tmp%j==0){
fac[k][++fac[k][0]]=i;
while(tmp%j==0) tmp/=j;
}
i++;
}
}
}
int q[200010];
bool bfs(int s,int t){
int i,u,v,head=0,tail=1;
for(i=s;i<=t;i++) dep[i]=-1,cur[i]=first[i];
q[0]=s;dep[s]=0;
while(head<tail){
u=q[head++];
for(i=first[u];~i;i=a[i].next){
v=a[i].to;
if(~dep[v]||!a[i].w) continue;
dep[v]=dep[u]+1;q[tail++]=v;
}
}
return ~dep[t];
}
int dfs(int u,int t,int limit){
if(u==t||!limit) return limit;
int i,v,f,flow=0;
for(i=cur[u];~i;i=a[i].next){
v=a[i].to;cur[u]=i;
if((dep[v]==dep[u]+1)&&(f=dfs(v,t,min(a[i].w,limit)))){
flow+=f;limit-=f;
a[i].w-=f;a[i^1].w+=f;
if(!limit) return flow;
}
}
return flow;
}
#define inf 1e9
int dinic(int s,int t){
int re=0;
while(bfs(s,t)) re+=dfs(s,t,inf);
return re;
}
int S=0,T;
int main(){
memset(first,-1,sizeof(first));
init();
n=read();m=read();int i,j,k,t1,t2,t3;
T=n+m+46*46*3+1;
for(i=1;i<=n;i++){
t1=read();t2=read();t3=read();
add(S,i,1);
for(j=1;j<=fac[t1][0];j++)
for(k=1;k<=fac[t2][0];k++)
add(i,n+id(fac[t1][j],fac[t2][k]),1);
for(j=1;j<=fac[t1][0];j++)
for(k=1;k<=fac[t3][0];k++)
add(i,n+id(fac[t1][j],fac[t3][k])+46*46,1);
for(j=1;j<=fac[t2][0];j++)
for(k=1;k<=fac[t3][0];k++)
add(i,n+id(fac[t2][j],fac[t3][k])+46*46*2,1);
}
for(i=1;i<=m;i++){
t1=read();t2=read();t3=read();
add(i+46*46*3+n,T,1);
for(j=1;j<=fac[t1][0];j++)
for(k=1;k<=fac[t2][0];k++)
add(n+id(fac[t1][j],fac[t2][k]),i+46*46*3+n,1);
for(j=1;j<=fac[t1][0];j++)
for(k=1;k<=fac[t3][0];k++)
add(n+id(fac[t1][j],fac[t3][k])+46*46,i+46*46*3+n,1);
for(j=1;j<=fac[t2][0];j++)
for(k=1;k<=fac[t3][0];k++)
add(n+id(fac[t2][j],fac[t3][k])+46*46*2,i+46*46*3+n,1);
}
printf("%d
",dinic(S,T));
}