题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1066
喜闻乐见大水题！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 25;
const int N = L*L*2+9;
const int M = N*100;
const int INF = 10000000;
int nxt[M],to[M],flow[M],head[N],dis[N],cur[N];
int m,n,d,mat[L][L],vout,S,T;
char pat[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(x,y,ty) ((x)+((y)-1)*n+(ty)*m*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] = 0;
}
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(); d = read(); S = 0; T = N-1;
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++) mat[i][j] = pat[i] - '0';
for (int i=1;i<=n;i++) if (mat[i][j]) Add_Edge(id(i,j,0),id(i,j,1),mat[i][j]);
}
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++) if (pat[i] == 'L') Add_Edge(S,id(i,j,0),1), vout++;
}
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if (mat[i][j]) {
if (min(min(i,n-i+1),min(j,m-j+1)) <= d) Add_Edge(id(i,j,1),T,INF);
for (int x=1;x<=n;x++) for (int y=1;y<=m;y++)
if (mat[x][y] && abs(x-i)+abs(y-j) <= d) Add_Edge(id(i,j,1),id(x,y,0),INF);
}
vout -= Dinic();
printf("%d\n",vout);
return 0;
}
Magnificent goods from you, man. I have understand your stuff previous to and you’re just
extremely wonderful. I actually like what you’ve acquired here, certainly like what you’re saying
and the way in which you say it. You make it enjoyable and you still care for
to keep it sensible. I can not wait to read far more from
you. This is actually a terrific web site.
Hi, I want to subscribe for this web site to obtain most recent updates, therefore
where can i do it please help out.
My brother suggested I would possibly like this website.
He was totally right. This put up truly made
my day. You can not imagine simply how a lot time I
had spent for this info! Thank you!
I blog often and I genuinely appreciate your content.
This article has really peaked my interest. I will book mark your blog
and keep checking for new details about once a week. I opted in for your Feed too.
With havin so much content and articles do you ever
run into any issues of plagorism or copyright infringement?
My website has a lot of exclusive content I’ve either
created myself or outsourced but it appears a lot of it is popping it up all over the internet without
my permission. Do you know any techniques to help prevent
content from being stolen? I’d definitely appreciate it.
Hello friends, pleasant post and pleasant urging
commented here, I am in fact enjoying by these.
Have you ever considered about including a little bit more than just your articles?
I mean, what you say is valuable and all. Nevertheless just
imagine if you added some great images or video clips to
give your posts more, “pop”! Your content is excellent but with pics and video clips, this website
could undeniably be one of the best in its niche.
Amazing blog!
My family always say that I am wasting my time here at web, however I know I am
getting know-how everyday by reading such pleasant articles or reviews.
Hello! Do you use Twitter? I’d like to follow you
if that would be okay. I’m undoubtedly enjoying your blog and look forward to
new posts.
My brother suggested I may like this blog. He used to be entirely right. This put up actually made my day. You cann’t believe simply how much time I had spent for this info! Thank you!
I do accept as true with all the concepts you’ve introduced to your post.
They are very convincing and can definitely work. Still, the posts are very quick for novices.
May you please extend them a little from next time?
Thank you for the post.
Just want to say your article is as astounding.
The clarity to your publish is just nice and that i could suppose you’re a professional on this
subject. Well together with your permission let me to clutch your feed to stay updated with forthcoming post.
Thanks a million and please carry on the enjoyable work.
Appreciating the hard work you put into your site and in depth information you provide.
It’s good to come across a blog every once in a while that isn’t the same out of date rehashed information. Wonderful
read! I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.
Link exchange is nothing else except it is simply placing the other person’s website link
on your page at suitable place and other person will also do similar in favor
of you.
I have read a few good stuff here. Certainly price bookmarking for revisiting.
I wonder how a lot attempt you put to make this kind of great informative website.
I was curious if you ever considered changing the page layout of your blog?
Its very well written; I love what youve got to say. But maybe
you could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having 1 or 2 pictures.
Maybe you could space it out better?
I am actually thankful to the holder of this website who has shared this impressive paragraph
at at this place.
Nice blog here! Also your website so much up very fast! What host are
you the usage of? Can I get your affiliate link
in your host? I desire my site loaded up as fast as yours
lol
First off I want to say terrific blog! I had a quick question which I’d like to ask if
you don’t mind. I was interested to know how you center yourself and clear your mind prior to writing.
I’ve had a tough time clearing my thoughts in getting my thoughts out.
I do enjoy writing but it just seems like the first
10 to 15 minutes are generally wasted simply just trying to figure out how to begin. Any suggestions or tips?
Kudos!
Hello, Neat post. There is an issue along with your website in web explorer, would test this?
IE still is the marketplace leader and a good component of folks will miss your fantastic writing due to this problem.
No matter if some one searches for his essential thing,
therefore he/she needs to be available that in detail, thus
that thing is maintained over here.
This actually answered my drawback, thanks!