【线性规划与网络流24题 4】魔术球

Description

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

Input

第1 行有 1个正整数n，表示柱子数。(0<n<60)

Output

/*
程序运行结束时，将 n 根柱子上最多能放的球数以及相应的放置方案输出。
文件的第一行是球数。接下来的n行，每行是一根柱子上的球的编号。
按字典序输出方案
*/
一行，包含一个整数，表示最多能放的球数

Sample Input

Sample Output

这个题难点在于：题目中建模的转化：跟流量有什么关系吗？

其实是有的：要求最多能放的球数，因为柱子数是固定的，那么：重叠的球数越多越好？！（不是废话吗）

当然不是：用流量的思路来说，就是要求最大流啊

所以主要思路是：枚举答案转化为判定性问题，然后最小路径覆盖，可以转化成二分图最大匹配，从而用最大流解决

第一点：为什么是枚举答案而不是二分？

在网络流中，建图是一个很大的板块（花很多时间和空间）

如果是枚举答案，只需要在原来的图上继续寻找增广路就可以了

如果是二分，那么需要重新建图，会很麻烦

第二点：如何拆点？

因为点数不定（是不断增加的）

那么，就不能采取i，i+n的这种平移形式的拆点

所以，用i<<1和i<<1|1是很好的方法

第三点：最小路径覆盖怎么弄？

把每个球看作一个顶点，就是编号较小的顶点向编号较大的顶点连接边，条件是两个球可以相邻，即编号之和为完全平方数

每根柱子看做一条路径，N根柱子要覆盖掉所有点，一个解就是一个路径覆盖

枚举A的值，当最小路径覆盖数刚好大于N时终止，A-1就是最优解

第四点：如何找方案？

dfs找匹配的点

因为每条边的容量都是1，如果这个点在方案中，那么在数组的flow中是有标记的

另外注意每个点连的，是另外一个点拆点之后的点，需要分清楚是哪一个，dfs一直走到头即可

代码如下：

#include<bits/stdc++.h>
using namespace std;

bool issqr(int x){
	int y=int(sqrt(x*1.0));
	if (x==y*y) return true;
	return false;
}

const int maxn=11000;
const int maxm=1200010;
const int INF=999999;

int n,m,k;
struct Edge{
	int to,nxt,cap,flow;
}edge[maxm];
int tol,Head[maxn];
bool flag[maxn];
int path[maxn],num;

void init(){
	memset(Head,-1,sizeof(Head));
	tol=2;
}

void addedge(int u,int v,int w,int rw=0){
	edge[tol].to=v;
	edge[tol].cap=w;
	edge[tol].flow=0;
	edge[tol].nxt=Head[u];
	Head[u]=tol++;
	
	edge[tol].to=u;
	edge[tol].cap=rw;
	edge[tol].flow=0;
	edge[tol].nxt=Head[v];
	Head[v]=tol++;
}

int Q[maxn],dep[maxn],cur[maxn],sta[maxn];

bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep[0])*(n+1));
	dep[s]=0;
	Q[tail++]=s;
	while(front<tail){
		int u=Q[front++];
		for(int i=Head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow&&dep[v]==-1){
				dep[v]=dep[u]+1;
				if (v==t) return true;
				Q[tail++]=v;
			}
		}
	}
	return false;
}

int dinic(int s,int t,int n){
	int maxflow=0;
	while(bfs(s,t,n)){
		for(int i=0;i<n;i++) cur[i]=Head[i];
		int u=s,tail=0;
		while(cur[s]!=-1){
			if (u==t){
				int tp=INF;
				for(int i=tail-1;i>=0;i--) 
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				maxflow+=tp;
				for(int i=tail-1;i>=0;i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if (edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else{
				while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
				cur[u]=edge[cur[u]].nxt;
			}
		}
	}
	return maxflow;
}

void getpath(int u){  
    if (u>2*n) return;
    flag[u]=1;
    num++;
    path[num]=u;
    u*=2;
    for(int i=Head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if (!flag[v]&&v&&edge[i].flow)
        	getpath(v/2);
    }  
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int ans=0,s=0,t,maxflow=0;
	scanf("%d",&k);
	t=10001;n=10002;
	init();
	while(1){
		ans++;
		addedge(s,ans<<1,1);
		addedge((ans<<1)|1,t,1);
		for(int i=1;i<ans;i++)
			if (issqr(i+ans))
				addedge(i<<1,(ans<<1)|1,1);
		maxflow+=dinic(s,t,n);
		if (ans-maxflow>k) break;
	}
	//printf("%d\n",--ans);
	printf("%d\n",--ans);
	/*
	memset(flag,false,sizeof(flag));
	for(int i=1;i<=ans;i++)
		if (!flag[i]){
			num=0;
			getpath(i);
			for(int j=1;j<=num;j++)
				printf("%d%c",path[j],j==num?'\n':' ');
		}
	*/
	return 0;
}