題目描述

題解：

個人認(rèn)為網(wǎng)絡(luò)流二十三題中比較有意思的一道。

先枚舉球數(shù)。

每加一個球，從$S$向$xi$連一條容量為$1$的邊，從$yi$向$T$連一條容量為$1$的邊。

然后從$xi$向滿足$i+j$為完全平方數(shù)的$yj$連容量為$1$的邊。

在殘余網(wǎng)絡(luò)上跑$EK$或$Dinic$，如果得到的最大流為$0$，說明失配，需要重開一柱。

其實(shí)就是動態(tài)的二分圖匹配。

每個球后面只能接一個球嘛。

代碼：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 6050
const int inf = 0x3f3f3f3f;
int n,S,T;
int m,tot;
int hed[N],cnt=-1,cur[N];
struct EG
{
    int to,nxt,w;
}e[2000050];
void ae(int f,int t,int w)
{
    e[++cnt].to = t;
    e[cnt].nxt = hed[f];
    e[cnt].w = w;
    hed[f] = cnt;
}
int dep[N];
bool vis[N];
queue<int>q;
bool bfs()
{
    memset(dep,0x3f,sizeof(dep));
    memcpy(cur,hed,sizeof(cur));
    dep[S] = 0;
    vis[S] = 1;
    q.push(S);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int j=hed[u];~j;j=e[j].nxt)
        {
            int to = e[j].to;
            if(e[j].w&&dep[to]>dep[u]+1)
            {
                dep[to] = dep[u]+1;
                if(!vis[to])
                {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
        vis[u] = 0;
    }
    return dep[T]!=inf;
}
int dfs(int u,int lim)
{
    if(u==T||!lim)return lim;
    int fl=0,f;
    for(int j=hed[u];~j;j=e[j].nxt)
    {
        int to = e[j].to;
        if(dep[to]==dep[u]+1&&(f=dfs(to,min(lim,e[j].w))))
        {
            fl+=f,lim-=f;
            e[j].w-=f,e[j^1].w+=f;
            if(!lim)break;
        }
    }
    return fl;
}
int dinic()
{
    int ret = 0;
    while(bfs())ret+=dfs(S,inf);
    return ret;
}
bool use[N];
void print(int u)
{
    printf("%d ",u);
    for(int j=hed[u<<1|1];~j;j=e[j].nxt)
    {
        int to = e[j].to;
        if(to==T||use[to>>1])continue;
        if(!e[j].w)continue;
        use[to>>1]=1;
        print(to>>1);
        break;
    }
}
int main()
{
    scanf("%d",&n);
    memset(hed,-1,sizeof(hed));
    S = 0,T = 1;
    for(m=1;;m++)
    {
        ae(S,m<<1,1);ae(m<<1,S,0);
        ae(m<<1|1,T,1);ae(T,m<<1|1,0);
        for(int i=1;i*i<2*m;i++)
            if(i*i>m)ae(m<<1,(i*i-m)<<1|1,1),ae((i*i-m)<<1|1,m<<1,0);
        if(!dinic())tot++;
        if(tot>n)break;
    }
    printf("%d
",m-1);
    for(int i=1;i<m;i++)
    {
        if(use[i])continue;
        use[i]=1;
        print(i);
        puts("");
    }
    return 0;
}

總結(jié)

以上是生活随笔為你收集整理的魔术球问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。