网络流24题之--魔术球问题

题面

其实没有范围

但是没有范围也没有关系。

声明：由于某些特殊原因，边i,j表示一条从i到j的有向边

求n根柱子最多几个球比较麻烦，但求n个球最少几根柱子会简单些。

显然j可以放在i上面的条件是i<j并且$i+j=k^2$，其中k是整数。

所以如果满足条件就连一条$i,j$边。

然后最少用的柱子数就是最小路径覆盖数。

把每个点拆成两个点：入点$X_i$，出点$Y_i$。

对于每一对满足条件的 $ i,j$ ，加一条$X_i$ 到 $Y_j$的边。

则n-MAX就是答案，其中MAX为最大匹配数。

具体的证明：

一开始先把n个球全部放在不同的柱子上。

然后匹配的每一条边$(X_i,Y_j)$表示把球j直接放在球i上面，就会少用一根柱子。

显然每个点不能被匹配两次，因为一个球不能有两个球都在它上面还紧挨着它，下面也一样。

然后显然少用的柱子数越多越好。

现在返回来考虑。

我们可以考虑每次加一个球，然后维护最大匹配。

如果在加上第k个球后只需要不超过n个柱子，但是k+1时就需要n+1个了，那么答案为k

维护最大匹配可以用匈牙利算法，也可以用网络流。

我写的匈牙利（似乎这样好输出方案些？？）。

/*
Author: CNYALI_LK
LANG: C++
PROG: 2765.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
    int cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
    putchar(end);
}
int beg[233333],to[1024244],lst[1024242],e;
int isss[1024242];
void add(int u,int v){
    to[++e]=v;
    lst[e]=beg[u];
    beg[u]=e;
}
int visx[233333],is[233333];
int dfs(int x){
    if(visx[x])return 0;
    visx[x]=1;
    for(int i=beg[x];i;i=lst[i])
        if(!is[to[i]]){
            is[to[i]]=x;
            return 1; 
        }
        else{
            if(dfs(is[to[i]])){
                is[to[i]]=x;
                return 1;
            }
        }
    return 0;
}
void fu(int x){
    while(x){
        printf("%d ",x);
        visx[x]=1;
        x=is[x];
    }
    putchar('\n');
}
int main(){
#ifdef cnyali_lk
    freopen("2765.in","r",stdin);
    freopen("2765.out","w",stdout);
#endif
    int n;
    n=read();
    int m;
    m=0;
    for(int i=1;i<=256;++i)isss[i*i]=1;
    while(n+1){
        ++m;
        for(int j=1;j<m;++j)if(isss[m+j]){
            add(m,j);   
        }
        for(int i=1;i<=m;++i){
            visx[i]=0;
        }
        --n+=dfs(m);
    }
    printf("%d\n",--m);
    for(int i=1;i<=m;++i)visx[i]=0;
    for(int i=1;i<=m;++i)if(!visx[i])fu(i);
    return 0;
}