【BZOJ 3171】[Tjoi2013] 循环格

Qizy 图论, 网络流, 解题报告, 费用流

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3171

按照入度出度拆点，然后就是萌萌哒费用流啦！

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

const int N = 15*15*2+9;
const int M = N*10; 
const int INF = 100000000;

int head[N],nxt[M],to[M],cost[M],flow[M],n,m,dis[N],FLOW[N];
int ord[20],dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1},S,T,inq[N],sur[N];
char pat[20]; queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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 ty) {
	static int SUM = n*m;
	if (!x) x = n; else if (x == n+1) x = 1;
	if (!y) y = m; else if (y == m+1) y = 1;
	return x+(y-1)*n+ty*SUM;
}

inline void Add_Edge(int u, int v, int f, int c) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline int SPFA() {
    memset(dis,127,sizeof(dis));
    memset(FLOW,0,sizeof(FLOW));
    que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
      
    while (!que.empty()) {
        int w = que.front(); que.pop(); inq[w] = 0;
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
            dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
            FLOW[to[i]] = min(FLOW[w], flow[i]);
            if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
        }
    } return FLOW[T];
}
  
inline int MCMF() {
    int ret = 0;
    for (int w=T,f;f=SPFA();w=T) 
        for (int t=sur[w];w!=S;t=sur[w]) 
            flow[t] -= f, flow[t^1] += f,
            ret += cost[t]*f, w = to[t^1];
    return ret;
}

int main(){
	m = read(); n = read(); S = 0; T = N-1;
	for (int j=1;j<=m;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) 
			if (pat[i] == 'R') ord[i] = 1; else if (pat[i] == 'D') ord[i] = 2;
			else if (pat[i] == 'L') ord[i] = 3; else ord[i] = 4;
		for (int i=1;i<=n;i++) {
			Add_Edge(S,id(i,j,0),1,0); Add_Edge(id(i,j,1),T,1,0);
			Add_Edge(id(i,j,0),id(i+dx[ord[i]],j+dy[ord[i]],1),1,0);
			for (int k=1;k<=4;k++) if (k != ord[i]) Add_Edge(id(i,j,0),id(i+dx[k],j+dy[k],1),1,1);
		}
	} printf("%d\n",MCMF());
	return 0;
}

333 thoughts to “【BZOJ 3171】[Tjoi2013] 循环格”

  1. I don’t even understand how I ended up here, however
    I assumed this publish used to be great. I don’t know who you might be but definitely you are going
    to a well-known blogger for those who are not already. Cheers!

    Reply

  2. Pretty section of content. I just stumbled upon your website and in accession capital to assert that I
    get in fact enjoyed account your blog posts. Any way I’ll be subscribing to your augment and
    even I achievement you access consistently rapidly.

    Reply

  3. Having read this I believed it was really informative.
    I appreciate you finding the time and effort to put this short article together.
    I once again find myself personally spending way too
    much time both reading and commenting. But so what, it was still
    worth it!

    Reply

  8. You’re so cool! I don’t think I have read a single thing like this before.
    So wonderful to find somebody with unique thoughts on this
    subject matter. Really.. thank you for starting this up.
    This website is one thing that is required on the internet, someone with
    a little originality!

    Reply

  9. Does your site have a contact page? I’m having problems locating it but, I’d like to shoot you an e-mail.
    I’ve got some creative ideas for your blog you might
    be interested in hearing. Either way, great site and I look forward to seeing it grow over time.

    Reply

  11. I have been exploring for a little bit for any high-quality articles or weblog posts on this sort
    of area . Exploring in Yahoo I finally stumbled upon this site.
    Studying this info So i’m happy to express that
    I’ve an incredibly good uncanny feeling I discovered just what I needed.
    I so much definitely will make sure to do not omit this site and provides
    it a look on a constant basis.

    Reply

  14. Hi there, I think your web site could be having internet browser compatibility issues.
    When I take a look at your site in Safari, it
    looks fine however, if opening in I.E., it’s got some overlapping
    issues. I merely wanted to provide you with a quick heads up!
    Other than that, great blog!

    Reply

  16. Incredible! This blog looks just like my old one! It’s on a completely different subject but it has pretty much the same layout and
    design. Excellent choice of colors! plenty of fish natalielise

    Reply

  17. you’re really a just right webmaster. The web site loading pace is amazing.

    It sort of feels that you’re doing any unique trick. In addition, The contents are masterpiece.
    you’ve performed a wonderful activity on this matter!

    Reply

  20. Hello there! This is my first comment here so I just wanted to give a quick shout out and tell
    you I genuinely enjoy reading through your blog posts.
    Can you suggest any other blogs/websites/forums that go over the same topics?

    Thank you!

    Reply

  23. You really make it seem so easy with your presentation but I find this matter to be really something that I think I would never understand.
    It seems too complicated and very broad for me.

    I am looking forward for your next post, I will try to get the hang of it!

    Reply

  29. It’s perfect time to make some plans for the future and it’s time to be happy.
    I’ve read this submit and if I may I wish to suggest
    you few interesting things or tips. Maybe you could write next articles
    referring to this article. I wish to learn even more issues about it!

    Reply

  30. Hi, I do think your website could be having browser compatibility problems.
    When I look at your blog in Safari, it looks fine however, if opening in Internet Explorer, it’s got some overlapping
    issues. I simply wanted to give you a quick heads up! Aside from that, fantastic site!

    Reply

  32. Hey just wanted to give you a brief 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 browsers and both show the
    same results.

    Reply

  33. Magnificent goods from you, man. I’ve keep in mind your stuff previous to and you are simply too magnificent.
    I really like what you have received right here, really like what you are
    stating and the way in which in which you are saying it. You are making it entertaining and you
    continue to take care of to stay it wise.

    I can not wait to read far more from you. That
    is actually a tremendous site.

    Reply

  37. You can certainly see your enthusiasm in the article
    you write. The sector hopes for even more passionate writers
    such as you who aren’t afraid to say how they believe.
    All the time follow your heart.

    Reply

  38. This is really interesting, You are a very skilled blogger.
    I’ve joined your rss feed and look forward to seeking more of your great post.
    Also, I’ve shared your site in my social networks!

    Reply

  41. Attractive part of content. I simply stumbled upon your blog and in accession capital to say that I acquire in fact loved account your weblog posts.
    Anyway I’ll be subscribing for your feeds or even I achievement
    you get right of entry to consistently rapidly.

    Reply

  42. Wonderful goods from you, man. I have understand your
    stuff previous to and you’re just extremely excellent. I really like what
    you have acquired here, really like what you’re stating
    and the way in which you say it. You make it entertaining and
    you still take care of to keep it wise. I cant wait to read far more from you.
    This is actually a tremendous web site.

    Reply

  43. I blog quite often and I truly thank you for your information. The article has truly
    peaked my interest. I am going to book mark your
    site and keep checking for new details about once a week.
    I opted in for your Feed as well.

    Reply

  46. I have been exploring for a little for any high-quality articles or blog posts in this kind of house .
    Exploring in Yahoo I finally stumbled upon this website.

    Reading this information So i am glad to exhibit that
    I’ve a very excellent uncanny feeling I came upon exactly what I needed.
    I most definitely will make sure to do not forget this website and
    give it a glance on a relentless basis.

    Reply

  50. Nice post. I was checking continuously this blog and I am impressed!
    Extremely useful info specifically the last part 🙂 I care for such information much.

    I was seeking this particular info for a very long time.
    Thank you and best of luck.

    Reply

  55. Hello there! This is kind of off topic but I need some advice from an established
    blog. Is it tough to set up your own blog? I’m not very techincal but I can figure things out pretty quick.
    I’m thinking about creating my own but I’m not sure
    where to start. Do you have any ideas or suggestions?
    With thanks

    Reply

  76. Hi! I could have sworn I’ve visited this website before but after going through
    many of the posts I realized it’s new to me. Regardless, I’m definitely happy I stumbled upon it
    and I’ll be book-marking it and checking back frequently!

    Reply

  78. Neat 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 jump out. Please let me know where you got your design. Thanks

    Reply

  94. Hello there I am so thrilled I found your blog page, I really found you by accident, while I was browsing on Yahoo for something else,
    Anyhow I am here now and would just like to say thanks for a
    fantastic post and a all round enjoyable blog (I also
    love the theme/design), I don’t have time to look over it all at the moment but I have bookmarked it and also added in your RSS feeds, so when I have time
    I will be back to read much more, Please do keep up the superb b.

    Reply

  113. Everything wrote made a lot of sense. However, what about
    this? suppose you added a little information? I
    mean, I don’t want to tell you how to run your blog, but suppose
    you added something that makes people desire more?
    I mean 【BZOJ 3171】[Tjoi2013] 循环格 – Qizy's Database
    is kinda plain. You could look at Yahoo’s front page and see how they create post headlines to grab viewers to click.
    You might add a related video or a related pic or two to grab readers interested about what
    you’ve written. In my opinion, it would bring your posts a little livelier.

    Reply

  121. hello!,I love your writing very much! percentage we be in contact more approximately your article
    on AOL? I need an expert in this space to unravel my problem.
    Maybe that is you! Taking a look forward to look you.

    Reply

  130. I’m not that much of a internet reader to be honest but your blogs really nice, keep it up!
    I’ll go ahead and bookmark your site to come back down the road.
    All the best

    Reply

  141. I have been browsing online more than 3 hours today, yet I never found any interesting article like yours.
    It’s pretty worth enough for me. In my opinion, if all site owners and bloggers made good content as you did, the net will be much more
    useful than ever before.

    Reply

  150. My programmer is trying to convince me to move to .net from
    PHP. I have always disliked the idea because of the expenses.
    But he’s tryiong none the less. I’ve been using WordPress
    on a variety of websites for about a year and am nervous about switching to another platform.
    I have heard excellent things about blogengine.net. Is there a way
    I can import all my wordpress content into it? Any kind of help would be really appreciated!

    Reply

  154. excellent publish, very informative. I’m wondering why the other specialists of this sector do not understand this. You should continue your writing. I’m confident, you have a huge readers’ base already!

    Reply

  188. I really like your blog.. very nice colors &
    theme. Did you create this website yourself or did you hire someone to do it for you?
    Plz respond as I’m looking to construct my own blog and
    would like to know where u got this from. thanks

    Reply

  212. Very nice post. I just stumbled upon your weblog and wished to say that I’ve really enjoyded surfing around your blog posts. After all I will be subscribing to your feed and I hope you write again very soon!

    Reply

  223. The world is like a hillside. As long as you are not standing at the apex, someone will always be taller than you. When you look up for a long time, you must look down at the right time. We are all ordinary people.

    Reply

  227. Hi it’s me, I am also visiting this site regularly,
    this web page is in fact fastidious and the viewers are actually sharing pleasant
    thoughts.

    Reply

  238. Hey I am so glad I found your web site, I really found you by mistake, while I was researching on Digg
    for something else, Anyhow I am here now and would just like
    to say thanks for a fantastic post and a all round interesting blog (I also love the theme/design), I
    don’t have time to read through it all at the moment but I have saved it and also added in your RSS feeds,
    so when I have time I will be back to read a lot more, Please
    do keep up the great job.

    Reply

  242. Have you ever considered writing an ebook or guest authoring
    on other websites? I have a blog based upon on the same ideas
    you discuss and would really like to have you share some stories/information. I know my viewers
    would appreciate your work. If you are even remotely interested, feel free to send me an e
    mail.

    Reply

  269. What’s Happening i’m new to this, I stumbled upon this I’ve found It absolutely helpful and it has helped me out loads. I hope to contribute & help other users like its aided me. Great job.

    Reply

  293. Can I just say what a comfort to discover somebody that actually understands what they’re discussing online. You actually realize how to bring a problem to light and make it important. More people must read this and understand this side of your story. It’s surprising you’re not more popular given that you definitely have the gift.|

    Reply

  299. I really like your blog.. very nice colors & theme. Did you design this website yourself or did you hire someone to do it for you? Plz answer back as I’m looking to design my own blog and would like to find out where u got this from. thank you|

    Reply

  307. Hey, I think your website might be having browser compatibility issues. When I look at your website in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, wonderful blog!|

    Reply

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

    Reply

  313. Wonderful post but I was wanting to know if you could write a litte more on this topic? I’d be very thankful if you could elaborate a little bit more. Many thanks!|

    Reply

  314. Hello there! I know this is kind of 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 problems with hackers and I’m looking at alternatives for another platform. I would be awesome if you could point me in the direction of a good platform.|

    Reply

  331. I’ve been browsing online more than 3 hours today, yet I never found any interesting article like yours. It is pretty worth enough for me. Personally, if all site owners and bloggers made good content as you did, the net will be a lot more useful than ever before.|

    Reply

Leave a Reply

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