描述

---

连续从1开始编号的球,按照顺寻一个个放在n个柱子上,\(i\)放在\(j\)上面的必要条件是\(i+j\)是一个完全平方数.问做多能放到几号球.

 

分析

---

cogs是简化版,我在网上找了个完整版的测试数据,要求输出方案...

求最大放几号球不方便,我们考虑枚举最大的球号,计算最少需要多少柱子.

我们对于满足\(j<i\)且\(i+j\)是一个完全平方数的\(i,j\),从\(j\)向\(i\)连一条边.那么我们要用几条路径,将全部点都连成几串.这个路径就相当于是柱子啦.所以这就是一个求最小路径覆盖的问题.

注意!!!是最小路径覆盖!不是最小边覆盖!!!

我们把每个点\(i\)拆成\(i\)和\(i'\),建立二分图,如果\(i,j\)满足条件,就从\(j\)向\(i'\)连一条边.

对于一个路径覆盖中的一条路径,除了路径末端的那个点,也就是一个柱子最下面的那个球,其他点都有一个后继,在二分图中我们让这些点和它们的后继匹配.

这样的话,由于路径数=路径末端点的个数=点的总数-非末端点的个数=点的总数-二分图中的匹配数,所以我们做一下二分图匹配就可以了.

由于随着球号的增大,最少需要的柱子数量是单调不降的,所以可以二分.但是二分的话每次都要重新建图跑最大流,如果顺次枚举的话,每次只需要加一些边,然后在原来的残量网络中继续跑就OK了.

至于输出方案,最后跑一遍最大球号对应的最大流,然后在二分图的右侧找容量是1的边(从左边流过来1的流量,那么右边回去的容量就会+1),把每个球上面的球号记下来,然后输出的时候从1开始,只要当前这个球还没有输出,就从这个球开始向上一直输出.

 

注意:

1.虽然答案最大是1600,但是完全平方数可能不止这么大,例如:\(1000+1500=2500=500^2\).

 

1 #include 
      
        2 using namespace std; 3  4 const int maxn=1600+5,opposite=1600,maxm=1000000+5,INF=0x3fffffff; 5 int n,cnt=1,s,t,max_flow,ans; 6 int head[maxn<<1],q[maxn<<1],lv[maxn<<1],itr[maxn<<1],match[maxn]; 7 bool issquare[maxn<<1],vis[maxn]; 8 struct edge{ 9     int to,cap,next;10     edge(){}11     edge(int to,int cap,int next):to(to),cap(cap),next(next){}12 }g[maxm];13 void add_edge(int u,int v,int cap){14     g[++cnt]=edge(v,cap,head[u]); head[u]=cnt;15     g[++cnt]=edge(u,0,head[v]); head[v]=cnt;16 }17 void bfs(){18     int front=0,tail=1;19     q[front]=s;20     memset(lv,-1,sizeof lv); lv[s]=0;21     while(front
       
        0){26                 lv[v]=lv[u]+1;27                 q[tail++]=v;28             }29         }30     }31 }32 int dfs(int u,int f){33     if(u==t) return f;34     for(int &i=itr[u];i;i=g[i].next){35         int v=g[i].to;36         if(g[i].cap>0&&lv[u]
        
         0){39                 g[i].cap-=d;40                 g[i^1].cap+=d;41                 return d;42             }43         }44     }45     return 0;46 }47 void Dinic(){48     int flow=0,f;49     for(bfs();lv[t]>0;bfs()){50         for(int i=s;i<=t;i++) itr[i]=head[i];51         while((f=dfs(s,INF))>0) flow+=f;52     }53     max_flow+=flow;54 }55 void solve(){56     max_flow=0;57     for(int i=1;;i++){58         ans=i-1;59         add_edge(s,i,1);60         add_edge(i+opposite,t,1);61         for(int j=1;j
         
          n) break;64     }65     memset(head,0,sizeof head); cnt=1; max_flow=0;66     for(int i=1;i<=ans;i++){67         add_edge(s,i,1);68         add_edge(i+opposite,t,1);69         for(int j=1;j
         
        
       
      

 

算法实现题 8-4 魔术球问题(习题 8-14)

«问题描述:

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

(1)每次只能在某根柱子的最上面放球。

(2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可

放 11 个球。

«编程任务:

对于给定的 n,计算在 n 根柱子上最多能放多少个球。

«数据输入:

由文件 input.txt 提供输入数据。文件第 1 行有 1 个正整数 n,表示柱子数。

«结果输出:

程序运行结束时,将 n 根柱子上最多能放的球数以及相应的放置方案输出到文件

output.txt 中。文件的第一行是球数。接下来的 n 行,每行是一根柱子上的球的编号。

输入文件示例

input.txt

4

输出文件示例

output.txt

11

1 8

2 7 9

3 6 10

4 5 11