相关链接
题目传送门: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,现在的图中不能存在 $ 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; } };
哇塞,居然是沙发?留个名
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!
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?
It’s really a great and useful piece of info. I’m
glad that you just shared this useful info with us. Please
keep us up to date like this. Thank you for sharing.
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.
Hi! I just wanted to ask if you ever have any trouble with hackers?
My last blog (wordpress) was hacked and I ended up losing many months of hard work due to no
back up. Do you have any solutions to protect against hackers?
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!
Awesome! Its really awesome post, I have got much clear idea
about from this article.
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
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!
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.
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!
I couldn’t resist commenting. Perfectly written!
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
I constantly spent my half an hour to read this website’s content all the
time along with a mug of coffee. natalielise plenty of fish
I every time spent my half an hour to read this web site’s
articles all the time along with a cup of coffee.
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.
If some one desires expert view concerning blogging afterward
i advise him/her to pay a visit this website, Keep up the nice work.
What’s up, yes this post is truly good and
I have learned lot of things from it concerning blogging.
thanks.
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?
I know this web page gives quality depending posts and additional stuff,
is there any other website which provides such information in quality?
plenty of fish natalielise
It is not my first time to pay a visit this web
site, i am browsing this web page dailly and take good information from here every day.
Heya i am for the primary time here. I came across this board and I in finding It truly helpful & it helped me out a
lot. I hope to give something back and aid others like you helped me.
I am in fact happy to glance at this webpage posts which includes lots of helpful information, thanks for providing these data.
Truly no matter if someone doesn’t know afterward its up
to other visitors that they will assist, so here it occurs.
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.
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?
What’s up, for all time i used to check weblog posts here early in the daylight, for the reason that
i like to find out more and more.
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!
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!
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.
This is a really good tip especially to those new to the blogosphere.
Brief but very precise information… Many thanks for
sharing this one. A must read post!
Hi my family member! I want to say that this post is amazing,
great written and come with approximately all important infos.
I’d like to peer more posts like this .
I always spent my half an hour to read this webpage’s content all the time along
with a cup of coffee.
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.
What’s up mates, its impressive paragraph regarding educationand completely explained, keep it
up all the time.
Hi, its fastidious paragraph concerning media print,
we all be aware of media is a wonderful source of data.
This post will help the internet visitors for setting up new weblog or even a weblog from
start to end.
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!
I love what you guys are usually up too. This kind of
clever work and exposure! Keep up the wonderful works guys
I’ve incorporated you guys to blogroll.
It’s awesome to pay a quick visit this site and reading the views of all friends concerning this post, while I am also zealous of getting knowledge.
This information is priceless. Where can I find out more?
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!
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.
Why visitors still make use of to read news papers when in this technological globe all is existing on web?
Pretty! This was an incredibly wonderful article.
Thank you for providing these details.
If some one wants to be updated with most recent technologies after that he must be go to see this web site and be
up to date all the time.
Thanks for sharing your thoughts on plenty of fish dating site.
Regards
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 are
going to a famous blogger if you are not already 😉 Cheers!
Pretty! This was an extremely wonderful post. Many thanks for providing these details.
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.
I am actually thankful to the holder of this website who
has shared this wonderful article at at this time.
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.
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!
Excellent write-up. I absolutely love this
site. Thanks!
Nice post. I learn something totally new and challenging on sites I
stumbleupon everyday. It’s always useful to read content from other writers and use something from their websites.
Now I am ready to do my breakfast, later than having my breakfast coming over again to
read other news.
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.
What’s up to every one, the contents present at this website are in fact remarkable
for people knowledge, well, keep up the nice work fellows.
Hi, this weekend is fastidious for me, for the reason that this moment i am reading this enormous educational article here at my home.
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
Wow, incredible blog layout! How long have
you been blogging for? you make blogging look easy.
The overall look of your site is fantastic, as well as the content!
Hurrah! After all I got a weblog from where I know how to genuinely obtain helpful data
concerning my study and knowledge.
all the time i used to read smaller posts that also clear their motive,
and that is also happening with this article which I am reading at this time.
I’m not sure exactly why but this blog is loading incredibly slow for me.
Is anyone else having this problem or is it a issue on my end?
I’ll check back later and see if the problem still exists.
What’s up, I desire to subscribe for this web site to take latest
updates, so where can i do it please help out.
Keep this going please, great job!
Hello to every single one, it’s in fact a pleasant for me to pay a visit this site, it includes precious Information.
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.
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!
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..
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!
bookmarked!!, I really like your site!
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.
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!
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.
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
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
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.
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!
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.
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.
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!
If some one needs expert view concerning blogging afterward i advise
him/her to pay a quick visit this weblog, Keep up the nice work.
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!