【TopCoder SRM558】Surrounding Game

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/01/SurroundingGame.html
中文题面:http://www.cnblogs.com/enigma-aw/p/6236241.html
神犇题解:http://vfleaking.blog.163.com/blog/static/17480763420129289015251/

解题报告

看到这种收益相关的题目,肯定想到最小割
并且对于这题来讲,不难想到下面这种构图方式:

$ j$ 是点 $ i$ 拆出来的点, $ a$ 、 $ b$ 、 $ c$ 、 $ d$ 是与i点相邻的点拆出来的点

但这样构图,节点的意义不具备普遍性,即对于考虑的关系不同,相同节点的意义不同

比如对于点j,现在的图中不能存在 $ j \to T$ 这条边,但在考虑其他点的时候,该边不可被忽略

因为是网格图,所以考虑能否使用二分图染色解决这个问题
考虑将黑点连到 $ S$, 白点连到 $ T$
并规定,黑点被割到 $ S$ 集表示选,白点被割到 $ S$ 集表示不选(割到 $ T$ 集的意义以此递推)

于是提到的第一种建图方式就可以得到下面这种建图方式:

然后我们惊奇地发现,该种建图方式满足原题的一切要求!

不要问我是怎么推出来的
我也普吉岛…

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000;
const int M = 100000;
const int INF = 1e9;

int S,T,head[N],nxt[M],to[M],flow[M];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1,0};

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,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 (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

class SurroundingGame {
	int n,m,E,vout; 
    public:
    	int maxScore(vector<string> cost, vector<string> benefit) {
    	    init();
			m = cost.size();
    	    n = cost[0].size();
    	    for (int j=0;j<m;j++) {
				for (int i=0;i<n;i++) {
					vout += Val(benefit[j][i]);
				}
			}
    	    for (int j=1;j<=m;j++) {
				for (int i=1;i<=n;i++) {
					if (i + j & 1) {
						Add_Edge(S, id(i,j,1), Val(cost[j-1][i-1]));
						Add_Edge(id(i,j,1), id(i,j,2), Val(benefit[j-1][i-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) {
								Add_Edge(id(i,j,1), id(x,y,2));
								Add_Edge(id(i,j,2), id(x,y,1));
							}  
						}
					} else {
						Add_Edge(id(i,j,1), T, Val(cost[j-1][i-1]));
						Add_Edge(id(i,j,2), id(i,j,1), Val(benefit[j-1][i-1]));
					}	
				}
			}
			return vout - Dinic.MaxFlow();
   		}
   	private:
   		inline void init() {
			E = 1; S = vout = 0; T = N - 1;
			memset(head,0,sizeof(head));   
		}
		inline void Add_Edge(int u, int v, int f = INF) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
			to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
		} 
		inline int id(int x, int y, int t) {
			return ((y-1) * n + (x-1)) * 2 + t;
		}
		inline int Val(char c) {
			if ('A' <= c && c <= 'Z') return c - 29;
			if ('a' <= c && c <= 'z') return c - 87;
			if ('0' <= c && c <= '9') return c - 48;
		}
};

85 thoughts to “【TopCoder SRM558】Surrounding Game”

  1. Hi there, I found your site by the use of Google while searching for a comparable subject, your website got here up, it seems to be good.
    I have bookmarked it in my google bookmarks.
    Hi there, simply turned into alert to your weblog via Google, and found that it is truly informative.
    I am gonna watch out for brussels. I’ll appreciate if you happen to continue this
    in future. A lot of people shall be benefited from your writing.
    Cheers!

  2. Thanks , I’ve recently been searching for information about this subject
    for a while and yours is the greatest I have found out till now.
    But, what about the conclusion? Are you sure about the source?

  3. Greate article. Keep posting such kind of info on your page.

    Im really impressed by your site.
    Hey there, You have done a great job. I will certainly digg it and individually recommend to my friends.
    I’m confident they will be benefited from this web site.

  4. Hey there! This is my first visit to your blog! We
    are a collection of volunteers and starting a new initiative in a
    community in the same niche. Your blog provided us valuable information to work on. You have done a extraordinary job!

  5. Excellent weblog here! Additionally your web site quite a bit up very fast!

    What host are you using? Can I am getting your affiliate hyperlink for your host?
    I want my site loaded up as fast as yours lol

  6. Heya! I realize this is kind of off-topic however I had to ask.
    Does building a well-established blog such as yours require a lot of work?

    I am brand new to blogging but I do write in my journal every
    day. I’d like to start a blog so I will be able to share my personal experience and feelings online.
    Please let me know if you have any recommendations or tips for brand new aspiring blog owners.
    Thankyou!

  7. I’m not sure why but this website is loading extremely slow for
    me. Is anyone else having this issue or is it a problem on my end?
    I’ll check back later on and see if the problem
    still exists.

  8. Greetings from Idaho! I’m bored at work so I decided to browse your
    site on my iphone during lunch break. I love the information you present here and can’t wait to take a look when I get home.

    I’m surprised at how quick your blog loaded on my cell phone ..
    I’m not even using WIFI, just 3G .. Anyhow, good blog!

  9. I think this is among the most significant information for me.
    And i’m glad reading your article. But should remark on some general things, The site style is
    great, the articles is really great : D. Good job, cheers

  10. After looking over a handful of the articles on your site, I honestly appreciate
    your technique of writing a blog. I book-marked it to my bookmark site list and will be checking back soon. Take a look
    at my web site as well and let me know your opinion.

  11. If some one desires expert view concerning blogging afterward
    i advise him/her to pay a visit this website, Keep up the nice work.

  12. Write more, thats all I have to say. Literally, it seems as though you relied on the video to
    make your point. You obviously know what youre talking
    about, why waste your intelligence on just posting videos to your weblog when you
    could be giving us something informative to read?

  13. Hey! Someone in my Myspace group shared this website with us so I came to check it out.
    I’m definitely loving the information. I’m
    book-marking and will be tweeting this to my
    followers! Superb blog and amazing style and design.

  14. I am curious to find out what blog platform you happen to be working with?
    I’m having some minor security problems with my latest website
    and I would like to find something more secure. Do you have any suggestions?

  15. Hi there! I could have sworn I’ve been to this website before but
    after reading through some of the post I realized it’s new to
    me. Anyhow, I’m definitely delighted I found it and
    I’ll be bookmarking and checking back frequently!

  16. Hiya! Quick question that’s entirely off topic. Do you know
    how to make your site mobile friendly? My web site looks weird
    when browsing from my iphone 4. I’m trying to find a template or
    plugin that might be able to correct this problem. If you have any recommendations, please share.
    Thanks!

  17. Heya i’m for the first time here. I found this board and I in finding It truly useful & it helped me out much.
    I’m hoping to offer one thing again and help others such as you
    aided me.

  18. Simply desire to say your article is as amazing. The clearness
    in your post is just nice and i could assume you
    are an expert on this subject. Well with your permission let me to grab your
    feed to keep up to date with forthcoming post. Thanks a million and please
    carry on the rewarding work.

  19. Greetings from Ohio! I’m bored at work so I decided to
    browse your site on my iphone during lunch break. I enjoy the knowledge you present here and can’t wait to
    take a look when I get home. I’m surprised at how fast your blog loaded on my cell
    phone .. I’m not even using WIFI, just 3G .. Anyhow, awesome blog!

  20. Hello there, just became alert to your blog through Google, and found that it’s
    truly informative. I am gonna watch out for brussels.
    I’ll be grateful if you continue this in future.
    Numerous people will be benefited from your writing.
    Cheers!

  21. Hey There. I found your blog using msn. This is a very well written article.
    I’ll be sure to bookmark it and return to read more of your useful info.
    Thanks for the post. I will definitely comeback.

  22. Hello just wanted to give you a quick heads up and let you know a few of the images aren’t loading properly.
    I’m not sure why but I think its a linking issue. I’ve tried it in two different web
    browsers and both show the same results.

  23. What’s Happening i’m new to this, I stumbled upon this I have found It absolutely
    useful and it has aided me out loads. I am hoping
    to contribute & aid other users like its helped me.
    Good job.

  24. This is the perfect blog for anybody who wishes to understand this topic.
    You know a whole lot its almost tough to argue with you (not that I really
    would want to…HaHa). You certainly put a brand new spin on a subject that’s been written about for a long time.

    Great stuff, just wonderful!

  25. Good day! I know this is kinda off topic but I was wondering which blog platform are you
    using for this website? I’m getting sick and tired of
    Wordpress because I’ve had issues with hackers and I’m looking at options
    for another platform. I would be fantastic if you could point me in the direction of a good platform.

  26. Nice blog here! Also your site loads up very fast!
    What host are you using? Can I get your affiliate link to your
    host? I wish my site loaded up as quickly as yours lol

  27. Your style is really unique compared to other people I’ve read stuff from.

    Many thanks for posting when you have the opportunity, Guess I’ll just book
    mark this page.

  28. Hello there! This article couldn’t be written any better!
    Going through this post reminds me of my previous roommate!
    He always kept preaching about this. I am going to send this
    information to him. Fairly certain he’ll have a
    good read. Many thanks for sharing!

  29. hey there and thank you in your info – I have definitely picked up anything new from proper here. I did then again experience a few technical issues using this web site, as I experienced to reload the web site lots of times prior to I may get it to load correctly. I were puzzling over in case your web hosting is OK? Now not that I’m complaining, however slow loading instances occasions will very frequently affect your placement in google and could harm your quality ranking if ads and ***********|advertising|advertising|advertising and *********** with Adwords. Anyway I’m adding this RSS to my email and could glance out for a lot more of your respective exciting content. Make sure you update this again very soon..

  30. Today, I went to the beach front with my children. I found a
    sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed
    the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is totally off topic but I
    had to tell someone!

  31. Howdy! Someone in my Facebook group shared this
    site with us so I came to look it over. I’m definitely enjoying the information. I’m
    book-marking and will be tweeting this to my followers! Terrific blog and wonderful design and style.

  32. Hey there! I know this is somewhat off-topic however I had to ask.
    Does managing a well-established blog like yours take a
    massive amount work? I am brand new to running a blog but I
    do write in my diary everyday. I’d like to start
    a blog so I can share my personal experience and feelings online.
    Please let me know if you have any ideas or tips for new aspiring blog owners.
    Thankyou!

  33. My family members always say that I am killing my time here at net, however I know
    I am getting familiarity every day by reading
    such fastidious posts.

  34. That is really interesting, You are an excessively skilled blogger.
    I’ve joined your rss feed and look forward to in the hunt
    for more of your great post. Also, I’ve shared your web site
    in my social networks

  35. I’m not that much of a online reader to be honest but your sites really nice,
    keep it up! I’ll go ahead and bookmark your site to come back later on. All the best

  36. I’m not sure exactly why but this site is loading very slow
    for me. Is anyone else having this problem or is it a problem
    on my end? I’ll check back later and see if the problem still exists.

  37. It is perfect time to make a few plans for
    the long run and it’s time to be happy. I have learn this
    post and if I could I desire to suggest you few attention-grabbing things or suggestions.
    Maybe you could write subsequent articles regarding this article.
    I wish to read even more things about it!

  38. Hi! I know this is somewhat off topic but I was wondering which blog platform
    are you using for this website? I’m getting fed up of WordPress because I’ve had issues with hackers and I’m looking at
    options for another platform. I would be great if you could point me in the direction of
    a good platform.

  39. Thank you for another great article. The place else may anyone get that kind of info in such a perfect method
    of writing? I’ve a presentation subsequent week, and I’m at the look for such info.

  40. It’s a pity you don’t have a donate button! I’d definitely donate
    to this outstanding blog! I guess for now i’ll settle for
    book-marking and adding your RSS feed to my Google account.
    I look forward to fresh updates and will share this site with my Facebook group.
    Talk soon!

  41. Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your blog? My blog is in the exact same area of interest as yours and my visitors would really benefit from a lot of the information you present here. Please let me know if this ok with you. Many thanks!

Leave a Reply

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