首页 > 代码库 > 【网络流24题----04】软件补丁问题魔术球问题
【网络流24题----04】软件补丁问题魔术球问题
问题描述：
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1，2，3，4......的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可
放11个球。
´编程任务：
对于给定的n，计算在 n根柱子上最多能放多少个球。
´数据输入：
文件第1 行有 1个正整数n，表示柱子数。
´结果输出:
文件的第一行是球数。
数据规模
n<=60 保证答案小于1600
输入文件示例
4
输出文件示例
11
方案如下
1 8
2 7 9
3 6 10
4 5 11
每一行表示一个柱子上的球
如果不要输出方案好题立马变水题（可以用式子直接输出答案）
假设我不知道式子：问题变成最小路径覆盖，并且路径不能相交，如果一个数加上一个比他大的数是完全平方数，直接连有向边即可。
枚举答案，每次往如图中放入一个点，然后再残量网络上继续更新答案，判断所需路径数是否>n即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 500010 #define llg int11 #define inf (llg)1e16 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 llg m,r[maxn],c[maxn],tot,k,N=4999;14 15 struct DINIC16 {17 vector<llg>a[maxn],ba[maxn],val[maxn];18 llg dl[maxn],deep[maxn],bj[maxn];19 20 void insert(llg x,llg y,llg z)21 {22 a[x].push_back(y),val[x].push_back(z);23 a[y].push_back(x),val[y].push_back(0);24 ba[x].push_back(a[y].size()-1); ba[y].push_back(a[x].size()-1);25 }26 27 void in(llg x)28 {29 for (llg i=1;i<x;i++) 30 if (floor(sqrt(i+x))*floor(sqrt(i+x))==x+i)31 32 {33 insert(i*2,x*2-1,1);34 }35 insert(0,x*2,1);36 insert(x*2-1,N,1);37 }38 39 llg dfs(llg x,llg low)40 {41 llg va=0,inc=0;42 if (x==N) return low;43 llg w=a[x].size();44 for (llg i=0;i<w;i++)45 if (deep[x]+1==deep[a[x][i]] && val[x][i]>0 && (va=dfs(a[x][i],min(low,val[x][i]))))46 {47 val[x][i]-=va; val[a[x][i]][ba[x][i]]+=va; inc+=va;48 return va;49 }50 if (!inc) deep[x]=-1;51 return 0;52 }53 54 void fencen()55 {56 llg x,w,v; deep[0]=0;57 memset(bj,0,sizeof(bj));58 llg head=0,tail=1; dl[1]=0; bj[0]=1;59 do60 {61 x=dl[++head]; w=a[x].size();62 for (llg i=0;i<w;i++)63 {64 v=a[x][i];65 if (bj[v] || val[x][i]<=0) continue;66 dl[++tail]=v;67 deep[v]=deep[x]+1; bj[v]=1;68 }69 }while (head!=tail);70 }71 72 llg dinic()73 {74 llg ans=0;75 while (1)76 {77 fencen();78 if (!bj[N]) break;79 ans+=dfs(0,inf);80 }81 return ans;82 }83 }G;84 85 86 int main()87 {88 yyj("balla");89 llg up; cin>>up;90 for (llg i=1;;i++)91 {92 G.in(i);93 tot+=G.dinic();94 if (i-tot>up){cout<<i-1; return 0;} 95 }96 return 0;97 }
【网络流24题----04】软件补丁问题魔术球问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。