魔术球问题

链接

题意：给定一些数，每个数可以叠在前面某一堆上面（需要满足与最上面那个成完全平方），也可以自成一列，堆数有限定，求最多的球数

做法：

网络最大流（二分图匹配）

从上面的题意整理出这样的情况：

1.一个球可以找到一个比它小的数匹配，则由这个数连向那个小的数

2.也可能一枝独秀，建立一个新堆

每加入一个数，通过1情况连接对应边，进行一次二分图匹配，看能不能匹配到某个点，如果可以，则表明可以放在某个数上面，暂时放在这上面；如果不能，则只能自成一派。当总堆数超过限制时停止加数字。

实际上，总的数字可能比较多（1500左右），直接匈牙利算法可能过不了，可以用dinic，连边的方向可能改变

Code：

#include<bits/stdc++.h>
#define N 50000
#define INF 1000000000
using namespace std;
int n,s=0,t=(N<<1)-1,maxflow;
int sum,used;
int dep[N<<1],nxt[N<<1],fir[100];

struct Edge
{
    int next,to,flow;
}edge[N<<4];int head[N<<1],cnt=1;
void add_edge(int from,int to,int flow)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].flow=flow;
    head[from]=cnt;
}
void add(int from,int to,int flow)
{
    add_edge(from,to,flow);
    add_edge(to,from,0);
}

int bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int> q; while(!q.empty()) q.pop();
    q.push(s); dep[s]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(!dep[v]&&edge[i].flow)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t];
}
int dfs(int u,int limit)
{
    if(u==t||!limit) return limit;
    int k,flow=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dep[v]==dep[u]+1&&(k=dfs(v,min(limit,edge[i].flow))))
        {
            if(v!=t) nxt[u>>1]=v>>1;
            edge[i].flow-=k;
            edge[i^1].flow+=k;
            limit-=k;
            flow+=k;
        }
    }
    return flow;
}
int dinic()//普通的最大流 
{
    maxflow=0;int k;
    while(bfs())
    {
        while((k=dfs(s,INF))) maxflow+=k;
    }
    return maxflow;
}

int main()
{
    scanf("%d",&n);
    while(used<=n)
    {
        sum++;add(s,sum<<1,1);add((sum<<1)|1,t,1);
        for(int i=sqrt(sum)+1;i*i<2*sum;++i)
        add((i*i-sum)<<1,(sum<<1)|1,1);
        int k=dinic();
        //将前一个数的起点于sum的终点相连 
        if(!k) fir[++used]=sum;
        //不能由其他点做起点流到汇点，只能重新开柱子自己做起点 
    }
    printf("%d\n",--sum);
    for(int i=1;i<=n;++i)
    {
        for(int j=fir[i];j;j=nxt[j]) printf("%d ",j);
        printf("\n");
    }
    return 0;
}

魔术球问题

原文：https://www.cnblogs.com/Chtholly/p/10665945.html