【BZOJ 3144】[HNOI2013] 切糕

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3144
神犇题解:http://www.cnblogs.com/zig-zag/archive/2013/05/13/3076563.html

解题报告

这题根据阶段来建图应该是非常经典的建图方式
考虑每一个纵轴,上端连T,下端连S
这样的话,最后在S集合中的点等价于在斜面下方
而在T集合中的点等价于在斜面上方
考虑D的限制,连两条容量为INF的边就好啦!

Code

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

const int N = 70000;
const int M = N << 2;
const int INF = 1e9;

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

inline void Add_Edge(int u, int v, int f = INF) {
	static int E = 1;
	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 read() {
	char c=getchar(); int f=1,ret=0;
	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;
}

inline int id(int x, int y, int z) {
	return ((y - 1) * q + x - 1) * (r + 1) + z;
}

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;

int main() {
	p = read(); q = read();
	r = read(); d = read();
	S = 0; T = N - 1;
	for (int z=1;z<=r;z++) {
		for (int y=1;y<=p;y++) {
			for (int x=1,v;x<=q;x++) {
				Add_Edge(id(x,y,z), id(x,y,z+1), read());
				for (int k=0,X,Y;k<4;k++) {
					X = x + dx[k];
					Y = y + dy[k];
					if (1 <= X && X <= q && 1 <= Y && Y <= p) {	
						if (z > d) Add_Edge(id(x,y,z), id(X,Y,z-d));
						if (z+d+1 <= r) Add_Edge(id(X,Y,z+d+1), id(x,y,z));
					}
				}
			}
		}
	}
	for (int x=1;x<=q;x++) {
		for (int y=1;y<=p;y++) {
			Add_Edge(S, id(x,y,1));
			Add_Edge(id(x,y,r+1), T);
		}
	}
	printf("%d\n",Dinic.MaxFlow());
	return 0;
}

266 thoughts to “【BZOJ 3144】[HNOI2013] 切糕”

  1. Pretty great post. I simply stumbled upon your weblog and wished
    to mention that I’ve truly loved surfing around your blog posts.
    After all I’ll be subscribing on your rss feed and I’m hoping you
    write again very soon!

  2. Hi there! I just wanted to ask if you ever have any problems
    with hackers? My last blog (wordpress) was hacked and I ended
    up losing many months of hard work due to no backup. Do you have any methods to prevent hackers?

  3. An interesting discussion is definitely worth comment.
    I do believe that you ought to write more about this subject matter, it may
    not be a taboo subject but usually folks don’t speak about such topics.
    To the next! Cheers!!

  4. I do consider all of the concepts you’ve introduced on your post.
    They’re really convincing and can definitely work.

    Still, the posts are very short for beginners. May just you please
    extend them a little from next time? Thanks for the post.

  5. Unquestionably believe that which you stated. Your
    favorite justification seemed 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 just do
    not know about. You managed to hit the nail upon the top and also defined out the whole thing without having side effect , people can take a signal.

    Will likely be back to get more. Thanks

  6. Nice post. I was checking continuously this blog and I am impressed!
    Very helpful information specially the last part 🙂 I care for such info a lot.
    I was looking for this certain information for
    a very long time. Thank you and good luck.

  7. Hello are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and set up my own.
    Do you need any html coding expertise to make your own blog?
    Any help would be really appreciated!

  8. Excellent blog! Do you have any tips and hints for
    aspiring writers? I’m hoping to start my own site soon but
    I’m a little lost on everything. Would you advise starting
    with a free platform like WordPress or go for a paid option? There are so many options
    out there that I’m totally confused .. Any tips?
    Thanks!

  9. Admiring the hard work you put into your website and detailed information you present.
    It’s nice to come across a blog every once in a while that isn’t the same out of date rehashed material.
    Excellent read! I’ve bookmarked your site and I’m
    including your RSS feeds to my Google account.

  10. Pretty section of content. I just stumbled upon your web site
    and in accession capital to assert that I get actually enjoyed account your blog posts.
    Anyway I will be subscribing to your feeds and even I achievement you access consistently fast.

  11. We absolutely love your blog and find most of your post’s to be what precisely I’m looking for.
    Does one offer guest writers to write content for yourself?
    I wouldn’t mind composing a post or elaborating on many of the subjects
    you write concerning here. Again, awesome weblog!

  12. Hello there, I believe your website might be having internet browser compatibility issues.

    Whenever I take a look at your blog in Safari, it looks fine but when opening in IE,
    it has some overlapping issues. I simply wanted to provide you with a quick heads up!
    Besides that, fantastic blog!

  13. I’ve been surfing online more than three hours today, yet
    I never found any interesting article like
    yours. It is pretty worth enough for me. Personally, if
    all webmasters and bloggers made good content as you did, the
    net will be much more useful than ever before.

  14. What i do not realize is in fact how you’re now
    not actually much more smartly-liked than you may be now. You’re so
    intelligent. You recognize thus considerably with regards to this matter, made me in my view consider it
    from numerous various angles. Its like women and men are
    not fascinated unless it’s one thing to do with Girl gaga!
    Your individual stuffs outstanding. All the time take care of it up!

    natalielise pof

  15. Hello there, I discovered your site by way of
    Google at the same time as searching for a comparable subject, your website came up, it looks good.

    I have bookmarked it in my google bookmarks.
    Hello there, just turned into alert to your weblog
    through Google, and located that it’s really informative.
    I’m going to be careful for brussels. I will be grateful when you
    continue this in future. Many other folks shall be benefited out of your writing.
    Cheers!

  16. Greetings! This is my first comment here so I just wanted to give a
    quick shout out and say I truly enjoy reading your blog posts.
    Can you suggest any other blogs/websites/forums that deal with
    the same topics? Thanks!

  17. Hmm it looks like your blog ate my first comment (it was super
    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 writer but I’m still new to the whole thing.
    Do you have any suggestions for rookie blog writers? I’d certainly appreciate it.

    natalielise plenty of fish

  18. Hi my family member! I wish to say that this article is
    amazing, nice written and come with approximately all important infos.
    I’d like to see more posts like this .

  19. Hi there excellent blog! Does running a blog such as this take a great deal of work?
    I have very little expertise in computer programming but I had been hoping to start my own blog soon. Anyhow, should you have any suggestions
    or techniques for new blog owners please share. I understand this is off subject nevertheless I simply needed to ask.
    Thanks a lot!

  20. I think this is among the most important info for
    me. And i’m glad reading your article. But wanna remark
    on some general things, The web site style is great, the articles is really
    excellent : D. Good job, cheers

  21. It is truly a nice and helpful piece of info. I’m happy that you just shared this helpful information with us.

    Please stay us up to date like this. Thank you for sharing.

  22. Hello, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot of
    spam feedback? If so how do you stop it, any plugin or anything you can advise?

    I get so much lately it’s driving me mad so any assistance
    is very much appreciated. natalielise pof

  23. Pretty great post. I simply stumbled upon your weblog and wanted to mention that I’ve
    truly loved surfing around your weblog posts.
    In any case I’ll be subscribing to your feed and I’m hoping you write again very soon!

  24. I think that is one of the most important info for
    me. And i’m happy studying your article. But want to commentary on some general issues, The website style
    is wonderful, the articles is in reality excellent
    : D. Just right process, cheers

  25. Hello there! Would you mind if I share your
    blog with my zynga group? There’s a lot of folks that I think would really appreciate your content.
    Please let me know. Thank you

  26. Woah! I’m really digging the template/theme of this site.
    It’s simple, yet effective. A lot of times it’s
    difficult to get that “perfect balance” between usability and visual appeal.
    I must say you have done a great job with this. Additionally, the blog loads extremely quick for me on Internet explorer.
    Outstanding Blog!

  27. It’s a shame 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 new updates and will share this website with my Facebook group.
    Chat soon!

  28. Hi there I am so excited I found your site, I really
    found you by mistake, while I was researching on Askjeeve for something else, Anyways I am here
    now and would just like to say cheers for a fantastic post and
    a all round enjoyable blog (I also love the theme/design), I don’t have time to browse it all at the minute but I have saved
    it and also added your RSS feeds, so when I have time I will be
    back to read a lot more, Please do keep up the excellent jo.

  29. Hello there, I discovered your blog by the use of Google whilst searching for a comparable subject, your web site
    came up, it seems great. I’ve bookmarked it in my google bookmarks.

    Hi there, simply changed into alert to your weblog through Google, and
    located that it is truly informative. I’m gonna
    watch out for brussels. I will appreciate for those who continue
    this in future. A lot of folks shall be benefited out of your writing.
    Cheers!

  30. I do agree with all of the ideas you’ve introduced to
    your post. They are very convincing and will certainly work.
    Nonetheless, the posts are very quick for beginners.
    May you please lengthen them a bit from subsequent time?
    Thank you for the post.

  31. Hello there, I discovered your website by means of Google whilst searching for a comparable topic, your web site got here up, it seems to be
    good. I’ve bookmarked it in my google bookmarks.
    Hi there, just was alert to your blog via Google, and located that it’s truly informative.
    I am going to be careful for brussels. I will appreciate should you proceed this in future.

    Lots of other people will probably be benefited out
    of your writing. Cheers!

  32. I like the valuable info you provide in your articles.
    I’ll bookmark your weblog and check again here frequently.
    I’m quite certain I will learn lots of new stuff right
    here! Good luck for the next!

  33. I’m truly enjoying the design and layout of your site.
    It’s a very easy on the eyes which makes it much more enjoyable for me to
    come here and visit more often. Did you hire out a designer to create your
    theme? Fantastic work!

  34. Thanks for the marvelous posting! I definitely enjoyed reading it, you might be a great author.

    I will be sure to bookmark your blog and definitely will come back in the future.
    I want to encourage you to definitely continue your great job, have a nice holiday weekend!

  35. When I initially left a comment I seem to have clicked the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I receive four emails with the exact same comment.
    Is there a means you are able to remove me from that service?
    Thanks a lot!

  36. Have you ever thought about adding a little bit more than just your articles?
    I mean, what you say is valuable and everything. Nevertheless imagine if you
    added some great pictures or video clips to give your
    posts more, “pop”! Your content is excellent but with images and videos,
    this blog could definitely be one of the very best in its
    niche. Wonderful blog!

  37. Excellent beat ! I would like to apprentice even as you amend
    your web site, how can i subscribe for a blog site?
    The account helped me a acceptable deal. I have been a
    little bit acquainted of this your broadcast provided bright clear idea

  38. Heya i am for the first time here. I found this
    board and I in finding It truly helpful & it helped me out much.
    I’m hoping to present something again and help
    others like you aided me.

  39. Hi, I do believe this is an excellent website. I stumbledupon it 😉
    I’m going to return yet again since I bookmarked it.
    Money and freedom is the greatest way to change,
    may you be rich and continue to help other people.

  40. A person essentially lend a hand to make seriously articles I’d state.
    This is the very first time I frequented your website page and up to now?
    I surprised with the analysis you made to make this particular post amazing.
    Magnificent activity!

  41. I’m really enjoying the design and layout of your blog.
    It’s a very easy on the eyes which makes it much more pleasant for me to
    come here and visit more often. Did you hire out a designer to create your theme?

    Fantastic work!

  42. It’s appropriate time to make a few plans for the
    longer term and it’s time to be happy. I’ve read this put up and if I may I wish to counsel you some fascinating issues or tips.
    Maybe you can write next articles relating to this article.
    I want to read even more things about it!

  43. Hello! This is my first visit to your blog! We are a team of volunteers and starting a new project in a community in the same niche.

    Your blog provided us beneficial information to work
    on. You have done a outstanding job!

  44. Hi there it’s me, I am also visiting this website on a regular basis,
    this web page is actually good and the viewers are in fact
    sharing nice thoughts.

  45. Wow that was odd. I just wrote an really long comment but after I clicked submit my comment didn’t
    show up. Grrrr… well I’m not writing all that over again. Anyway, just wanted to
    say excellent blog!

  46. Hey There. I found your blog using msn. This is a very 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 will definitely return.

  47. Great work! This is the kind of info that are meant to be shared across the web.
    Disgrace on the seek engines for not positioning this post
    upper! Come on over and consult with my website . Thanks =)

  48. I do agree with all the ideas you have offered to
    your post. They are really convincing and can certainly work.
    Nonetheless, the posts are too short for newbies. Could you please lengthen them a bit
    from next time? Thanks for the post.

  49. Hey! I just wanted to ask if you ever have any issues with hackers? My last blog (wordpress) was hacked and I ended up losing months of hard work due to no data backup. Do you have any methods to protect against hackers?

Leave a Reply to ehlers danlos syndrome Cancel reply

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