BZOJ 3308 九月的咖啡店 費用流

BZOJ 3308 九月的咖啡店 費用流

題目大意：在[1,n]區間內選擇一些數，使得這些數兩兩互質，求這些數的和的最大值

容易發現對於一個最優解，每個質數存在且僅存在於一個數中。(廢話。
但是有可能一個數中存在多個質數
下面是兩個結論：
1.一個數中最多存在兩個不同的質數
2.這兩個質數一個，一個>n√
我完全不會證明這兩個結論，這兩個結論都是官方題解裡的
然後就好辦了，我們對於的質數和>n√的質數建立二分圖，求最大費用最大流即可
但是這樣會T掉，因為圖太大了
因此我們有兩個剪枝：
1.對於>n2的質數，一定單獨存在於解集中，不用扔進二分圖跑了
2.如果某兩個質數組合起來不如分別取最大後加起來，就不加這條邊
加了之後基本就能過了……20W的點跑了9s+
這個題是PE的355 聽說PE的那群人跑的都是模擬退火？
據說巨快……

#include 
#include 
#include 
#include 
#define M 10100
#define S 0
#define T (M-1)
#define INF 0x3f3f3f3f
using namespace std;
int n;
long long ans;
int prime[M<<2],tot;
bool not_prime[200200];
namespace Max_Cost_Max_Flow{
    struct abcd{
        int to,flow,cost,next;
    }table[100100];
    int head[M],tot=1;
    void Add(int x,int y,int f,int c)
    {
        table[++tot].to=y;
        table[tot].flow=f;
        table[tot].cost=c;
        table[tot].next=head[x];
        head[x]=tot;
    }
    void Link(int x,int y,int f,int c)
    {
        Add(x,y,f,c);
        Add(y,x,0,-c);
    }
    bool Edmonds_Karp()
    {
        static int q[65540],cost[M],from[M];
        static unsigned short r,h;
        static bool v[M];
        int i;
        memset(cost,0xef,sizeof cost);
        cost[S]=0;q[++r]=S;
        while(r!=h)
        {
            int x=q[++h];v[x]=false;
            for(i=head[x];i;i=table[i].next)
                if(table[i].flow&&cost[table[i].to]=x)
        n/=x,re*=x;
    return re;
}
int main()
{
    int i,j;
    cin>>n;
    Linear_Shaker();
    for(i=1;i<=tot&&prime[i]*2<=n;i++)
        if((long long)prime[i]*prime[i]<=n)
        {
            Max_Cost_Max_Flow::Link(S,i,1,0);
            Max_Cost_Max_Flow::Link(i,T,1,Get_Max(n,prime[i]));
        }
        else
        {
            Max_Cost_Max_Flow::Link(i,T,1,0);
            Max_Cost_Max_Flow::Link(S,i,1,prime[i]);
        }
    for(;i<=tot;i++)
        ans+=prime[i];
    for(i=1;i<=tot&&(long long)prime[i]*prime[i]<=n;i++);
    for(;i<=tot&&prime[i]*2<=n;i++)
        for(j=1;j<=tot&&(long long)prime[j]*prime[j]<=n;j++)
        {
            if(prime[i]*prime[j]>n)
                break;
            int temp=Get_Max(n/prime[i],prime[j])*prime[i];
            if(temp>Get_Max(n,prime[j])+prime[i])
                Max_Cost_Max_Flow::Link(j,i,1,temp);
        }
    while( Max_Cost_Max_Flow::Edmonds_Karp() );
    cout<