【网络流24题】魔术球问题

Description

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1，2，3，4......的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11个球。
´编程任务：
对于给定的n，计算在 n根柱子上最多能放多少个球。

Input

第1 行有 1个正整数n，表示柱子数。

Output

第一行是球数。

Sample Input

4

Sample Output

11

Hint

样例方案如下
1 8
2 7 9
3 6 10
4 5 11
每一行表示一个柱子上的球
n＜=60 保证答案小于1600

正解：网络流

解题报告：一个点最多上面有一个点，下面有一个点，然后我们就可以由此把图构出来，把一个点拆成两个点，分别管上和下，分别连源点与汇点，把与源点和汇点连的边容量定为1，是完全平方数的再连一条边，然后跑出的最大流就是有多少个可以接在上面，然后用当前的点数减去最大流，就是要用的柱子数，然后动态加点，当要用的柱子数超过n时，上一次的点数就是最多能放的球。

 1 #include <iostream>
 2 #include <iomanip>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <string>
 9 #define MIN(a,b) a<b?a:b
10 #define RG register
11 const int N = 100000;
12 const int M = 30000;
13 const int inf = 2147483641;
14 
15 using namespace std;
16 
17 int gi(){
18     char ch=getchar();int x=0;
19     while(ch<'0' || ch>'9') ch=getchar();
20     while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
21     return x;
22 }
23 
24 struct date{
25     int from,to,val;
26 }nn[N];
27 
28 int S,T,m=M,head[N],nxt[N],f[N],dis[N],cnt=1;
29 
30 void link(int l,int r){
31     nn[++cnt]=(date){l,r,1},nxt[cnt]=head[l],head[l]=cnt;
32     nn[++cnt]=(date){r,l,0},nxt[cnt]=head[r],head[r]=cnt;
33     return;
34 }
35 
36 int bfs(){
37     for (RG int i=S; i<=T; ++i) dis[i]=0;
38     f[1]=0,dis[0]=1;
39     int l=0,r=1;
40     while(l<r){
41         ++l;
42         for (RG int i=head[f[l]]; i; i=nxt[i])
43             if (nn[i].val && dis[nn[i].to]==0)
44                 dis[nn[i].to]=dis[f[l]]+1,
45                     f[++r]=nn[i].to;
46         if (dis[T]) return 1;
47     }
48     return 0;
49 }
50 
51 int dinic(int xh,int sum){
52     int s=0;
53     if (xh==T) return sum;
54     for (RG int i=head[xh]; i; i=nxt[i])
55         if (nn[i].val && dis[nn[i].to]==dis[xh]+1){
56             int tmp=dinic(nn[i].to,MIN(sum,nn[i].val));
57             sum-=tmp,s+=tmp,nn[i].val-=tmp,nn[i^1].val+=tmp;
58             if (sum==0) break;
59         }
60     if (s==0) dis[xh]=-1;
61     return s;
62 }
63 
64 int main(){
65     freopen("magic.in","r",stdin);
66     freopen("magic.out","w",stdout);
67     RG int n=gi(),ans=0,xh=0;T=2*M;
68     for (;;){
69         ++ans,++xh;
70         for (RG int i=1; i<xh; ++i)
71             if ((ceil)(sqrt(i+xh))==(floor)(sqrt(i+xh)))
72                 link(i,xh+m);
73         link(S,xh),link(xh+m,T);
74         while(bfs()) ans-=dinic(S,inf);
75         if (ans>n) break;
76     }
77     printf("%d",xh-1);
78     return 0;
79 }