【BZOJ 2132】圈地计划

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

可以说是最经典的一种最小割建模了吧!
看一看这张图片就能知道他的重要性了:
7856454545
然而做题的时候,只能确定是染色后转二分图,并没有确定该如何建图QAQ
题解的话,让我们召唤Menci:https://oi.men.ci/bzoj-2132/

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

const int L = 100+9;
const int N = L*L+9;
const int M = N*15;
const int INF = 1000000000;

int head[N],nxt[M],to[M],flow[M],n,m,A[L][L],B[L][L],C[L][L],vout;
int S,T,dis[N],cur[N]; 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;
}

#define id(i,j) (i+((j)-1)*n)
inline void Add_Edge(int u, int v, int f) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = f;
}

inline bool BFS(){
    memset(dis,-1,sizeof(dis));
    dis[S] = 0; que.push(S);
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    } return ~dis[T];
}
 
int DFS(int w, int f) {
    if (w == T) return f;
    else { int ret = 0;
        for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
            int tmp = DFS(to[i], min(f, flow[i]));
            ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
            if (!f) break;
        } return ret;
    }
}
 
inline int Dinic(){
    int ret = 0; while (BFS()) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(S,INF);
    } return ret;
}

int main(){
	m = read(); n = read(); S = 0; T = N-1;
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (A[i][j] = read());
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (B[i][j] = read());
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) C[i][j] = read();
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		if (i+j & 1) Add_Edge(S,id(i,j),A[i][j]), Add_Edge(id(i,j),T,B[i][j]);
		else Add_Edge(S,id(i,j),B[i][j]), Add_Edge(id(i,j),T,A[i][j]);
		if (j > 1 && i+j&1) Add_Edge(id(i,j),id(i,j-1),C[i][j]+C[i][j-1]), vout += C[i][j]+C[i][j-1];
		if (i > 1 && i+j&1) Add_Edge(id(i,j),id(i-1,j),C[i][j]+C[i-1][j]), vout += C[i][j]+C[i-1][j];
		if (j < m && i+j&1) Add_Edge(id(i,j),id(i,j+1),C[i][j]+C[i][j+1]), vout += C[i][j]+C[i][j+1];
		if (i < n && i+j&1) Add_Edge(id(i,j),id(i+1,j),C[i][j]+C[i+1][j]), vout += C[i][j]+C[i+1][j];
	} printf("%d\n",vout-Dinic());
	return 0;
}

25 thoughts to “【BZOJ 2132】圈地计划”

  1. My brother recommended I might like this website. He was totally right.
    This post truly made my day. You can not imagine just how much time I had spent for this information!
    Thanks!

  2. Great post. I used to be checking constantly this blog and I’m impressed!
    Extremely useful information specifically the remaining
    part 🙂 I take care of such information a lot. I used to be seeking this certain info for a very lengthy time.
    Thank you and best of luck.

  3. Hey, I think your blog might be having browser compatibility issues.
    When I look at your blog site in Ie, 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, terrific blog!

  4. I’m not sure where you’re getting your info, but good 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.

  5. We are a group of volunteers and opening a new scheme in our community.
    Your site provided us with valuable information to work on. You have
    done a formidable job and our whole community
    will be thankful to you.

  6. Excellent goods from you, man. I’ve understand your stuff previous to and you’re just extremely excellent.
    I actually like what you’ve acquired here, really like what you’re
    saying and the way in which you say it. You make it entertaining
    and you still care for to keep it wise. I can not wait to read far more from you.
    This is really a tremendous web site.

  7. Hi! Quick question that’s totally off topic. Do you know how to make your site mobile friendly?
    My weblog looks weird when browsing from my iphone. I’m trying to find a theme or plugin that might be able to resolve this problem.

    If you have any suggestions, please share. Cheers!

  8. Wow, marvelous blog layout! How lengthy have you been running a blog for?
    you make running a blog look easy. The whole glance of
    your website is magnificent, as well as the content material!

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

  10. Those are yours alright! . We at least need to get these people stealing images to start blogging! They probably just did a image search and grabbed them. They look good though!

  11. Hello! 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 begin. Do you have any
    tips or suggestions? Thank you

  12. You could certainly see your enthusiasm in the work you write.

    The arena hopes for even more passionate writers such as you who aren’t afraid to say how they believe.
    At all times follow your heart.

  13. I must thank you for the efforts you have put in writing this site.
    I’m hoping to view the same high-grade content from you later on as well.
    In fact, your creative writing abilities has inspired me to get my own, personal blog now 😉

  14. My partner and I stumbled over here coming from a different page and thought
    I should check things out. I like what I see so i am just following you.
    Look forward to looking at your web page for a
    second time.

  15. This is really attention-grabbing, You are an overly skilled blogger.
    I’ve joined your rss feed and look forward to searching for extra of
    your wonderful post. Additionally, I’ve shared your web site in my social networks

  16. Hello, Neat post. There’s an issue with your web site in internet explorer, would check this?
    IE nonetheless is the marketplace chief and a large section of
    other people will omit your fantastic writing due to this problem.

Leave a Reply

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