记录编号	175468	评测结果	AAAAAAAAAA
题目名称	[网络流24题]魔术球问题（简化版）	最终得分	100
用户昵称	雾腾腾	是否通过	通过
代码语言	C++	运行时间	0.441 s
提交时间	2015-08-05 21:41:17	内存使用	1.96 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
const int inf = 1 << 30;
const int maxa = 1600;
using namespace std;

int n, ecnt;
int ans, maxflow, d[maxa * 2 + 5], cnt[maxa * 2 + 5], N, adj[maxa * 2 + 5];
bool num[maxa * 2 + 5];

void CSN()
{
	for(int i = 1; i * i <= maxa * 2; i ++)
		num[i * i] = 1;
}

struct Edge
{
	int v, w, Next;
}edge[maxa * 100 + 5];

void addedge(int u, int v, int w)
{
	edge[++ecnt].v = v;
	edge[ecnt].w = w;
	edge[ecnt].Next = adj[u];
	adj[u] = ecnt;
}

int aug(int cur, int augco)
{
	if(cur == N)return augco;
	int mind = N - 1, delta, augc = augco;
	for(int p = adj[cur]; p; p = edge[p].Next){
		int v = edge[p].v, w = edge[p].w;
		if(w <= 0)continue;
		if(d[v] == d[cur] - 1){
			delta = min(w, augc);
			delta = aug(v, delta);
			augc -= delta;
			edge[p].w -= delta;
			if(delta) addedge(v, cur, delta);
			if(!augc)break;
			if(d[1] >= N)return augco - augc;
		}
		mind = min(mind, d[v]);
	}
	if(augco == augc){
		cnt[d[cur]] --;
		if(!cnt[d[cur]])d[1] = N;
		d[cur] = mind + 1;
		cnt[d[cur]] ++;
	}
	return augco - augc;
}

int solve(int x)
{
	memset(cnt, 0, sizeof cnt);
	memset(d, 0, sizeof d);
	cnt[0] = N;
	while(d[1] < N)
		maxflow += aug(1, inf);
	return x - maxflow;
}

void Do(int st)
{
	N = maxa * 2 + 2;
	for(int i = 1; i <= maxa; i ++)
		addedge(1, 2 * i, 1), addedge(2 * i + 1, N, 1);
	for(int i = 1; i <= maxa; i ++){
		for(int j = 1; j < i; j ++)
			if(num[i + j])
				addedge(2 * j, 2 * i + 1, inf);
		ans = solve(i);
		if(ans == n + 1){
			printf("%d", i - 1);return;
		}
	}
}

int main()
{
	freopen("balla.in", "r", stdin);
	freopen("balla.out", "w", stdout);
	scanf("%d", &n);
	CSN();
	Do(n);
}