记录编号	278337	评测结果	AAAAAAAAAA
题目名称	[网络流24题]魔术球问题（简化版）	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.379 s
提交时间	2016-07-07 17:19:24	内存使用	4.16 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using std::min;
using std::queue;
const int INF=1e9,MAXV=(1600+10)*2,MAXE=2e5; 
int n,ans;
bool square(int a){
	int sq=sqrt(a);
	return a==sq*sq; 
}
struct Dinic{
	struct EDGE{int u,v,c,f;}st[MAXE];
	int s,t,lv[MAXV],nowe[MAXV],head[MAXV],nxt[MAXE],sz;
	Dinic(){
		sz=1;
		s=1600*2+1,t=1600*2+2; 
	}
	void sadd(int u,int v,int c){
		st[++sz].u=u,st[sz].v=v,st[sz].c=c;
		nxt[sz]=head[u],head[u]=sz;
	} 
	void add(int u,int v){
		sadd(u,v,1),sadd(v,u,0);
	}
	bool bfs(){
		memset(lv,0,sizeof(lv));
		lv[s]=1;
		queue<int> q;
		q.push(s);
		while(!q.empty()) {
			int u=q.front();q.pop();
			for(int e=head[u];e;e=nxt[e]) if(st[e].c>st[e].f&&!lv[st[e].v])  lv[st[e].v]=lv[u]+1,q.push(st[e].v);
		}
		return lv[t];
	}
	void clnowe(){
		for(int i=1;i<=MAXV;i++) nowe[i]=head[i];
	}
	int dfs(int u,int a){
		if(u==t) return a;
		int flow=0,f;
		for(int& e=nowe[u];e;e=nxt[e]) if(st[e].c>st[e].f&&lv[st[e].v]==lv[u]+1&&(f=dfs(st[e].v,min(st[e].c-st[e].f,a)))){
			flow+=f,st[e].f+=f,st[e^1].f-=f,a-=f;
			if(!a) break;
		}
		if(!a) lv[u]=-1;
		return flow;
	}
	int maxf(){
		static int flowg=0;
		while(bfs()) clnowe(),flowg+=dfs(s,INF);
		//printf("%d\n",flowg);
		return flowg;
	}
	int minpath(){
		add(s,ans),add(ans+1600,t);
		for(int i=1;i<ans;i++) if(square(i+ans)) add(i,ans+1600);//,printf("%d->%d\n",i,ans);
		return ans-maxf();
	}
}foo;
int main(){
	freopen("balla.in","r",stdin);
	freopen("balla.out","w",stdout);
	scanf("%d",&n);
	for(ans=1;ans<=1600;ans++) if(foo.minpath()>n) break;
	printf("%d",ans-1);
}