网络流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;
}