[题解]P2765 |魔术球问题

zh_dou · 2019-09-19 11:45:43 · 题解

魔术球问题

通过观察题面，我们发现柱子好像并没有什么用，于是考虑枚举球

每次向残量网络中加入代表球的点和边，如果有增量，说明这个球利用了现有的柱子，否则就要多加一个柱子

由于并不预先知道球的数量，也就是答案，所以说 t 要开大一点

然后在我们透彻网络流时，Dinic算法中的 dfs 是处理的每一次 bfs 所发现的增量

所以我们不断向图中加边、加点，直到柱子不够用

此时 --num 便是答案

在加边时，

因为一个球只能放一次 , s\xrightarrow{1}i\ ,\ i'\xrightarrow{1}t

对于 j<i 且 i+j 为完全平方数， 连边i\xrightarrow{1}j'

若增量为0，则新开一个柱子

#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 50030
#define int long long
#define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n"
inline int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*y;
}
int n,m,s,t,dep[N];
int head[N],tot=1,front,used[N];
int ans;
int table[N],vis[N],after[N];
struct Node{
    int nxt,to,dis;
}edge[N<<2];
inline void add(int x,int y,int z){
    edge[++tot].nxt=head[x];
    edge[tot].to=y;
    edge[tot].dis=z;
    head[x]=tot;
}
queue<int> q;
inline int bfs(){
    register int i;
    for(i=0;i<=N-10;i++) dep[i]=-1, used[i]=head[i];
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        front=q.front();q.pop();
//      cout<<front<<" ";debug;
        for(i=head[front];i;i=edge[i].nxt){
            if(edge[i].dis&&dep[edge[i].to]==-1){
                dep[edge[i].to]=dep[front]+1;q.push(edge[i].to);
            }
        }
    }
//  debug;
    return dep[t]!=-1;
}
int dfs(int now,int limit){
    if(!limit||now==t) return limit;
    int flow=0;
    for(int &i=used[now],pro;i;i=edge[i].nxt){
        if(dep[edge[i].to]==dep[now]+1&&edge[i].dis){
            pro=dfs(edge[i].to,min(limit,edge[i].dis));
            if(!pro) continue;
            edge[i].dis-=pro;
            edge[i^1].dis+=pro;
            flow+=pro;
            limit-=pro;
//          cout<<now<<" "<<edge[i].to<<"\n";
            if(edge[i].to!=t) after[now>>1]=edge[i].to>>1;
            if(!limit) return flow;
        }
    }
//  cout<<flow<<" ";debug;
//  system("pause");
    return flow;
}
inline void Dinic(){
    while(bfs()){ans+=(dfs(s,10000000001LL));}
}
signed main(){
//  freopen("a.in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();
    s=0;t=50001;
    int now=0,num=0;
    while(now<=n){
        ++num;
        add(s,num<<1,1);add(num<<1,s,0);
        add(num<<1|1,t,1);add(t,num<<1|1,0);
        for(int i=sqrt(num)+1;i*i<(num<<1);i++) add((i*i-num)<<1,num<<1|1,1),add(num<<1|1,(i*i-num)<<1,0);
        ans=0;Dinic();
        if(ans==0) table[++now]=num;
//        cout<<num<<" "<<now<<"\n";
    }
    cout<<--num<<"\n";
    for(int i=1,k;i<=n;i++){
        if(!vis[table[i]]){
            cout<<(k=table[i]);vis[k]=1;
            while(after[k]>0&&after[k]!=t>>1){
                cout<<" "<<(k=after[k]);
                vis[k]=1;
            }
            cout<<"\n";
        }
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}