网络流24题之四 魔术球问题
填坑
地址：luogu2765
题目描述
«问题描述：
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
«编程任务：
对于给定的n，计算在n根柱子上最多能放多少个球。
输入输出格式
输入格式：
第1 行有1个正整数n，表示柱子数。
输出格式：
程序运行结束时，将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。接下来的n行，每行是一根柱子上的球的编号。
输入输出样例
输入样例#1：
|
1 |
4 |
输出样例#1：
|
1 2 3 4 5 |
11 1 8 2 7 9 3 6 10 4 5 11 |
模型：
枚举答案转化为判定性问题，然后最小路径覆盖，可以转化成二分图最大匹配，从而用最大流解决。
实现：
枚举答案A，在图中建立节点1..A。如果对于i<j有i+j为一个完全平方数，连接一条有向边(i,j)。该图是有向无环图，求最小路径覆盖。如果刚好满足最小路径覆盖数等于N，那么A是一个可行解，在所有可行解中找到最大的A，即为最优解。
具体方法可以顺序枚举A的值，当最小路径覆盖数刚好大于N时终止，A-1就是最优解。
分析
由于是顺序放球，每根柱子上的球满足这样的特征，即下面的球编号小于上面球的编号。抽象成图论，把每个球看作一个顶点，就是编号较小的顶点向编号较大的顶点连接边，条件是两个球可以相邻，即编号之和为完全平方数。每根柱子看做一条路径，N根柱子要覆盖掉所有点，一个解就是一个路径覆盖。
最小路径覆盖数随球的数量递增不递减，满足单调性，所以可以枚举答案（或二分答案），对于特定的答案求出最小路径覆盖数，一个可行解就是最小路径覆盖数等于N的答案，求出最大的可行解就是最优解。本问题更适合枚举答案而不是二分答案，因为如果顺序枚举答案，每次只需要在残量网络上增加新的节点和边，再增广一次即可。如果二分答案，就需要每次重新建图，大大增加了时间复杂度。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include <cstdio> #include <algorithm> #include <queue> #include <cstring> #include <cmath> #define M 200010 #define N 10010 #define T 10000 #define CUT 5000 #define min(x,y) ((x<y)?(x):(y)) using namespace std; struct node { int from,to,next,flow; }e[M]; int tot=-1,st[M],dis[N],used[N],to[N]; int n,m,x,y,z; void add(int x,int y,int z) { e[++tot].to=y; e[tot].from=x; e[tot].flow=z; e[tot].next=st[x]; st[x]=tot; } int bfs(int s,int t) { int now; queue<int>que; memset(dis,-1,sizeof dis); dis[s]=1; que.push(s); while (!que.empty()) { int now=que.front(); que.pop(); for (int i=st[now];~i;i=e[i].next) if (dis[e[i].to]<0&&e[i].flow>0) dis[e[i].to]=dis[now]+1, que.push(e[i].to); } if (dis[t]>0) return 1; return 0; } int finds(int x,int y,int low) { int ans; if (x==y) return low; for (int i=st[x];~i;i=e[i].next) if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow)))) { e[i].flow-=ans; e[i^1].flow+=ans; return ans; } return 0; } int Dinic(int s,int t) { int flow=0; while(bfs(s,t)) { while(x=finds(s,t,0x3f3f3f3f)) flow+=x; } return flow; } void add_edge(int x,int y,int z) {add(x,y,z),add(y,x,0);} //枚举答案s，在图中建节点1,2,….,s，并将每个节点拆成两个点，一个连接原点，一个连接汇点， //对于每一个i< s，如果存在i+s是一个平方数，那么就将i与原点连接的点和s与汇点连接的点建边。 //每次求一遍最大流a，如果a-1==n，那么s-1即为所求解。 main() { memset(e,-1,sizeof e); memset(st,-1,sizeof st); scanf("%d",&n); int ans=0,s=0; while(1) { ans++,s++; for (int i=1;i<s;i++) if (sqrt(i+s)==(int)sqrt(i+s)) add_edge(i,s+CUT,1); add_edge(0,s,1),add_edge(s+CUT,T,1); ans-=Dinic(0,T); if (ans>n) break; } printf("%d\n",s-1); for(int i=1;i<s;i++) for(int j=st[i];~j;j=e[j].next) { if(e[j].flow)continue; to[i]=e[j].to-CUT; break; } for(int i=1;i<s;i++) { if(used[i])continue; int t=i; while(t!=-CUT) { printf("%d ",t); used[t]=true; t=to[t]; } puts(""); } } |