【TopCoder SRM570】Curvy on Rails

相关链接

题目传送门: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/

解题报告

首先考虑一个简单的子问题:

给定你一个网格图,其中有一些点有障碍,不能经过
问:能否通过一些回路,使得每一个点恰好经过一次

考虑回路的性质:

  1. 回路中的每一个点的度一定是 $ 2$
  2. 如果每一个点的度都是 $ 2$ ,那么这一定是由一些回路构成的图

这样的话,这个 $ Subcase$ 就可以通过染色后二分图匹配来解决了

现在回到原问题,显然可行解的判断可以用上述算法来解决
现在来考虑 towns with Curvies

在上一个 $ Subcase$ 中使用的二分图匹配,实际上是对 进行匹配
现在考虑将度分类:

  1. 横向的度
  2. 纵向的度

对于 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;
		}
};

129 thoughts to “【TopCoder SRM570】Curvy on Rails”

  1. 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!!

  2. 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.

  3. 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?

  4. 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!

  5. 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.

  6. 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.

  7. 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!

  8. 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

  9. 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

  10. 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!

  11. 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.

  12. 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?

  13. 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

  14. 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!

  15. 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!

  16. 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

  17. 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?

  18. 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!

  19. 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?

  20. 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!

  21. 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.

  22. 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!

  23. 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!

  24. 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!

  25. 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!

  26. 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!

  27. 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

  28. 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

  29. 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!

  30. 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!

  31. 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

  32. 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.

  33. 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.

  34. 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.

  35. 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!!

  36. 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.

  37. 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.

  38. 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!

  39. 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.

  40. 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.

  41. 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!!

  42. 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.

  43. 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!

  44. 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.

  45. 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.

  46. 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!

  47. 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!

  48. 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.

  49. 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.

  50. 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.

Leave a Reply to http://tinyurl.com/quest-bars-cheap-85497 Cancel reply

Your email address will not be published. Required fields are marked *