题目链接

题意

给定一个二分图，二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$，则这两点之间有一条边。求二分图最大匹配。

解析

首先我们发现，如果暴力建边的话，我们可能会建 $n^2$ 条边，在 $100$ 组数据的情况下，非常容易 TLE。

我们考虑优化。对于一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$ 这个条件，我们可以理解为这两个点有一个共同的因子。因此我们可以对于每一个点的权值进行分解质因数，然后对于左部点，令这个点连向因子；对于右部点，令因子连向这个点。最后建出连向所有左部边的超级源点和所有右部边连向的超级汇点。

这样的话，一条边就变成了超级原点到左部点到共同因子到右部点再到超级汇点。由于 $\log_210^7<24$，因此每个点连的边就从可能最多的 $500$ 变成了一个不大于 $24$ 的数，我们就成功做到了优化，接着只需要跑一遍网络流就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,m,n;
map<int,int> ma;//开个 map 记录质因数代表的点
struct edge{
    int to,nxt,w;
}e[N<<3];
int head[N],cnt=1;
inline void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
int tot,ans;
//以下为 Dinic
int dep[N];
inline bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;q.push(1);dep[1]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w&&(!dep[v])){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if(dep[2]) return true;
    return false;
}
inline int dfs(int u,int in){
    if(u==2) return in;
    int out=0;
    for(int i=head[u];i&&in;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].w&&dep[v]==dep[u]+1){
            int tmp=dfs(v,min(in,e[i].w));
            e[i].w-=tmp;e[i^1].w+=tmp;
            in-=tmp;
            out+=tmp;
        }
    }
    if(!out) dep[u]=0;
    return out;
}
//以上为 Dinic
signed main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);ans=0;
        tot=n+m+2;cnt=1;memset(head,0,sizeof(head));ma.clear();
        for(int i=3,x;i<=m+2;i++){
            add(1,i,1);add(i,1,0);//超级源点
            scanf("%d",&x);
            for(int j=2;j<=x;j++){//分解质因数
                if(x%j==0){
                    if(!ma[j]){
                        tot++;
                        add(i,tot,1);add(tot,i,0);
                        ma[j]=tot;
                    }
                    else{
                        add(i,ma[j],1);add(ma[j],i,0);
                    }
                }
            }
        }
        for(int i=m+3,x;i<=m+2+n;i++){
            add(2,i,0);add(i,2,1);//超级汇点
            scanf("%d",&x);
            for(int j=2;j<=x;j++){//分解质因数
                if(x%j==0){
                    if(!ma[j]){
                        tot++;
                        add(i,tot,0);add(tot,i,1);
                        ma[j]=tot;
                    }
                    else{
                        add(i,ma[j],0);add(ma[j],i,1);
                    }
                }
            }
        }
        while(bfs()){
            ans+=dfs(1,1e9);
        }
        printf("%d\n",ans);
    }
    return 0;
}