原题链接

Description

假设有n(n≤55)根柱子，现要按下述规则在这n根柱子中依次放入编号为1,2,3,4,⋯的球。

1. 每次只能在某根柱子的最上面放球。
2. 在同一根柱子中，任何2个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在n根柱子上最多能放多少个球。

Solution

如果u+v(u<v)是完全平方数则连有向边(u,v)，那么一个柱子上的球就相当于图中的一条路径。二分答案，以是否能用不超过n条路径覆盖作为条件。

Code

//「网络流 24 题」魔术球

#include <cstdio>

#include <cstring>

int const N=1e4+10;

int n,ans[100]={0,1,3,7,11,17,23,31,39,49,59,71,83,97,111,127,143,161,179,199,219,241,263,287,311,337,363,391,419,449,479,511,543,577,611,647,683,721,759,799,839,881,923,967,1011,1057,1103,1151,1199,1249,1299,1351,1403,1457,1511,1567};

int cnt,h[N];

struct edge{int v,nxt;} ed[N*100];

void edAdd(int u,int v) {cnt++; ed[cnt].v=v,ed[cnt].nxt=h[u],h[u]=cnt;}

int link[N]; bool used[N];

int find(int u,int lim)

{

    for(int i=h[u];i;i=ed[i].nxt)

    {

        int v=ed[i].v;

        if(used[v]||v>lim) continue;

        used[v]=true;

        if(!link[v]||find(link[v],lim)) {link[v]=u; return true;}

    }

    return false;

}

int Hungrian(int lim)

{

    int ans=0; memset(link,0,sizeof link);

    for(int i=1;i<=lim;i++)

    {

        memset(used,0,sizeof used);

        if(find(i,lim)) ans++;

    }

    return ans;

}

int pre[N],nxt[N];

int main()

{

    scanf("%d",&n);

    cnt=0; memset(h,0,sizeof h);

    for(int i=1;i<=n;i++)

        for(int u=1;u<i*i-u;u++) edAdd(u,i*i-u);

    Hungrian(ans[n]);

    printf("%d\n",ans[n]);

    for(int i=1;i<=ans[n];i++) pre[i]=link[i],nxt[link[i]]=i;

    for(int i=1;i<=ans[n];i++)

    {

        if(pre[i]) continue;

        for(int u=i;u;u=nxt[u]) printf("%d ",u);

        printf("\n");

    }

    return 0;

 } 

P.S.

比较有毒的是本机TLE但交上去很快…速度大概差十倍吧。我为了不T还打了表= = hzwer的源码本机2s+交上去115ms