C

题目链接：https://cn.vjudge.net/contest/281959#problem/C

题目大意：中文题目

具体思路：用网络流的思想，我们求得是最大的匹配数，那么我们按照二分图的形式去建边就可以了，加上超级源点和超级汇点，就可以用网络流跑了。

建边的时候，我们首先把每个数进行素因子分解，看一下当前的这个数能够被分解成多少个素数，奇数个的放在一个数组里，偶数个的放在另一个数组里面（如果两个点直接能匹配的话，就需要他们两个相除之后只能剩余一个素数）。对于当前的这条边的权值，我们是按照最大流进行的，所以需要建立负边，具体的注释在代码中解释吧。

AC代码：

  1 #include <iostream>
  2 #include<stack>
  3 #include<stdio.h>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<cstring>
  8 using namespace std;
  9 # define ll long long
 10 const int maxn = 200+100;
 11 const int maxm = 3e5+20050;
 12 const int mod = 1e9+7;
 13 const ll inf =1000000000000000ll;
 14 struct node
 15 {
 16     int to;
 17     ll cost;
 18     ll w;
 19     int nex;
 20 } edge[maxm];
 21 ll dis[maxm],prev[maxm],pree[maxm];
 22 int vis[maxm];
 23 int head[maxm],num;
 24 ll t1[maxm],t2[maxm],t3[maxm];
 25 ll tx[maxm],ty[maxm];
 26 int viss[maxm],prim[maxm],primnum,isprim[maxm*100];
 27 void prime()
 28 {
 29     for(int i=2; i<maxm; i++)
 30     {
 31         if(viss[i]==0)
 32         {
 33             viss[i]=1;
 34             prim[++primnum]=i;
 35             isprim[i]=1;
 36             for(int j=i; j<maxm; j+=i)
 37             {
 38                 viss[j]=1;
 39             }
 40         }
 41     }
 42 }
 43 bool judge(ll t1,ll t2)
 44 {
 45     if(t1==0||t2==0)
 46         return false;
 47     if(t1<t2)
 48         swap(t1,t2);
 49     if(t1%t2!=0)
 50         return false;
 51     t1/=t2;
 52 //    if(isprim[t1])
 53 //        return true;
 54 //    return false;
 55  for(int i=1;i<=primnum;i++){//判断是不是只剩下一个素数，这个地方有一个小的优化，我们看当前这个数是不是素数，只需要看到他的sqrt就可以了。
 56         if(prim[i]>=t1)break;
 57         if(t1%prim[i]==0)return 0;
 58     }
 59     return 1;
 60 }
 61 void addedge(int fr,int to,ll w,ll cost)
 62 {
 63     edge[num].to=to;
 64     edge[num].w=w;
 65     edge[num].cost=-cost;
 66     edge[num].nex=head[fr];
 67     head[fr]=num++;
 68     edge[num].to=fr;
 69     edge[num].w=0;
 70     edge[num].cost=cost;
 71     edge[num].nex=head[to];
 72     head[to]=num++;
 73 }
 74 bool spfa(int st,int ed)
 75 {
 76     memset(vis,0,sizeof(vis));
 77     memset(pree,-1,sizeof(pree));
 78     for(int i=0; i<=ed; i++)
 79         dis[i]=inf;
 80     dis[st]=0,vis[st]=1;
 81     queue<int>q;
 82     q.push(st);
 83     while(!q.empty())
 84     {
 85         int top=q.front();
 86         q.pop();
 87         vis[top]=0;
 88         for(int i=head[top]; i!=-1; i=edge[i].nex)
 89         {
 90             int tmp=edge[i].to;
 91             if(edge[i].w&&dis[tmp]>dis[top]+edge[i].cost)
 92             {
 93                 dis[tmp]=dis[top]+edge[i].cost;
 94                 pree[tmp]=top;
 95                 prev[tmp]=i;
 96                 if(vis[tmp]==0)
 97                 {
 98                     vis[tmp]=1;
 99                     q.push(tmp);
100                 }
101             }
102         }
103     }
104     return pree[ed]!=-1;
105 }
106 ll mincostflow(int st,int ed)
107 {
108     ll ans=0;
109     ll cost=0;
110     while(spfa(st,ed))
111     {
112         ll minn=inf ;
113         for(int i=ed; i!=st; i=pree[i])
114         {
115             minn=min(minn,edge[prev[i]].w);
116         }
117         if(cost+minn*dis[ed]<=0)//注意这个地方，我们建立的是负边。
118         {
119             cost+=dis[ed]*minn;
120             ans+=minn;
121             for(int i=ed; i!=st; i=pree[i])
122             {
123                 edge[prev[i]].w-=minn;
124                 edge[prev[i]^1].w+=minn;
125             }
126         }
127         else //寻找临界点
128         {
129             ans-=(cost/dis[ed]);
130             return ans;
131         }
132     }
133     return ans;
134 }
135 int main()
136 {
137     prime();
138     int n;
139     memset(head,-1,sizeof(head));
140     scanf("%d",&n);
141    // cout<<primnum<<endl;
142     for(int i=1; i<=n; i++)
143     {
144         scanf("%lld",&t1[i]);
145     }
146     for(int i=1; i<=n; i++)
147     {
148         scanf("%lld",&t2[i]);
149     }
150     for(int i=1; i<=n; i++)
151     {
152         scanf("%lld",&t3[i]);
153     }
154     int num1=0,num2=0;
155     for(int i=1; i<=n; i++)//预先处理
156     {
157         int tmp=t1[i],tt=0;
158         for(int j=1; j<=primnum; j++)
159         {
160             while(tmp%prim[j]==0)
161             {
162                 tmp/=prim[j];
163                 tt++;
164             }
165             if(tmp==1||tmp==0)
166                 break;
167         }
168         if(tt&1)
169             tx[++num1]=i;
170         else
171             ty[++num2]=i;
172     }
173     for(int i=1; i<=num1; i++)
174     {
175         for(int j=1; j<=num2; j++)
176         {
177             if(judge(t1[tx[i]],t1[ty[j]]))
178             {
179                 addedge(tx[i],ty[j],1e9,t3[tx[i]]*t3[ty[j]]);
180             }
181         }
182     }
183     for(int i=1; i<=num1; i++)
184     {
185         addedge(0,tx[i],t2[tx[i]],0);
186     }
187     for(int i=1; i<=num2; i++)
188     {
189         addedge(ty[i],n+1,t2[ty[i]],0);
190     }
191     ll ans=mincostflow(0,n+1);
192     printf("%lld
",ans);
193     return 0;
194 }