贵阳网站设计报价,网站开发项目需求,淘宝优惠群的网站是怎么做,哪些网站做黑名单文章目录题目描述解析代码题目描述
有n种数字#xff0c;第 i 种数字是 ai#xff0c;有 bi个#xff0c;权值是 ci。
若两个数字 ai,aj 满足#xff0c; ai 是 aj 的倍数#xff0c;且 ai/aj 是一个质数#xff0c;那么这两个数字可以配对#xff0c;并获得 ci*cj 的…
文章目录题目描述解析代码题目描述
有n种数字第 i 种数字是 ai有 bi个权值是 ci。
若两个数字 ai,aj 满足 ai 是 aj 的倍数且 ai/aj 是一个质数那么这两个数字可以配对并获得 ci*cj 的价值。
一个数字只能参与一次配对可以不参与配对。
在获得的价值总和不小于 0 的前提下求最多进行多少次配对。
解析
很神奇的题 考虑限制条件的转化 把每个数字进行质因数分解设 ai 的质因子个数为 cnti 那么ai、aj可以配对的充要条件为 1.ai | aj 2.cnticntj-1 注意到两个数字能够配对当且仅当它们cnt的奇偶性不同 所以如果我们按照cnt的奇偶性分类的话这就成了一个二分图 然后问题就简单了变成了一个配对问题 注意题目要求价值不小于0的条件下的最大流又因为dinic本身就是贪心的算法所以我们直接让它跑到价值用尽即可
代码
#includebits/stdc.h
using namespace std;
const int N1e5100;
const int M2e6100;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}
int n,m,s,t;
struct node{int to,nxt;ll cap,w;
}p[M1];
int fi[N],cur[N],cnt-1;
void addline(int x,int y,ll cap,ll w){p[cnt](node){y,fi[x],cap,w};fi[x]cnt;p[cnt](node){x,fi[y],0,-w};fi[y]cnt;
}
ll flow,cost;
queueintq;
bool vis[N];
ll dis[N];
bool jd;
bool spfa(){if(jd) return false;bool flag0;memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));dis[s]0;q.push(s);while(!q.empty()){int nowq.front();q.pop();vis[now]0;for(int icur[now]fi[now];~i;ip[i].nxt){int top[i].to;if(!p[i].cap) continue;if(dis[to]dis[now]p[i].w){dis[to]dis[now]p[i].w;if(tot) flag1;if(!vis[to]){q.push(to);vis[to]1;}}}}return flag;
}
ll dfs(int x,ll lim){if(jd) return 0;if(xt||!lim){//printf(lim%lld dis%lld\n,lim,dis[t]);if(costlim*dis[t]0){jd1;ll add(-cost)/dis[t];return add;}costlim*dis[t];return lim;}ll res0;vis[x]1;for(int icur[x];~i;ip[i].nxt){int top[i].to;if(vis[to]||!p[i].cap||dis[to]!dis[x]p[i].w) continue;ll adddfs(to,min(lim,p[i].cap));resadd;lim-add;p[i].cap-add;p[i^1].capadd;if(!lim) break;}vis[x]0;if(lim) dis[x]-1;return res;
}
void dinic(){flowcost0;while(spfa()){while(ll tmpdfs(s,2e18)) flowtmp;}
}
int ccnt[N],prime[N],tp,num,v[N];
void find_prime(){int tp100000;for(int i2;itp;i){if(!v[i]){prime[num]i;v[i]i;}for(int j1;jnum;j){int nowprime[j];if(nowtp/i||nowv[i]) break;v[now*i]now;}}
}
int calc(int x){int tpfloor(sqrt(x)),res0;for(int i1;inum;i){int nowprime[i];if(nowtp) break;while(x%now0){x/now;res;}}if(x1) res;return res;
}
ll a[N],b[N],c[N];
int main(){memset(fi,-1,sizeof(fi));find_prime();nread();for(int i1;in;i) a[i]read();for(int i1;in;i) b[i]read();for(int i1;in;i) c[i]read();for(int i1;in;i) ccnt[i]calc(a[i]);sn1;ts1;for(int i1;in;i){if(ccnt[i]%20) addline(s,i,b[i],0);else addline(i,t,b[i],0);}for(int i1;in;i){if(ccnt[i]%2) continue;for(int j1;jn;j){if((a[i]%a[j]0||a[j]%a[i]0)abs(ccnt[i]-ccnt[j])1) addline(i,j,2e18,-c[i]*c[j]);}}dinic();printf(%lld,flow);return 0;
}
/*
7 6
1 2 10000
2 3 10000
3 6 10000
1 4 8000
4 3 8000
2 5 6000
5 6 6000
*/
