BZOJ4205: 卡牌配对

题解:

首先暴力连边匹配肯定是不行的...

由于$200$以内的质数仅有$46$个,我们构造三类点$ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$分别表示参数1能被$p_1$整除,参数2能被$p_2$整除,剩下的依此类推.

然后对于左侧的点向符合条件的中间点连边.

对于右侧的点从符合条件的中间点连边.

这样做事实上是边分组,很显然是正确的.

直接用dinic玩就行了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
#define inf 0x3f3f3f3f
 
struct Solver{
    static const int V=100010;
    static const int E=3000010;
    int head[V],next[E],flow[E],end[E],ind,d[V];
    inline void reset(){
        memset(head,-1,sizeof head);
        ind=0;
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b;
        next[q]=head[a];
        head[a]=q;
        flow[q]=f;
    }
    inline void make(int a,int b,int f){
        addedge(a,b,f);
        addedge(b,a,0);
    }
    inline bool bfs(int s,int t){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d);
        d[q[ta++]=s]=0;
        while(fr!=ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])
                if(flow[j]&&d[end[j]]==-1)
                    d[q[ta++]=end[j]]=d[i]+1;
        }
        return d[t]!=-1;
    }
    inline int dinic(int p,int t,int Maxflow){
        if(p==t)
            return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])
            if(flow[j]&&d[end[j]]==d[p]+1){
                int to=dinic(end[j],t,flow[j]>last?last:flow[j]);
                if(to){
                    flow[j]-=to;
                    flow[j^1]+=to;
                    if(!(last-=to))
                        return Maxflow;
                }
            }
        d[p]=-1;
        return Maxflow-last;
    }
    inline int Maxflow(int s,int t){
        int re=0;
        while(bfs(s,t))
            re+=dinic(s,t,inf);
        return re;
    }
}g;
 
#define N 210
int p[N],cnt;
bool np[N];
inline void pre(){
    int i,j;
    for(i=2;i<=200;++i){
        if(!np[i])
            p[++cnt]=i;
        for(j=1;j<=cnt&&p[j]*i<=200;++j){
            np[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
}
int a[51][51],b[51][51],c[51][51];
int x[2][30010],y[2][30010],z[2][30010];
 
vector<int>v[N];
int main(){
    pre();
    int n,m;
    cin>>n>>m;
    int i,j,k;
    for(i=1;i<=n;++i)
        scanf("%d%d%d",&x[0][i],&y[0][i],&z[0][i]);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&x[1][i],&y[1][i],&z[1][i]);
     
    for(i=1;i<=200;++i)
        for(j=1;j<=cnt;++j)
            if(i%p[j]==0)
                v[i].push_back(j);
     
    int id=n+m;
    for(i=1;i<=cnt;++i)
        for(j=1;j<=cnt;++j){
            a[i][j]=++id;
            b[i][j]=++id;
            c[i][j]=++id;
        }
     
    int s=0,t=++id;
     
    g.reset();
    for(i=1;i<=n;++i)
        g.make(s,i,1);
    for(i=1;i<=m;++i)
        g.make(n+i,t,1);
     
    int p,q;
    for(i=1;i<=n;++i){
        for(j=0;j<v[x[0][i]].size();++j)
            for(k=0;k<v[y[0][i]].size();++k){
                p=v[x[0][i]][j];
                q=v[y[0][i]][k];
                g.make(i,a[p][q],1);
            }
        for(j=0;j<v[x[0][i]].size();++j)
            for(k=0;k<v[z[0][i]].size();++k){
                p=v[x[0][i]][j];
                q=v[z[0][i]][k];
                g.make(i,b[p][q],1);
            }
        for(j=0;j<v[y[0][i]].size();++j)
            for(k=0;k<v[z[0][i]].size();++k){
                p=v[y[0][i]][j];
                q=v[z[0][i]][k];
                g.make(i,c[p][q],1);
            }
    }
    for(i=1;i<=m;++i){
        for(j=0;j<v[x[1][i]].size();++j)
            for(k=0;k<v[y[1][i]].size();++k){
                p=v[x[1][i]][j];
                q=v[y[1][i]][k];
                g.make(a[p][q],n+i,1);
            }
        for(j=0;j<v[x[1][i]].size();++j)
            for(k=0;k<v[z[1][i]].size();++k){
                p=v[x[1][i]][j];
                q=v[z[1][i]][k];
                g.make(b[p][q],n+i,1);
            }
        for(j=0;j<v[y[1][i]].size();++j)
            for(k=0;k<v[z[1][i]].size();++k){
                p=v[y[1][i]][j];
                q=v[z[1][i]][k];
                g.make(c[p][q],n+i,1);
            }
    }
     
    cout<<g.Maxflow(s,t)<<endl;
     
    return 0;
}