bzoj3308: 九月的咖啡店 數學 玄學 最大流

bzoj3308: 九月的咖啡店

Description

深繪裡在九份開了一家咖啡讓，如何調配咖啡民了她每天的頭等大事

我們假設她有N種原料，第i種原料編号為i,調配一杯咖啡則需要在這

裡若幹種兌在一起。不過有些原料不能同時在一杯中，如果兩個編号

為i,j的原料，當且僅當i與j互質時，才能兌在同一杯中。

現在想知道，如果用這N種原料來調同一杯咖啡，使用的原料編号之和

最大可為多少。

Input

一個數字N

Output

如題

Sample Input

10

Sample Output

30

HINT

1<=N<=200000

分析

網絡流&數學神題。

兩個結論扔出來的時候已經懵逼了。

對于最後的最大編号之和的數的選擇:

1.至多2個質因數存在于一個數中

2.一個大于 n−√ ，一個小于 n−√

不會證不會證不會證。

大概的思路就是如果單獨放質因數應該會很優，但是舉舉例子會發現也有可能存在兩個質因數更優的情況。

比如hzwer大神的：

3，5，n=20

9+5<3*5

然後就是費用流比對小于 n−√ 和大于 n−√ 的數。

但是會炸。

于是優化，考慮單獨選數對答案的貢獻，再考慮把兩個單獨的數修改成比對狀态的收益 Vab−Va−Vb

然後不斷spfa增廣直到費用小于零。

虛淵玄

代碼

/**************************************************************
    Problem: 3308
    User: 2014lvzelong
    Language: C++
    Result: Accepted
    Time:140 ms
    Memory:13540 kb
****************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N = ;
const int M = ;
const int inf = ;
int read() {
    char ch = getchar();int x = , f = ;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x *  + ch - '0'; ch = getchar();}
    return x * f; 
}
int pre[N], head[N], to[M], w[M], f[M], nxt[M], dis[N], Q[M], p[N], top, tot, n, m, ans, s, t;
bool vis[N];
void add(int u, int v, int ww, int ff) {
    to[++top] = v; w[top] = ww; nxt[top] = head[u]; head[u] = top; f[top] = ff;
}
void adds(int u, int v, int w, int f) {add(u, v, w, f); add(v, u, , -f);}

void pri(int n) {
    vis[] = ;
    for(int i = ;i <= n; ++i) {
        if(!vis[i]) p[++tot] = i;
        for(int j = ;j <= tot && i * p[j] <= n; ++j) {
            vis[i * p[j]] = true;
            if(!(i % p[j])) break;
        }
    }
}

int calc(int n, int x) {int t; for(t = x; L * t * x <= n; t = t * x) ;return t;}

void Build() {
    s = tot + ; t = s + ; int pos = ;
    for(int i = ;i <= tot; ++i) {
        if(p[i] >= n / ) {ans += p[i]; continue;}
        if(L * p[i] * p[i] <= n) adds(s, i, , ), ans += calc(n, p[i]);
        else pos = (!pos) ? i : pos, adds(i, t, , ), ans += p[i];
    }
    for(int i = ;i < pos; ++i)
        for(int j = pos; j <= tot; ++j) {
            if(L * p[i] * p[j] > n) break;
            int f = calc(n / p[j], p[i]) * p[j] - calc(n, p[i]) - p[j];
            if(f > ) adds(i, j, , f);
        }
}

bool spfa() {
    for(int i = ;i <= t; ++i) dis[i] = -inf, vis[i] = ;
    int L = , R; Q[R = ] = s; dis[s] = ; vis[s] = true;
    while(L < R) {
        int u = Q[++L]; vis[u] = false;
        for(int i = head[u]; i; i = nxt[i]) 
            if(w[i] && dis[to[i]] < dis[u] + f[i]) {
                dis[to[i]] = dis[u] + f[i];
                pre[to[i]] = i;
                if(!vis[to[i]]) {
                    vis[to[i]] = true;
                    Q[++R] = to[i];
                }
            }
    }
    return dis[t] >= ;
}

int augment() {
    int flow = inf;
    for(int i = t; i != s; i = to[pre[i] ^ ]) flow = min(flow, w[pre[i]]);
    for(int i = t; i != s; i = to[pre[i] ^ ]) w[pre[i]] -= flow, w[pre[i] ^ ] += flow;
    return flow * dis[t];
}

void MCMF() {
    int mincost;
    while(spfa())
        mincost += augment();
    ans += mincost;
}

int main() {
    n = read(); 
    pri(n); top = ;
    Build();
    MCMF();
    printf("%d\n", ans + );
    return ;
}