90pts TLEon#6 求调
查看原帖
90pts TLEon#6 求调
688674
Night_fall楼主2024/7/23 10:47

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;
}
2024/7/23 10:47
加载中...