D

本文主要是介绍D，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

假设\(a\)是\(b\)的倍数，而且\(a / b\) 是质数
我们根据所含质数种类奇偶来建图，如果是奇数的话，就和\(s\)连边，如果是偶数的话就和\(t\)连边
\(s\)是源点，\(t\)是汇点
\(a\)如果能分解为奇数个质数相乘，那么\(a\)到\(b+n\)连一条容量为\(inf\)，费用为\(c[a]*c[b]\)的边
\(a\)如果能分解为偶数个质数相乘，那么\(b\)到\(a+n\)连一条容量为\(inf\)，费用为\(c[a]*c[b]\)的边
如果\(a\)能分解为奇数个质数相乘，那么源点到\(a\)连一条容量为\(sum[a]\)，费用为\(0\)的边
如果\(a\)能分解为偶数个质数相乘，那么\(a\)到汇点连一条容量为\(sum[a]\)，费用为\(0\)的边
剩下就是网络流的板子，然后需要注意的是，求的是费用不低于\(0\)的情况下的最大流

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=10020*30;
#define int long long
typedef long long ll;
bool vis[maxn];
int n,m,s,t,x,y,z,f,cost[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//cost最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
//maxflow 最大流量
//mincost 最大流量的情况下的最小花费
struct Edge {
	int to,next,flow,cost;//flow流量 cost花费
} edge[maxn];
int head[maxn],num_edge;
queue <int> q;
int t1,m1,t2,m2;

#define INF 2147483647
void add(int from,int to,int flow,int cost) {
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	edge[num_edge].flow=flow;
	edge[num_edge].cost=cost;
	head[from]=num_edge;

	edge[++num_edge].next=head[to];
	edge[num_edge].to=from;
	edge[num_edge].flow=0;
	edge[num_edge].cost=-cost;
	head[to]=num_edge;
}
bool spfa(int s,int t) {
	memset(cost,0x7f,sizeof(cost));
	memset(flow,0x7f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	q.push(s);
	vis[s]=1;
	cost[s]=0;
	pre[t]=-1;
	while (!q.empty()) {
		int now=q.front();
		q.pop();
		vis[now]=0;
		for (int i=head[now]; i!=-1; i=edge[i].next) {
			if (edge[i].flow>0 && cost[edge[i].to]>cost[now]+edge[i].cost) { //正边
				cost[edge[i].to]=cost[now]+edge[i].cost;
				pre[edge[i].to]=now;
				last[edge[i].to]=i;
				flow[edge[i].to]=min(flow[now],edge[i].flow);//
				if (!vis[edge[i].to]) {
					vis[edge[i].to]=1;
					q.push(edge[i].to);
				}
			}
		}
	}
	return pre[t]!=-1;
}

void MCMF() {
	while (spfa(s,t)) {
		int now=t;
		while (now!=s) {
			//从源点一直回溯到汇点
			edge[last[now]].flow-=flow[t];//flow和cost容易搞混
			edge[last[now]^1].flow+=flow[t];
			now=pre[now];
		}
		if(mincost + flow[t]*cost[t] <= 0)
			maxflow+=flow[t], mincost+=flow[t]*cost[t];
		else {
			maxflow += llabs(mincost)/llabs(cost[t]);
			break;
		}
	}
}
int top, pri[1000000], d[1000100], a[maxn], b[maxn], id[maxn];
int i, j, k;
ll c[maxn];
void getprime() {
	int n = 1000000, i, j;
	top = 0;
	for(i=2; i<=n; i++) {
		if(!d[i])pri[top++] = i;
		for(j=0; j<top && i*pri[j]<=n; j++) {
			d[i*pri[j]] = 1;
			if(i%pri[j] == 0)break;
		}
	}
}
signed main() {
	getprime();
	memset(head,-1,sizeof(head));
	num_edge=-1;
	cin>>n;
	s = 0;
	t = n+n+2;
	for(i=1; i<=n; i++)scanf("%d", &a[i]);
	for(i=1; i<=n; i++)scanf("%d", &b[i]);
	for(i=1; i<=n; i++)scanf("%lld", &c[i]);
	for(i=1; i<=n; i++) {
		int num = 0, x= a[i];
		for(j=0; (ll)pri[j]*pri[j]<=x; j++) {
			while(x%pri[j] == 0)
				x/=pri[j], num++;
		}
		if(x!=1)num++;
		if(num%2) {
			id[i] = i;
			//			  flow
			add(0, id[i], b[i], 0);
		} else {
			id[i] = i+n;
			add(id[i], t, b[i], 0);
		}
	}
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			if(i!=j && a[i]>a[j] && a[i]%a[j] == 0) {
				int x = a[i]/a[j];
				for(k=0; pri[k]*pri[k]<=x; k++)
					if(x % pri[k] == 0)
						break;
				if(pri[k]*pri[k] > x) {
					if(id[i]<id[j])
						add(id[i], id[j], INF, -c[i]*c[j]);
					else
						add(id[j], id[i], INF, -c[i]*c[j]);
				}
			}
	MCMF();
	cout<<maxflow<<endl;
	return 0;
}

这篇关于D的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！