rt,最小值和最大值我都开到1e18了啊,有没有哪位dalao帮一下QAQ
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
#define int long long
int a[210],b[210],c[210];
struct edge{
int v,f,c,nxt;
}e[100010];
bool vis[410];
int n,ecur=1,top[410],dis[410],cnt[410];
void add(int u, int v, int c, int f){
e[++ecur]={v,f,c,top[u]};top[u]=ecur;
e[++ecur]={u,0,-c,top[v]};top[v]=ecur;
}
bool bfs(int s, int t){
memset(dis,-0x3f,sizeof(dis));
queue<int>q;
q.push(s);dis[s]=0;
while(q.size()){
int u=q.front();q.pop();
for(int i=top[u];i;i=e[i].nxt){
int v=e[i].v,c=e[i].c;
if(e[i].f&&dis[u]+c>dis[v]) dis[v]=dis[u]+c,q.push(v);
}
}
return dis[t]>-1e18;
}
int dfs(int x, int ret, int t){
vis[x]=1;
if(x==t||!ret) return ret;
int lef=ret;
for(int i=top[x];i;i=e[i].nxt){
int v=e[i].v,f=e[i].f;
if(dis[v]==dis[x]+e[i].c&&!vis[v]&&f){
int tmp=dfs(v,min(lef,f),t);
lef-=tmp;
e[i].f-=tmp,e[i^1].f+=tmp;
}
if(!lef) break;
}
return ret-lef;
}
void init(int t){
for(int i=2;i<=4*n+1;i++)
if(i&1) e[i].f=0;
else e[i].f=b[(i-2)/4+1];
for(int i=4*n+2;i<=ecur-2;i++) if(i&1) e[i].f=0; else e[i].f=1e18;
e[ecur-1].f=t,e[ecur].f=0;
}
int work(int s, int t){
int l=1,r=1e8,anst=0;
while(l<=r){
int mid=(l+r)>>1,ans=0,flow=0;
init(mid*2);
//for(int i=1;i<=ecur;i++) cout<<e[i].v<<' '<<e[i].f<<' '<<e[i].c<<'\n';
while(bfs(s,t)){
vis[t]=1;
while(vis[t]){
memset(vis,0,sizeof(vis));
int tt=dfs(s,1e18,t);
ans+=dis[t]*tt;
flow+=tt;
}
}
//for(int i=1;i<=ecur;i++) cout<<e[i].v<<' '<<e[i].f<<' '<<e[i].c<<'\n';
flow/=2;//cout<<flow<<' '<<mid<<'\n';
if(ans>=0&&flow==mid) l=mid+1,anst=mid;
else r=mid-1;
}
return anst;
}
signed main(){
cin>>n;
int s=n*2+1,t=n*2+2;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=n;j++) cin>>b[j];
for(int k=1;k<=n;k++) cin>>c[k];
for(int i=1;i<=n;i++){
add(s,i,0,b[i]),add(i+n,t,0,b[i]);
int tt=a[i];
for(int j=2;j*j<=tt;j++) while(tt%j==0) tt/=j,cnt[i]++;
if(tt>1) cnt[i]++;
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
if(a[i]%a[j]==0&&cnt[i]==cnt[j]+1) add(i,j+n,c[i]*c[j],1e18),add(j,i+n,c[i]*c[j],1e18);
}
int st=n*2+3;
add(st,s,0,0);
cout<<work(st,t);
return 0;
}