题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2127
数据传送门：http://pan.baidu.com/s/1c1Ldkp6
这题的输入数据我已无力吐槽……
为此wa了两个小时
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 100+9;
const int N = 10000+9;
const int M = 500000+9;
const int INF = 100000000;
int head[N],nxt[M],to[M],flow[M],n,m,vout,wen[L][L],li[L][L];
int dis[N],cur[N],S,T; 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 i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), wen[i][j] += tmp*2;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), li[i][j] += tmp*2;
for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), wen[i][j] += tmp, wen[i+1][j] += tmp;
for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), li[i][j] += tmp, li[i+1][j] += tmp;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), wen[i][j] += tmp, wen[i][j+1] += tmp;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), li[i][j] += tmp, li[i][j+1] += tmp;
for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) Add_Edge(S,id(i,j),wen[i][j]), Add_Edge(id(i,j),T,li[i][j]);
printf("%d\n",vout-Dinic()/2);
return 0;
}
哇塞，居然是沙发？留个名
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! However, how can we communicate?
It’s the best time to make a few plans for the future and it
is time to be happy. I’ve read this put
up and if I may just I desire to suggest you few
interesting issues or advice. Perhaps you could write next articles relating to this article.
I desire to learn even more issues approximately
it!
I blog frequently and I genuinely appreciate your content.
This article has truly peaked my interest. I will bookmark your site and keep checking for
new information about once per week. I subscribed to
your RSS feed too.
You can definitely see your expertise within the article you write.
The world hopes for even more passionate writers such as you who aren’t afraid to mention how they believe.
At all times go after your heart.
Excellent web site you’ve got here.. It’s hard to find high quality writing like yours these days.
I really appreciate individuals like you! Take care!!
When someone writes an paragraph he/she retains the thought of
a user in his/her brain that how a user can understand it.
Therefore that’s why this post is amazing. Thanks!
It’s hard to come by knowledgeable people in this particular topic, however, you seem like you know what you’re talking about!
Thanks
Hey! I know this is kinda off topic however I’d figured
I’d ask. Would you be interested in exchanging links or maybe guest authoring a blog post or
vice-versa? My site addresses a lot of the same topics as
yours and I believe we could greatly benefit from each other.
If you are interested feel free to shoot me an e-mail.
I look forward to hearing from you! Terrific blog by the way!
I am not sure where you are getting your information, but
good topic. I needs to spend some time learning more or understanding more.
Thanks for magnificent information I was looking for this info for my mission.
When someone writes an post he/she maintains the idea
of a user in his/her brain that how a user can be aware of
it. So that’s why this article is outstdanding. Thanks!
Hi there, just became aware of your blog through Google, and found that it’s truly informative.
I am gonna watch out for brussels. I will appreciate if you continue
this in future. Numerous people will be benefited from your writing.
Cheers!
I do not know whether it’s just me or if perhaps
everyone else encountering issues with your blog.
It appears as if some of the written text in your posts are
running off the screen. Can someone else please provide feedback and let me know if this
is happening to them as well? This may be a issue with my internet browser because
I’ve had this happen previously. Cheers
Fantastic web site. Lots of helpful info here. I am sending it to
some pals ans also sharing in delicious. And naturally, thanks for your effort!
You’re so cool! I do not believe I’ve truly read through a single thing like this before.
So wonderful to discover someone with some genuine thoughts on this subject.
Seriously.. thanks for starting this up. This website is something that’s needed on the web, someone with a bit of originality!
I was recommended this web site via my cousin. I am not positive whether this submit is written by way of him as no one else recognise such distinctive about my trouble. You’re wonderful! Thanks!
When someone writes an post he/she keeps the idea of a user in his/her brain that how a user can understand
it. Thus that’s why this piece of writing is amazing. Thanks!
I think that what you said was actually very logical.
However, what about this? what if you were to write a awesome headline?
I am not suggesting your information is not good, but suppose you added something
to maybe get people’s attention? I mean 【BZOJ 2127】happiness – Qizy's Database is kinda vanilla.
You ought to glance at Yahoo’s front page and note how they write post
titles to get people interested. You might add a
related video or a picture or two to get readers excited about what you’ve written. Just my opinion, it would make your posts
a little bit more interesting.
Excellent post. I used to be checking continuously
this weblog and I am impressed! Very helpful info specifically the last section 🙂 I handle such
info a lot. I was looking for this particular info for a long time.
Thank you and good luck.
I would like to thank you for the efforts you have put
in penning this site. I really hope to check out the same high-grade
blog posts by you in the future as well. In truth, your creative writing abilities has encouraged me to get my very own site now 😉
If you want to increase your experience simply keep visiting this web page and be updated with
the newest news posted here.
Pretty nice post. I just stumbled upon your blog and wanted to say that I’ve really enjoyed browsing your blog
posts. After all I will be subscribing to your feed and I hope you write
again soon!
This is very interesting, You are a very skilled blogger.
I have joined your rss feed and look forward to seeking more of your magnificent
post. Also, I’ve shared your web site in my social networks!
I’ve been exploring for a little for any high-quality articles or weblog posts in this sort of space .
Exploring in Yahoo I eventually stumbled upon this site.
Studying this info So i’m happy to convey that I’ve an incredibly good
uncanny feeling I came upon exactly what I
needed. I most for sure will make certain to don?t forget this website and
give it a look regularly.
Thanks for finally talking about >【BZOJ 2127】happiness – Qizy’s Database <Loved it!
I was looking through some of your blog posts on this site and I conceive this web site is very informative ! Retain posting.