设为首页 加入收藏

TOP

【2019雅礼集训】【最大费用流】【模型转换】D2T3 sum(一)
2019-01-09 14:09:03 】 浏览:239
Tags:2019 集训 最大 费用 模型 转换 D2T3 sum

目录

题意

现在你有一个集合{1,2,3,...,n},要求你从中取出一些元素,使得这些元素两两互质。问你能够取出的元素总和最多是多少?

输入格式

一个整数n

输出格式

一个整数表示能够选出的最大的元素总和。

思路

这道题居然是结论+网络流?根本想不到啊...~~
感觉写题解都只能照搬官方题解了~~

首先出题人就给了两个自己也没有证出来的结论:

  1. 最后选出的数至多只有两个不同的质因子
  2. 每个选出的数val所包含的质因子如果有两个的话,一定是一个小于\(\sqrt{val}\),还有一个是大于\(\sqrt{val}\)

至于为什么呢?好像没有人知道...
然后我们考虑建图。如果暴力建图(就是像二分图那样),将所有的质因子分为两个部,左边是小于等于\(\sqrt {n}\)的,右边是大于\(\sqrt {n}\),然后两个部之间两两连边就可以了。但是这样子边的数量好像多了一点..."据说"可能会T(没试过)。

那么就是优化。
首先,先定义F(pri[1],pri[2]...pri[k])为包含pri[]这些质因子的最大的小于等于n的数。然后我们能够发现,F(pri[1]),F(pri[2]),F(pri[3])...F(pri[pri.size()-1])这些数字是比较优秀的。
然后由于分成了两个部,我们考虑左边一个数质数x,右边一个数质数y,如果我们加入F(x,y)的话,我们能够发现F(x)和F(y)就不能选了。那么就会获得\(F(x,y)-F(x)-F(y)\)的贡献。只有当这个值大于0的时候,我们才将这条边加进去。
宏观感受下,这样子之后边的数量就变得很少了...然后你可以过了...

建图的话,就是源点S连向左边的部,容量为1,费用为0;
左边的部按照上述方式向右边的部连边,容量为1,费用为\(F(x,y)-F(x)-F(y)\)


右边的部向汇点T连边,容量为1,费用为0。
然后跑一个最大费用流(注意不是最大流!!wa了好久!!注意当当前求出来的费用小于0时需要退出!!否则答案就会偏小),在加上最开始的初始值(\(\sum_{i=1}^{k}F(pri[i])\)),就是最后的答案了。

代码

我的实现是建立负权边跑最小费用流,可能具体细节和上述的做法是反着的。如果你采用SPFA求最长路的话,细节和上面就是一样的了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define MAXN 200000
#define INF 1000000000000000000LL
using namespace std;
typedef long long LL;
struct node
{
    int to;
    LL cap,cost;
    node *nxt,*bck;
}edges[MAXN*10+5];
node *ncnt=&edges[0],*Adj[MAXN+5];
int S,T,n;
vector<LL> prime,p1,p2;
bool vis[MAXN+5],inque[MAXN+5];
LL maxval[MAXN+5],dist[MAXN+5],d[MAXN+5];
int prevv[MAXN+5];
node *preve[MAXN+5];
queue<int> que;
void Sieve()
{
    for(int i=2;i<=n;i++)
    {
        if(vis[i]==false)
            prime.push_back(i);
        for(int j=0;1LL*prime[j]*i<=n;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }
}
LL F(LL x,LL y)
{
    LL ret=y;//由于y>sqrt(n),所以y这个质因子在ret中只会出现一次
    while(1LL*ret*x<=n)
        ret*=x;
    return ret;
}
void AddEdge(int u,int v,LL cap,LL cost)
{
    node *p=++ncnt;
    p->to=v;p->cap=cap;p->cost=cost;
    p->nxt=Adj[u];Adj[u]=p;
    
    node *q=++ncnt;
    q->to=u;q->cap=0;q->cost=-cost;
    q->nxt=Adj[v];Adj[v]=q;
    
    p->bck=q;q->bck=p;
}
void Build()
{
    S=0,T=(int)prime.size()+1;
    for(int i=0;i<(int)prime.size();i++)
        if(1LL*prime[i]*prime[i]<=n)
            AddEdge(S,i+1,1,0),p1.push_back(i);
        else
            AddEdge(i+1,T,1,0),p2.push_back(i);
    for(int i=0;i<(int)p1.size();i++)
        for(int j=0;j<(int)p2.size();j++)
        {
            LL num1=prime[p1[i]],num2=prime[p2[j]];
            LL num=F(num1,num2);
            if(num-maxval[p1[i]]-maxval[p2[j]]>0)
            {
//              printf("val:%lld\n",num-maxval[p1[i]]-maxval[p2[j]]);
                AddEdge(p1[i]+1,p2[j]+1,1,-num+maxval[p1[i]]+maxval[p2[j]]);
            }
        }
}
void SPFA()
{
    while(que.empty()==false)
        que.pop();
    memset(inque,0,sizeof(inque));
    fill(dist,dist+T+1,INF);
    fill(d,d+T+1,INF);
    dist[S]=0;
    que.push(S);inque[S]=true;
    while(que.empty()==false)
    {
        int u=que.front();
        que.pop();inque[u]=false;
        for(node *p=Adj[u];p!=NULL;p=p->nxt)
        {
            int v=p->to;
            LL w=p->cost;
            if(p->cap&&dist[v]>dist[u]+w)
            {
                if(inque[v]==false)
                    inque[v]=true,que.push(v);
                d[v]=min(d[u],p->cap);
                dist[v]=dist[u]+w;
                prevv[v]=u;preve[v]=p;
            }
        }
    }
}
LL Min_Cost_Flow()
{
    LL flow=0,cost=0,d
			
		  
编程开发网
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Chromium base库分割字符串SplitS.. 下一篇[P4721] 分治 FFT

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }