题目传送门:http://cojs.tk/cogs/problem/problem.php?pid=396
这题,大家都说贪心可以过QAQ
但我总觉得贪心有问题…
贪心那块,不会证明小于a且a+b为完全平方数的数至多存在一个解
于是还是最小路径覆盖比较靠谱吧!
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000; const int INF = 10000000; int head[N],to[N],nxt[N],flow[N],dis[N],cur[N]; int n,m,S,T; queue<int> que; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } #define id(x,ty) ((x)*2+ty) inline int Add_Edge(int u, int v, int f) { static int TT = 1; to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1; to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; return TT - 1; } inline bool BFS(){ memset(dis,-1,sizeof(dis)); que.push(S); dis[S] = 0; while (!que.empty()) { int w = que.front(); que.pop(); for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) dis[to[i]] = dis[w] + 1, que.push(to[i]); } return ~dis[T]; } inline int DFS(int w, int f) { if (w == T) return f; else { int ret = 0; for (int &i=head[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) { int tmp = DFS(to[i], min(f, flow[i])); flow[i] -= tmp; flow[i^1] += tmp; ret += tmp; f -= tmp; if (!f) break; } return ret; } } inline int Dinic(){ int ret = 0; while (BFS()) { memcpy(cur,head,sizeof(head)); ret += DFS(S,INF); } return ret; } int main(){ freopen("balla.in","r",stdin); freopen("balla.out","w",stdout); n = read(); S = 0; T = 1; for (int i=1,w=0;i<=1600;i++) { Add_Edge(S,id(i,0),1); Add_Edge(id(i,1),T,1); for (int j=i-1;j;j--) if (i + j == (int)sqrt(i+j)*(int)sqrt(i+j)) Add_Edge(id(i,0),id(j,1),1); w += Dinic(); if (i - w > n) cout<<i-1, exit(0); } return 0; }