elta;
int u,v;
while(true)
{
SPFA();
if(d[T]==INF||dist[T]>=0)//就是这里,一定要判一下!!!否则答案偏小
break;
delta=d[T];
for(v=T;v!=S;v=u)
{
u=prevv[v];
node *&p=preve[v];
p->cap-=delta;
p->bck->cap+=delta;
cost+=1LL*p->cost*delta;
}
}
return cost;
}
int main()
{
scanf("%d",&n);
Sieve();
LL ans=1LL;
for(int i=0;i<(int)prime.size();i++)
maxval[i]=F(prime[i],1LL),ans+=maxval[i];//先确定初始的值
// printf("%lld\n",ans);
Build();
ans-=min(0LL,Min_Cost_Flow());//加上可能存在的更有的方案(应该可以不用取min,懒得改了...)
printf("%lld\n",ans);
return 0;
}
|