看了一眼题目&数据范围，觉得应该是带下界的费用流
原来想拆点变成二分图，能配对的连边，跑二分图，可行性未知
后来看到另外一种解法。。
符合匹配要求的数要满足：质因子的个数相差为1，且两者可整除
因此筛完素数、分解质因子，记录质因子的个数
奇数个分为一类，偶数个分为一类，那么连边一定是奇数向偶数才可以连，而其中能整除的且商为质数的连边
然后源点向奇数的点连边，偶数的点向汇点连边，跑费用流
至于下界，我们先把权值取负
由于是求最小费用，那么当求得费用刚好大于0时
上一次刚好小于零的费用流就是最终的流
答案就是上一次的流量
程序写的不是很简洁。。有些细节比如要开LL值得注意= =
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<vector> 5 #include<queue> 6 #define LL long long 7 #define INF 0x7fffffff 8 #define maxe 40000*2+10 9 #define maxn 1000 10 using namespace std; 11 struct node{ 12 int from,to,flow,next; 13 LL cost; 14 }e[maxe]; 15 int ans,cnt,head[maxn],pre[maxn],vis[maxn]; 16 int n,s,t,a[maxn],b[maxn],notprime[32010],odd[maxn],even[maxn]; 17 LL c[maxn],sum,dis[maxn]; 18 vector<int> prime; 19 20 void insert(int u, int v, int f, LL c){ 21 e[++cnt].from=u; 22 e[cnt].to=v; 23 e[cnt].flow=f; 24 e[cnt].cost=c; 25 e[cnt].next=head[u]; 26 head[u]=cnt; 27 e[++cnt].from=v; 28 e[cnt].to=u; 29 e[cnt].flow=0; 30 e[cnt].cost=-c; 31 e[cnt].next=head[v]; 32 head[v]=cnt; 33 } 34 35 void init(){ 36 scanf("%d", &n); 37 for (int i=1; i<=n; i++) scanf("%d", &a[i]); 38 for (int i=1; i<=n; i++) scanf("%d", &b[i]); 39 for (int i=1; i<=n; i++) scanf("%lld", &c[i]); 40 } 41 42 bool judge(int i, int j){ 43 if (!a[i] || !a[j] || a[i]%a[j] && a[j]%a[i]) return 0; 44 int tmp=max(a[i]/a[j], a[j]/a[i]); 45 for (int k=0; k<prime.size(); k++) 46 if (prime[k]>=tmp) break; 47 else if (tmp % prime[k]==0) return 0; 48 return 1; 49 } 50 51 void get_prime(){ 52 memset(notprime,0,sizeof(notprime)); 53 for (int i=2; i<=32000; i++) 54 if (!notprime[i]){ 55 prime.push_back(i); 56 for (int j=i*i; j<=32000; j+=i) 57 notprime[j]=1; 58 } 59 } 60 61 void build(){ 62 odd[0]=even[0]=0; 63 for (int i=1; i<=n; i++){ 64 int sum=0; 65 for (int j=0; j<prime.size(); j++){ 66 int tmp=a[i]; 67 while (tmp%prime[j]==0) tmp/=prime[j],sum++; 68 } 69 if (sum&1) odd[++odd[0]]=i; 70 else even[++even[0]]=i; 71 } 72 73 cnt=-1; 74 memset(head,-1,sizeof(head)); 75 memset(e,0,sizeof(e)); 76 77 for (int i=1; i<=odd[0]; i++) 78 for (int j=1; j<=even[0]; j++) 79 if (judge(odd[i], even[j])) 80 insert(odd[i],even[j],INF,-c[odd[i]]*c[even[j]]); 81 s=n+1; t=n+2; 82 for (int i=1; i<=odd[0]; i++) 83 insert(s,odd[i],b[odd[i]],0); 84 for (int i=1; i<=even[0]; i++) 85 insert(even[i],t,b[even[i]],0); 86 } 87 88 bool spfa(){ 89 memset(pre,-1,sizeof(pre)); 90 memset(dis,127,sizeof(dis)); 91 queue<int> Q; 92 Q.push(s); 93 dis[s]=0; vis[s]=1; 94 while (!Q.empty()){ 95 int now=Q.front(); 96 Q.pop(); 97 vis[now]=0; 98 for (int i=head[now]; i!=-1; i=e[i].next){ 99 int v=e[i].to; 100 if (e[i].flow>0 && dis[v]>dis[now]+e[i].cost){ 101 dis[v]=dis[now]+e[i].cost; 102 pre[v]=i; 103 if (!vis[v]){ 104 vis[v]=1; 105 Q.push(v); 106 } 107 } 108 } 109 } 110 if (pre[t]==-1) return 0; return 1; 111 } 112 113 bool flow(){ 114 int f=INF; 115 for (int i=pre[t]; i!=-1; i=pre[e[i^1].to]) f=min(f,e[i].flow); 116 if ((LL)sum+dis[t]*f<=0){ 117 for (int i=pre[t]; i!=-1; i=pre[e[i^1].to]){ 118 e[i].flow-=f; e[i^1].flow+=f; 119 } 120 sum+=dis[t]*f; 121 ans+=f; 122 return 1; 123 } 124 else{ 125 ans-=(sum/dis[t]); 126 return 0; 127 } 128 } 129 130 void work(){ 131 ans=0; sum=0; 132 while (spfa() && flow()); 133 printf("%d ", ans); 134 } 135 136 int main(){ 137 get_prime(); 138 init(); 139 build(); 140 work(); 141 return 0; 142 }