题目传送门：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;
}
Thanks for sharing, this is a fantastic blog.Thanks Again. Cool.
WOW just what I was looking for. Came here by searching for quest bars cheap
First of all I would like to say excellent blog! I had a quick question in which I’d like to ask if you do not mind.
I was curious to find out how you center yourself and clear your thoughts prior to writing.
I have had a tough time clearing my thoughts in getting my thoughts out.
I do enjoy writing however it just seems like the first 10 to 15 minutes tend to be wasted just trying to figure out
how to begin. Any suggestions or hints? Cheers!
I know this if off topic but I’m looking into starting my own weblog and
was curious what all is needed to get set up? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet smart so I’m not 100% positive.
Any suggestions or advice would be greatly appreciated.
Kudos
Unquestionably believe that which you said.
Your favorite justification appeared to be on the internet
the simplest thing to be aware of. I say to you,
I definitely get irked while people think about worries that they just don’t know about.
You managed to hit the nail upon the top and also
defined out the whole thing without having side-effects , people could take a
signal. Will probably be back to get more. Thanks
Tremendous issues here. I’m very happy to look
your post. Thank you a lot and I’m looking
ahead to contact you. Will you please drop me a mail?
Since the admin of this site is working, no
doubt very shortly it will be famous, due to its quality contents.
magnificent points altogether, you simply received a new reader.
What might you suggest about your put up that you simply made a few days
ago? Any certain?
Hi there, just became aware of your blog through Google, and found that it is truly informative.
I am gonna watch out for brussels. I’ll appreciate if you continue this
in future. Lots of people will be benefited from
your writing. Cheers!
After going over a handful of the articles on your web page,
I honestly appreciate your technique of blogging.
I saved as a favorite it to my bookmark site list and will be checking back in the near future.
Take a look at my website as well and let me know your opinion.
I really like looking through a post that can make people think.
Also, thank you for allowing for me to comment!
I used to be recommended this website via my cousin. I am no longer
positive whether or not this post is written through him as no
one else understand such special approximately my trouble.
You’re amazing! Thanks!
Asking questions are really good thing if you are
not understanding something entirely, except this piece of writing presents fastidious understanding yet.
Just wish to say your article is as surprising.
The clearness in your post is just spectacular and i can assume you
are an expert on this subject. Fine with your permission allow me to
grab your feed to keep updated with forthcoming post. Thanks a million and please carry on the enjoyable work.
After going over a number of the blog posts on your blog, I really appreciate your
way of writing a blog. I bookmarked it to my bookmark website list and will be checking back in the near future.
Please check out my website too and let me know your opinion.
Wonderful site. Plenty of helpful info here. I am sending it to a
few buddies ans additionally sharing in delicious. And naturally, thanks for your effort!
Hi there would you mind stating which blog platform you’re working with? I’m looking to start my own blog in the near future but I’m having a tough time making a decision between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique. P.S My apologies for being off-topic but I had to ask!
Hi everyone, it’s my first pay a visit at this web page, and article is in fact fruitful in favor of me, keep up posting these types of content.
If you want to improve your knowledge only keep visiting this web page
and be updated with the hottest information posted here.
It’s impressive that you are getting ideas from this article as well as from
our argument made here.
It is appropriate time to make some plans for the future and it is time to be happy.
I’ve read this post and if I could I want to suggest you few interesting things
or advice. Maybe you can write next articles referring
to this article. I wish to read more things about it!
Spot on with this write-up, I actually think this amazing site needs far more attention.
I’ll probably be returning to read through more, thanks for the information!
Greetings! Very useful advice in this particular article!
It is the little changes that produce the most important changes.
Thanks for sharing!
I am truly thankful to the owner of this web page who has shared this impressive article at at this place.
This design is incredible! You obviously know how
to keep a reader amused. Between your wit and
your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job.
I really loved what you had to say, and more than that, how you presented
it. Too cool!
Thankfulness to my father who shared with me
regarding this website, this webpage is genuinely amazing.
I don’t even know how I ended up here, but I thought this post was great.
I do not know who you are but certainly you’re going to a famous blogger if you aren’t already 😉 Cheers!
Excellent blog here! Also your site loads up fast! What host are you using?
Can I get your affiliate link to your host? I wish
my web site loaded up as quickly as yours lol
Very nice post. I just stumbled upon your weblog and wished to say that I’ve truly enjoyed browsing your blog posts. In any case I’ll be subscribing to your feed and I hope you write again soon!