记录编号	258373	评测结果	AAAAAAAAAA
题目名称	[网络流24题]魔术球问题（简化版）	最终得分	100
用户昵称	粘粘自喜	是否通过	通过
代码语言	C++	运行时间	2.017 s
提交时间	2016-05-05 18:42:40	内存使用	1.78 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int inf=1000000000;
const int maxn=20000,maxm=50000;
int squ[maxn];
int cur[maxn];
struct Edge{
	int v,f,nxt;
};
int n,src,sink;
int g[maxn+10];
int nume;

Edge e[maxm*2+10];
void addedge(int u,int v,int c){
	e[++nume].v=v;
	e[nume].f=c;
	e[nume].nxt=g[u];
	g[u]=nume;
	e[++nume].v=u;
	e[nume].f=0;
	e[nume].nxt=g[v];
	g[v]=nume;
}
void init()
{
	memset(g,0,sizeof(g));
	nume=1;
}
queue<int> q;
bool vis[maxn+10];
int dist[maxn+10];
inline void bfs()
{
	memset(dist,0,sizeof(dist));
	while(!q.empty()) q.pop();
	vis[src]=true;
	q.push(src);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=g[u];i;i=e[i].nxt)
			if(e[i].f&&!vis[e[i].v]){
				q.push(e[i].v);
				dist[e[i].v]=dist[u]+1;
				vis[e[i].v]=true;
			}
	}
	
}
inline int dfs(int u,int delta){
	if(u==sink){
		return delta;
	}else{
		int ret=0;
		for(int i=g[u];delta&&i;i=e[i].nxt)
			if(e[i].f&&dist[e[i].v]==dist[u]+1){
				int dd=dfs(e[i].v,min(e[i].f,delta));
				e[i].f-=dd;
				e[i^1].f+=dd;
				delta-=dd;
				ret+=dd;
						}
				return ret;
	}
}
int Dinic()
{
	int ret=0;
	while(1){
		memset(vis,0,sizeof(vis));
		bfs();
		if(!vis[sink]) return ret;
		ret+=dfs(src,inf);
	}
}
int main()
{
	freopen("balla.in","r",stdin);
	freopen("balla.out","w",stdout);
	int n,i,j,k;
	for(i=1;i*i<4001;i++)  
        squ[i*i]=1;  
    scanf("%d",&n);
    
        init();  
        src=0;sink=1;  
        for(i=1;i<4001;i++){  
            addedge(src,i<<1,1),addedge((i<<1)+1,sink,1);  
            for(j=1;j<i;j++)  if(squ[j+i])  
                addedge(j<<1,(i<<1)+1,1); 
				for(k=0;k<nume;k+=2)  
                e[k].f+=e[k^1].f,e[k^1].f=0;   
            if(i-Dinic()>n) break;  
        }  
        printf("%d\n",i-1); 
    return 0;  
}