loj6003「网络流 24 题」魔术球

loj6003「网络流 24 题」魔术球

(​​ 题目描述

假设有 n n n 根柱子，现要按下述规则在这 n n n 根柱子中依次放入编号为 1,2,3,4,⋯ 1, 2, 3, 4, \cdots 1,2,3,4,⋯ 的球。

每次只能在某根柱子的最上面放球。在同一根柱子中，任何 2 2 2 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 n n n 根柱子上最多能放多少个球。 输入格式

文件第 1 1 1 行有 1 1 1 个正整数 n n n，表示柱子数。 输出格式

第一行是球数。接下来的 n n n 行，每行是一根柱子上的球的编号。 样例 样例输入

4

样例输出

11 1 8 2 7 9 3 6 10 4 5 11

数据范围与提示

1≤n≤55 1 \leq n \leq 55 1≤n≤55

和路径覆盖问题区别不大 问题在于这次我要求最大数量 那么我就每次枚举一个大小 然后看填满他需要的最小路径数是多少 当我最小路径数第一次>我给的n时说明这时候我枚举的s-1就是答案

然后按照最小路径覆盖问题输出答案即可

#include#include#include#include#define N 11000#define inf 0x3f3f3f3fusing namespace std;struct node{ int y,z,next;}data[N*20];int h[N],level[N],ans,n,s,num=1,T;bool visit[N];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;}inline bool bfs(){ memset(level,0,sizeof(level));queueq;level[0]=1;q.push(0); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if (y==T) return 1; } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[x]+1==level[y]&&z){ int xx=dfs(y,min(s,z));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}int main(){ scanf("%d",&n);T=10001; while(1){ ans++;s++; for (int i=1;in) break; }s--;printf("%d\n",s); for (int i=1;i<=s;++i){ if (visit[i]) continue;int now=i;bool flag=0; do{ printf("%d ",now);flag=0;visit[now]=1; for (int j=h[now];j;j=data[j].next) if (!data[j].z&&data[j].y>5000&&data[j].y<=10000){now=data[j].y-5000;flag=1;break;} }while(flag);puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。