【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,delta;
    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;
}