首页 > 代码库 > bzoj-4514(网络流)
bzoj-4514(网络流)
题目链接：
4514: [Sdoi2016]数字配对
Description
有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。
若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，
那么这两个数字可以配对，并获得 ci×cj 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
Input
第一行一个整数 n。
第二行 n 个整数 a1、a2、……、an。
第三行 n 个整数 b1、b2、……、bn。
第四行 n 个整数 c1、c2、……、cn。
Output
一行一个数，最多进行多少次配对
Sample Input
3
2 4 8
2 200 7
-1 -2 1
2 4 8
2 200 7
-1 -2 1
Sample Output
4
HINT
n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5
思路：
这是一个有限制条件的最大匹配问题,可以把每个点拆成左右两个点,左边与源点相连,右边与汇点相连,容量为b[i],费用为零,左右的一对点若满足题目要求的关系,
那么就连一对容量为无穷,费用为c[i]*c[j]的边,这两条边对称,最后建出来的图也是对称的,所以ans/2，在跑费用流的时候要用spfa沿最长路增广,判断费用和0的大小,就可以得到答案了;
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=210;
const LL inf=1e18;
int n;
LL A[maxn],B[maxn],C[maxn];
struct Edge
{
int from,to;
LL cap,flow,cost;
};
int m,s,t,inq[2*maxn],p[2*maxn];
LL d[2*maxn],a[2*maxn];
std::vector<Edge> edge;
std::vector<int> G[2*maxn];
inline void add_edge(int from,int to,LL cap,LL cost)
{
edge.push_back((Edge){from,to,cap,0,cost});
edge.push_back((Edge){to,from,0,0,-cost});
m=edge.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool bellmanford(LL &flow,LL &cost)
{
for(int i=s;i<=t;i++)d[i]=-inf;
memset(inq,0,sizeof(inq));
d[s]=0;inq[s]=1;p[s]=0;a[s]=inf;
queue<int>qu;
qu.push(s);
while(!qu.empty())
{
int fr=qu.front();qu.pop();inq[fr]=0;
int len=G[fr].size();
for(int i=0;i<len;i++)
{
Edge& e=edge[G[fr][i]];
if(e.cap>e.flow&&d[e.to]<d[fr]+e.cost)
{
d[e.to]=d[fr]+e.cost;
p[e.to]=G[fr][i];
a[e.to]=min(a[fr],e.cap-e.flow);
if(!inq[e.to]){qu.push(e.to);inq[e.to]=1;}
}
}
}
if(d[t]<=-inf)return false;
if(cost+d[t]*a[t]<0)
{
LL tep=cost/(-d[t]);
flow+=tep;
return false;
}
flow+=a[t];
cost+=d[t]*a[t];
int u=t;
while(u!=s)
{
edge[p[u]].flow+=a[t];
edge[p[u]^1].flow-=a[t];
u=edge[p[u]].from;
}
return true;
}
inline LL mincostflow()
{
LL flow=0;
LL cost=0;
while(bellmanford(flow,cost));
return flow;
}
inline LL pow_mod(LL x,LL y,LL mod)
{
LL s=1,base=x;
while(y)
{
if(y&1)s=s*base%mod;
base=base*base%mod;
y>>=1;
}
return s;
}
inline int isprime(LL num)
{
if(num<=1)return 0;
if(num==2)return 1;
if(num%2==0)return 0;
for(int i=1;i<=50;i++)
{
LL x=rand()%num;
if(x==0)x++;
if(pow_mod(x,num-1,num)!=1)return 0;
}
return 1;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
for(int i=1;i<=n;i++)scanf("%lld",&C[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(A[i]/A[j]<=1||A[i]%A[j])continue;
if(isprime(A[i]/A[j]))
{
add_edge(j,i+n,100000000,(LL)C[i]*C[j]);
add_edge(i,j+n,100000000,(LL)C[i]*C[j]);
}
}
}
s=0,t=2*n+1;
for(int i=1;i<=n;i++)add_edge(s,i,B[i],0),add_edge(n+i,t,B[i],0);
printf("%lld\n",mincostflow()/2);
return 0;
}
bzoj-4514(网络流)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。