相关链接
题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=12432
中文题面:http://www.cnblogs.com/enigma-aw/p/6237246.html
神犇题解:http://metthesoul.blog.163.com/blog/static/23032003620147269343401/
解题报告
首先考虑一个简单的子问题:
给定你一个网格图,其中有一些点有障碍,不能经过
问:能否通过一些回路,使得每一个点恰好经过一次
考虑回路的性质:
- 回路中的每一个点的度一定是 $ 2$
- 如果每一个点的度都是 $ 2$ ,那么这一定是由一些回路构成的图
这样的话,这个 $ Subcase$ 就可以通过染色后二分图匹配来解决了
现在回到原问题,显然可行解的判断可以用上述算法来解决
现在来考虑 towns with Curvies
在上一个 $ Subcase$ 中使用的二分图匹配,实际上是对 度 进行匹配
现在考虑将度分类:
- 横向的度
- 纵向的度
对于 towns with Curvies 来说:如果同类的度匹配,那么就得付出代价
于是考虑将每一个点拆成一个横向的度和纵向的度
然后原图中相邻的格子,只连对应的点(纵向相邻就只连代表纵向的点)
这样的话,如果存在完备匹配,那么一定是一个两个不同类的度匹配现在再来考虑付出代价的情况:
将二分图匹配改造成费用流,已建的边费用全部为 $ 0$
然后在同一个格子拆开的点之间连一条双向、流量为 $ 1$、费用为 $ 0$ 的边
这样的话,就相当于两个匹配都使用同一类度的时候得付出 $ 1$ 的代价
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int L = 30; const int N = 2000; const int M = 50000; const int INF = 1000000000; int S,T,head[N],nxt[M],to[M],flow[M],cost[M]; int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1}; class Minimum_Cost_Flow{ int dis[N],sur[N],inq[N]; queue<int> que; public: inline pair<int,int> MaxFlow() { int ret_cost = 0, ret_flow = 0; for (int f=INF,w;SPFA();f=INF) { for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]); for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f; ret_cost += dis[T] * f; ret_flow += f; } return make_pair(ret_cost, ret_flow); } private: bool SPFA() { memset(dis,60,sizeof(dis)); que.push(S); dis[S] = 0; while (!que.empty()) { int w = que.front(); que.pop(); inq[w] = 0; for (int i=head[w];i;i=nxt[i]) { if (dis[to[i]] > dis[w] + cost[i] && flow[i]) { dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i; if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]); } } } return dis[T] < INF; } }MCMF; class CurvyonRails { int n,m,cnt,E; char pat[L][L]; public: int getmin(vector<string> field) { init(); m = field.size(); n = field[0].size(); for (int j=0;j<m;j++) { for (int i=0;i<n;i++) { pat[i+1][j+1] = field[j][i]; } } for (int j=1;j<=m;j++) { for (int i=1;i<=n;i++) { if (pat[i][j] == 'w') continue; else { if (++cnt, i + j & 1) { Add_Edge(id(i,j,0), T, 1); Add_Edge(id(i,j,1), T, 1); } else { Add_Edge(S, id(i,j,0), 1); Add_Edge(S, id(i,j,1), 1); for (int k=1,x,y;k<=4;k++) { x = i + dx[k]; y = j + dy[k]; if (1 <= x && x <= n && 1 <= y && y <= m) { if (x == i) Add_Edge(id(i,j,1), id(x,y,1), 1); if (y == j) Add_Edge(id(i,j,0), id(x,y,0), 1); } } } if (pat[i][j] == '.') { Add_Edge(id(i,j,0), id(i,j,1), 1); Add_Edge(id(i,j,1), id(i,j,0), 1); } if (pat[i][j] == 'C') { Add_Edge(id(i,j,0), id(i,j,1), 1, 1); Add_Edge(id(i,j,1), id(i,j,0), 1, 1); } } } } pair<int,int> vout = MCMF.MaxFlow(); if (vout.second < cnt) return -1; else return vout.first; } private: inline int id(int x, int y, int t) { return ((y-1)*n + (x-1)) * 2 + 1 + t; } inline void init() { E = 1; S = cnt = 0; T = N - 1; memset(head,0,sizeof(head)); } inline void Add_Edge(int u, int v, int f, int c = 0) { to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c; } };
What’s up it’s me, I am also visiting this site daily, this website is in fact fastidious and the users are in fact sharing nice thoughts.
Marvelous, what a webpage it is! This webpage presents useful information to us, keep it up.
Hi there, after reading this remarkable article
i am too delighted to share my experience here with mates.
I have read so many content regarding the blogger lovers
however this post is really a pleasant article, keep it up.
Thanks designed for sharing such a nice opinion, post is fastidious,
thats why i have read it completely
Oh my goodness! Incredible article dude! Thank you so much, However I am having
difficulties with your RSS. I don’t know the reason why I can’t subscribe to it.
Is there anybody having identical RSS issues?
Anyone that knows the answer will you kindly respond? Thanks!!
I am regular reader, how are you everybody? This piece of writing posted at this website
is truly nice.
Hi my friend! I wish to say that this article is amazing,
nice written and include almost all important infos. I would like to see more posts like this .
Ahaa, its good discussion on the topic of this article here at this web site, I have read all that, so now me also
commenting here.
I all the time used to read post in news papers but now as I am a user
of net so from now I am using net for articles,
thanks to web.
Hmm it seems like your website ate my first comment (it was extremely long) so I guess I’ll just sum it up
what I wrote and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog blogger but I’m still new to the whole thing.
Do you have any suggestions for first-time blog writers?
I’d genuinely appreciate it.
Way cool! Some extremely valid points! I appreciate you writing this write-up plus the
rest of the site is extremely good.
Wow, this piece of writing is nice, my younger
sister is analyzing these kinds of things, thus I am going to let know her.
I am really enjoying the theme/design of your blog.
Do you ever run into any browser compatibility problems?
A few of my blog visitors have complained about my site not operating correctly in Explorer but looks great in Firefox.
Do you have any ideas to help fix this problem?
Good blog post. I definitely appreciate this website.
Continue the good work!
Hello there! This post could not be written much better!
Looking through this post reminds me of my previous roommate!
He always kept talking about this. I most certainly
will forward this information to him. Pretty sure he’ll have a good read.
Thanks for sharing!
It’s going to be end of mine day, however before end I am reading this wonderful post to
improve my experience.
It’s in reality a great and useful piece of information. I am glad that
you just shared this helpful information with us. Please keep us up to date like this.
Thanks for sharing.
If some one wishes to be updated with newest technologies afterward he must
be pay a quick visit this website and be up to date every day.
Its such as you read my thoughts! You appear to understand
so much approximately this, such as you wrote the ebook in it or something.
I feel that you could do with some p.c. to power the message house a little bit, but other than that, that
is fantastic blog. A fantastic read. I will definitely be back.
Appreciate this post. Will try it out.
Very nice post. I definitely love this website.
Keep it up!
Hello! Someone in my Facebook group shared this site with us so I came to give it a
look. I’m definitely enjoying the information. I’m book-marking and
will be tweeting this to my followers! Excellent blog and amazing style
and design.
Thanks for your personal marvelous posting! I certainly enjoyed reading it, you could be a great author.I
will make certain to bookmark your blog and definitely will come back very soon. I want
to encourage you to definitely continue your great work, have a
nice weekend!
I think everything composed was very logical. But, what about
this? suppose you wrote a catchier title?
I am not suggesting your content isn’t good, but suppose you added something that makes people desire more?
I mean 【TopCoder SRM570】Curvy on Rails – Qizy's
Database is kinda boring. You should look at Yahoo’s home page and watch how they create
article titles to get people interested. You might add a related
video or a related pic or two to grab readers excited about what you’ve
got to say. In my opinion, it might make your website
a little livelier. natalielise pof
This is my first time pay a quick visit at here and i am genuinely pleassant to read everthing at
alone place.
It’s actually very complicated in this full of
activity life to listen news on TV, so I only use world
wide web for that reason, and obtain the newest information.
Awesome post.
If you are going for finest contents like me, just pay a quick visit this web site every day for the reason that it
presents quality contents, thanks plenty of fish natalielise
I seriously love your blog.. Pleasant colors & theme.
Did you create this site yourself? Please reply back as I’m trying to create my very own website and would love to learn where you got
this from or exactly what the theme is named. Appreciate it!
Magnificent goods from you, man. I’ve understand your stuff previous to and
you’re just too great. I really like what you’ve acquired here, really like what you are stating and
the way in which you say it. You make it entertaining
and you still care for to keep it sensible. I can not wait to read far more from you.
This is really a great site.
Heya! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing several weeks of hard work due to no
back up. Do you have any methods to stop hackers?
Way cool! Some very valid points! I appreciate you writing this
post and the rest of the website is extremely good.
Great blog you have here but I was wondering if you knew of any user discussion forums that
cover the same topics talked about in this article?
I’d really like to be a part of group where I can get advice from other experienced individuals that share
the same interest. If you have any suggestions, please let me know.
Thanks! plenty of fish natalielise
Magnificent website. Lots of useful info here. I am sending it to a few friends ans additionally sharing in delicious.
And obviously, thank you for your effort! natalielise pof
I do not even know how I ended up here, but I thought this post was
great. I don’t know who you are but definitely you are going
to a famous blogger if you are not already 😉 Cheers!
I love what you guys are up too. This kind of clever work and coverage!
Keep up the good works guys I’ve included you guys to my blogroll.
First of all I would like to say excellent blog!
I had a quick question which I’d like to ask if you don’t mind.
I was interested to know how you center yourself and clear your
thoughts before writing. I’ve had a difficult time clearing
my thoughts in getting my thoughts out there.
I do take pleasure in writing however it just seems like the first 10 to 15 minutes are generally wasted just trying to figure out how to begin. Any ideas or
tips? Appreciate it!
If you wish for to get a great deal from this paragraph then you have to apply these techniques to your won blog.
Heya i’m for the first time here. I came across this board and
I find It really useful & it helped me out much. I hope to give something back and help others
like you helped me.
Greetings! Quick question that’s completely off topic. Do you know how to make your site mobile friendly?
My site looks weird when viewing from my apple iphone.
I’m trying to find a template or plugin that might be able to correct this problem.
If you have any recommendations, please share.
With thanks!
What’s up, this weekend is good for me, because this moment i am reading this wonderful informative paragraph here at my home.
This blog was… how do I say it? Relevant!! Finally I’ve found something which helped
me. Appreciate it!
Nice blog! Is your theme custom made or did you download it from
somewhere? A theme like yours with a few simple tweeks would really make my blog
stand out. Please let me know where you got your theme. Bless you
Thanks , I have just been looking for info approximately this subject for a long time and yours is the greatest I
have came upon so far. But, what concerning the bottom line?
Are you sure in regards to the source?
I was suggested this web site by my cousin. I’m not sure whether this post
is written by him as nobody else know such detailed about my difficulty.
You’re incredible! Thanks!
Appreciate the recommendation. Will try it out.
I’m curious to find out what blog system you are working with?
I’m having some minor security problems with my latest site and I would like to find something more safeguarded.
Do you have any suggestions?
Can you tell us more about this? I’d want to find out
some additional information.
Thanks designed for sharing such a pleasant thinking, post is good, thats why
i have read it fully
I know this web site gives quality dependent content and other
data, is there any other web site which gives these kinds of
data in quality?
Hey! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to get
my blog to rank for some targeted keywords but I’m not seeing very good results.
If you know of any please share. Thank you!
Hi there, just wanted to say, I enjoyed this post.
It was inspiring. Keep on posting!
Hello There. I found your blog using msn. This is a really well written article.
I will make sure to bookmark it and come back to read more of your useful information. Thanks for the post.
I’ll definitely comeback.
Hey this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding expertise so I wanted to get
advice from someone with experience. Any help would be enormously appreciated!
Wow, fantastic weblog format! How long have you ever
been blogging for? you made blogging glance easy. The total
look of your web site is wonderful, let alone the content!
Hi, I do think your web site may be having web browser compatibility problems.
When I take a look at your site in Safari, it looks fine however,
if opening in Internet Explorer, it has some overlapping
issues. I merely wanted to provide you with a quick heads up!
Besides that, great blog!
Hey exceptional website! Does running a blog like
this take a massive amount work? I’ve absolutely no expertise in programming however I
had been hoping to start my own blog soon. Anyways, if you have any suggestions or tips for new blog
owners please share. I know this is off subject nevertheless I
simply had to ask. Many thanks!
Amazing! Its genuinely remarkable post, I have got much clear idea about from this post.
You actually make it seem so easy with your presentation but I find this matter to
be actually something that I think I would never understand.
It seems too complex and extremely broad for me. I’m looking forward for your next post, I will try to get the hang of it!
Have you ever considered about adding a little bit more than just your articles?
I mean, what you say is important and everything. But think about if you added some great pictures or video clips to give
your posts more, “pop”! Your content is excellent but with pics and clips, this site could certainly be
one of the very best in its field. Excellent blog!
Hi, i feel that i saw you visited my web site so i got here to
go back the want?.I am trying to to find issues to enhance
my web site!I suppose its adequate to use a few of your
concepts!!
This is a topic that is close to my heart… Best wishes!
Where are your contact details though?
Pretty! This has been an incredibly wonderful post.
Many thanks for supplying these details.
Wonderful beat ! I would like to apprentice while you
amend your website, how can i subscribe for a blog website?
The account aided me a acceptable deal. I had
been a little bit acquainted of this your broadcast offered bright clear concept
Undeniably believe that which you stated.
Your favorite reason appeared to be on the web the simplest thing
to be aware of. I say to you, I certainly get irked while people think about worries that they plainly don’t know about.
You managed to hit the nail upon the top and defined out the whole thing without having side effect ,
people could take a signal. Will probably be back to get more.
Thanks
I pay a visit day-to-day a few web pages and websites to read content, however this webpage gives quality based writing.
Hello there, just became alert to your blog through Google, and found that it’s truly informative.
I’m going to watch out for brussels. I’ll be grateful
if you continue this in future. Numerous people will be benefited from your writing.
Cheers!
Hi there all, here every person is sharing these kinds of know-how, thus it’s good to read this blog,
and I used to go to see this webpage everyday.
Hello there, just became alert to your blog through Google,
and found that it’s really informative. I am gonna watch out for brussels.
I’ll be grateful if you continue this in future.
Lots of people will be benefited from your writing.
Cheers!
I am regular reader, how are you everybody? This paragraph posted at
this web page is really nice.
I think this is one of the most significant info for me. And i am glad reading your article.
But want to remark on some general things, The site style is great,
the articles is really excellent : D. Good job, cheers
That is very attention-grabbing, You are an overly
skilled blogger. I’ve joined your rss feed and stay up for looking for more of your great post.
Also, I’ve shared your website in my social networks
Hi to all, how is everything, I think every one is getting more from this web page,
and your views are pleasant designed for new users.
For hottest information you have to go to see the web and on the web I found this site
as a most excellent site for newest updates.
Hello every one, here every one is sharing such know-how,
therefore it’s nice to read this web site, and I used to pay
a quick visit this webpage everyday.
I have been browsing on-line greater than 3 hours these
days, yet I never discovered any fascinating article
like yours. It is lovely value sufficient for me. In my opinion, if all website owners and
bloggers made excellent content material as you did,
the internet shall be a lot more useful than ever before.
This post is really a fastidious one it helps new
web users, who are wishing for blogging.
I’m not certain where you are getting your information, however great
topic. I must spend some time studying more
or figuring out more. Thanks for magnificent information I was
in search of this information for my mission.
Wow that was unusual. I just wrote an extremely long comment
but after I clicked submit my comment didn’t appear.
Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say wonderful blog!
I really like reading a post that will make men and women think.
Also, thanks for allowing for me to comment!
I go to see everyday a few sites and information sites
to read posts, however this weblog offers quality based posts.
Great information. Lucky me I recently found your website by
chance (stumbleupon). I have book marked it for later!
I all the time emailed this webpage post page to all my associates, since
if like to read it then my contacts will too.
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! However, how could we communicate?
Its like you read my mind! You appear to know a lot about this, like you wrote the book
in it or something. I think that you can do with some pics to drive the message home a
little bit, but instead of that, this is fantastic blog.
A great read. I’ll definitely be back.
Hi, i believe that i noticed you visited my site
so i came to return the prefer?.I’m trying to to find issues to enhance my web site!I
assume its good enough to use some of your concepts!!
I loved as much as you will receive carried out right here.
The sketch is attractive, your authored material stylish.
nonetheless, you command get bought an nervousness over
that you wish be delivering the following. unwell unquestionably come more formerly again as exactly the same
nearly a lot often inside case you shield this hike.
Hey There. I discovered your weblog the use of msn.
That is a very smartly written article. I will be sure to bookmark it and return to read extra of
your helpful info. Thank you for the post. I will certainly return.
If some one wishes expert view concerning blogging
afterward i propose him/her to go to see this website,
Keep up the nice work.
I’d like to find out more? I’d like to find out
some additional information.
A person necessarily assist to make seriously posts I’d state.
This is the very first time I frequented your website page
and so far? I surprised with the analysis you made to make
this actual submit amazing. Magnificent process!
I am not sure where you are getting your info, but great topic. I needs to spend some time learning much more or understanding more. Thanks for excellent information I was looking for this info for my mission.
I know this website presents quality dependent content and additional data, is there any other site which
provides these kinds of data in quality?
My partner and I stumbled over here different page and thought I might as well check things
out. I like what I see so now i am following you. Look forward to
looking at your web page again.
Great web site you’ve got here.. It’s hard to find quality
writing like yours nowadays. I seriously appreciate people like you!
Take care!!
This is a topic that is near to my heart… Best wishes!
Exactly where are your contact details though?
When some one searches for his vital thing, therefore he/she wishes to be available that in detail, so that
thing is maintained over here.
It’s an remarkable article designed for all the web viewers; they
will get advantage from it I am sure.
We are a group of volunteers and opening a new scheme in our community.
Your website offered us with valuable info to work on. You’ve done a
formidable job and our entire community will be
thankful to you.
What’s up to every one, since I am actually keen of reading this weblog’s post to be
updated regularly. It consists of nice material.
But wanna comment on few general things, The website
style and design is perfect, the subject material is really good :D.
I am continually searching online for articles that
can benefit me. Thanks!
Hello, after reading this awesome paragraph i am too delighted to share my knowledge here with
colleagues.
Thanks for sharing your thoughts about test.
Regards
Hello.This post was extremely fascinating, particularly because I was looking for thoughts on this matter last Friday.
You’ve made some decent points there. I looked on the internet for additional information about the
issue and found most people will go along with your views on this website.
Howdy! I just want to give you a big thumbs up for your
excellent info you have got here on this post.
I will be coming back to your blog for more soon.
I really love your site.. Pleasant colors & theme. Did you build this site yourself?
Please reply back as I’m attempting to create my very own site and would love to find out where you got
this from or exactly what the theme is named.
Kudos!
Hey there! I just want to give you a big thumbs up for the
great info you have got here on this post.
I am coming back to your site for more soon.
This blog was… how do I say it? Relevant!! Finally I have found something
that helped me. Cheers!
We are a group of volunteers and opening a brand new scheme in our community.
Your site provided us with helpful info to work on. You’ve done
an impressive process and our entire community shall be grateful to you.
Hello, its fastidious post regarding media print, we all be aware of media is a wonderful source of facts.
Superb, what a website it is! This website provides valuable
facts to us, keep it up.
I’ve read several good stuff here. Definitely price bookmarking for revisiting.
I surprise how so much effort you put to create such a magnificent
informative website.
It’s going to be end of mine day, but before ending
I am reading this impressive piece of writing to increase my knowledge.
Heya i’m for the primary time here. I came across this board and I find It
really useful & it helped me out much. I hope to
provide one thing again and aid others such as you aided me.
This paragraph will assist the internet people for building
up new blog or even a blog from start to end.
I visited several web pages however the audio feature for audio songs present at this site is actually fabulous.
Hello it’s me, I am also visiting this site daily, this web site is in fact nice and the visitors
are really sharing pleasant thoughts.
It is perfect time to make some plans for the longer term and it is time to be happy.
I have read this submit and if I may just I wish to recommend you few interesting issues or tips.
Perhaps you can write next articles referring to this article.
I desire to read more issues about it!
This is the right site for anyone who wishes to understand this topic.
You know a whole lot its almost hard to argue with you (not that I
personally will need to…HaHa). You certainly put
a fresh spin on a topic that’s been written about for many years.
Great stuff, just excellent!
Actually when someone doesn’t know then its up
to other visitors that they will assist, so here it takes place.
Im obliged for the article post. Fantastic.
Very good article. I’m experiencing many of these issues as
well..
Hi Dear, are you actually visiting this website daily, if so
after that you will without doubt get nice knowledge.
I am extremely impressed with your writing skills as well as with the layout
on your blog. Is this a paid theme or did you customize it
yourself? Either way keep up the nice quality writing,
it is rare to see a nice blog like this one nowadays.
Nice post. I was checking constantly this blog and I am impressed!
Extremely useful information specifically the final section 🙂 I take care
of such info a lot. I used to be looking for this particular information for a long time.
Thanks and good luck.
Great post. I was checking constantly this blog and I’m impressed!
Extremely useful information specifically the last part :
) I care for such information much. I was seeking this particular
information for a very long time. Thank you and best of luck.