将每一个数分解质因数,暴力连边后二分图匹配,
但是匈牙利肯定得超时,所以我们的选择是 Hopcroft-Karp
Hopcroft-Karp ( sqrt(V)*E) 很高效的二分图匹配算法
/* *********************************************** Author :CKboss Created Time :2014年12月27日 星期六 20时33分02秒 File Name :CF498C_2.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int INF=0x3f3f3f3f; const int maxn=5500; int n,m; int a[111]; int nt; int A2[5500]; /// Pr; bool vis[111]; struct Point { int from,to; }pt[111]; void fenjie(int id,int x) { /// fenjie prime int R=-INF,L=INF; for(int i=2;i*i<=x;i++) { while(x%i==0) { R=max(R,nt); L=min(L,nt); A2[nt++]=i; x/=i; } } if(x!=1) { R=max(R,nt); L=min(L,nt); A2[nt++]=x; } pt[id].from=L; pt[id].to=R; } /**********************************/ /// Hopcroft-Karp int Mx[maxn],My[maxn]; int dx[maxn],dy[maxn]; int dis; bool used[maxn]; int uN; vector<int> G[maxn]; bool SearchP() { queue<int> Q; dis = INF; memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(int i=0;i<uN;i++) { if(Mx[i]==-1) { Q.push(i); dx[i]=0; } } while(!Q.empty()) { int u = Q.front(); Q.pop(); if(dx[u]>dis) break; int sz = G[u].size(); for(int i=0;i<sz;i++) { int v = G[u][i]; if(dy[v]==-1) { dy[v]=dx[u]+1; if(My[v]==-1) dis = dy[v]; else { dx[My[v]]=dy[v]+1; Q.push(My[v]); } } } } return dis!=INF; } bool DFS(int u) { int sz=G[u].size(); for(int i=0;i<sz;i++) { int v=G[u][i]; if(!used[v]&&dy[v]==dx[u]+1) { used[v]=true; if(My[v]!=-1&&dy[v]==dis) continue; if(My[v]==-1||DFS(My[v])) { My[v]=u; Mx[u]=v; return true; } } } return false; } int MaxMatch() { int res=0; memset(Mx,-1,sizeof(Mx)); memset(My,-1,sizeof(My)); while(SearchP()) { memset(used,false,sizeof(used)); for(int i=0;i<uN;i++) { if(Mx[i]==-1&&DFS(i)) res++; } } return res; } /**********************************/ int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); x--; y--; if(x%2==1) swap(x,y); /// Link Edge beteen x and y if(vis[x]==false) { fenjie(x,a[x]); vis[x]=true; } if(vis[y]==false) { fenjie(y,a[y]); vis[y]=true; } for(int j1=pt[x].from;j1<=pt[x].to;j1++) { for(int j2=pt[y].from;j2<=pt[y].to;j2++) { if(A2[j1]==A2[j2]) { /// Link edge uN=max(uN,j1); G[j1].push_back(j2); } else if(A2[j1]<A2[j2]) break; } } } uN++; cout<<MaxMatch()<<endl; return 0; }