SDOI2016 Round 1 Day 1 T2，一道 网络流 水题。
题目链接：Luogu P4068/BZOJ 4514/LibreOJ 2031/SDOI2016 R1D1T2。
题目
题目描述
有 \(n\) 种数字，第 \(i\) 种数字是 \(a _ i\)、有 \(b _ i\) 个，权值是 \(c _ i\)。
若两个数字 $a _ i,a _ j$ 满足，$a _ i$ 是 $a _ j$ 的倍数，且 $\frac{a _ i}{a _ j}$ 是一个质数，那么这两个数字可以配对，并获得 $c _ i\times c _ j$ 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 $0$ 的前提下，求最多进行多少次配对。
数据范围
| 变量 | 数据范围 |
|---|---|
| $n$ | $\leq 200$ |
| $a _ i$ | $\leq 10^9$ |
| $b _ i$ | $\leq 10^5$ |
| $|c _ i|$ | $\leq 10^5$ |
时空限制
| 题目编号 | 时间限制 | 空间限制 |
|---|---|---|
| Luogu P4068 | $1\text{s}$ | $125\text{MiB}$ |
| BZOJ 4514 | $10\text{s}$ | $168\text{MiB}$ |
| LibreOJ 2031 | $1\text{s}$ | $128\text{MiB}$ |
| SDOI2016 R1D1T2 | $1\text{s}$ | $128\text{MiB}$ |
题解
思路
考虑求出 $\text{cnt} _ i$，表示 $a _ i$ 分解质因数之后，每个质因数的指数之和。
那么 $a _ i$ 和 $a _ j$ 能配对的条件转化为：
$a _ i$ 是 $a _ j$ 的倍数，且 $\text{cnt} _ i=\text{cnt} _ j+1$。
考虑一个二分图的模型。先按照 $\text{cnt}$ 的奇偶性，把数字分为两个集合。
- 源点向所有 $\text{cnt}$ 为奇数的点连一条容量为 $b _ i$，费用为 $0$ 的边。
- 所有 $\text{cnt}$ 为偶数的点向汇点连一条容量为 $b _ i$，费用为 $0$ 的边。
- 对于一对 $i,j$，如果 $a _ i$ 和 $a _ j$ 能配对并且 $\text{cnt} _ i$ 为奇数，则由 $i$ 向 $j$ 连一条边，容量为 $+\infty$，费用为 $c _ i\times c _ j$。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
reg bool f=false;
reg char ch=getchar();
reg ll res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=200+5;
const int MAXV=MAXN;
const int MAXE=MAXN*MAXN*2;
int n;
ll a[MAXN],b[MAXN],c[MAXN];
int cnt[MAXN];
inline void Div(reg int id){
reg ll x=a[id];
for(reg ll i=2;i*i<=x;++i)
if(x%i==0)
while(x%i==0){
x/=i;
++cnt[id];
}
if(x!=1)
++cnt[id];
return;
}
int Ecnt=1,head[MAXV],to[MAXE],Next[MAXE];
ll w[MAXE],p[MAXE];
inline void Add_Edge(reg int u,reg int v,reg ll len,reg ll val){
Next[++Ecnt]=head[u];
to[Ecnt]=v;
w[Ecnt]=len;
p[Ecnt]=val;
head[u]=Ecnt;
return;
}
inline void Add_Tube(reg int u,reg int v,reg ll len,reg ll val){
Add_Edge(u,v,len,val);
Add_Edge(v,u,0,-val);
return;
}
bool inque[MAXN];
ll dis[MAXN];
queue<int> Q;
inline bool SPFA(int s,reg int t){
memset(inque,false,sizeof(inque));
fill(dis+s,dis+t+1,-INF);
inque[s]=true,dis[s]=0,Q.push(s);
while(!Q.empty()){
reg int ID=Q.front();
Q.pop();
inque[ID]=false;
for(reg int i=head[ID];i;i=Next[i])
if(dis[to[i]]<dis[ID]+p[i]&&w[i]>0){
dis[to[i]]=dis[ID]+p[i];
if(!inque[to[i]]){
inque[to[i]]=true;
Q.push(to[i]);
}
}
}
return dis[t]>-INF;
}
bool vis[MAXV];
int cur[MAXV];
inline ll DFS(reg int ID,reg int t,reg ll lim){
if(ID==t)
return lim;
vis[ID]=true;
reg ll flow=0;
for(reg int &i=cur[ID];i;i=Next[i])
if(dis[to[i]]==dis[ID]+p[i]&&w[i]>0&&!vis[to[i]]){
reg int f=DFS(to[i],t,min(lim-flow,w[i]));
if(f){
flow+=f;
w[i]-=f;
w[i^1]+=f;
if(flow==lim)
break;
}
}
vis[ID]=false;
return flow;
}
inline ll Dinic(reg int s,reg int t){
reg ll res=0,Cost=0;
while(SPFA(s,t)){
memcpy(cur,head,sizeof(head));
reg ll sum=DFS(s,t,INF);
if(Cost+sum*dis[t]>=0)
res+=sum,Cost+=sum*dis[t];
else
return res+Cost/(-dis[t]);
}
return res;
}
int main(void){
n=read();
reg int s=0,t=n+1;
for(reg int i=1;i<=n;++i)
a[i]=read();
for(reg int i=1;i<=n;++i)
b[i]=read();
for(reg int i=1;i<=n;++i)
c[i]=read();
for(reg int i=1;i<=n;++i)
Div(i);
for(reg int i=1;i<=n;++i)
if(cnt[i]&1){
Add_Tube(s,i,b[i],0);
for(reg int j=1;j<=n;++j)
if((a[i]%a[j]==0&&cnt[i]==cnt[j]+1)||(a[j]%a[i]==0&&cnt[j]==cnt[i]+1))
Add_Tube(i,j,INF,c[i]*c[j]);
}
else
Add_Tube(i,t,b[i],0);
reg ll ans=Dinic(s,t);
printf("%lld\n",ans);
return 0;
}
近期评论