题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1189
数据生成器：http://paste.ubuntu.com/23173568/
这题还是很好想的，要么二分时间，要么时间上暴力
然而HZWER的做法是错误的，门那里肯定需要按时间拆点
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500000;
const int M = 2000000;
const int L = 30;
const int INF = 10000000;
int n,m,mat[L][L],S,T,vout,dis[N],cur[N];
int nxt[M],to[M],flow[M],head[N],nod_cnt;
char pat[L]; vector<int> num[N],dor; queue<int> que;
#define id(x,y) ((x)+((y)-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] = 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;
}
inline void search(int s){
memset(dis,-1,sizeof(dis));
que.push(s); dis[s] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
int x=w, y=0; while ((y+1)*n < w) y++; x -= y*n; y++;
if (mat[x][y] == 1) Add_Edge(w,num[s][dis[w]],1);
if (x - 1 >= 1 && !~dis[id(x-1,y)] && mat[x-1][y] == 1) que.push(id(x-1,y)), dis[id(x-1,y)] = dis[w] + 1;
if (x + 1 <= n && !~dis[id(x+1,y)] && mat[x+1][y] == 1) que.push(id(x+1,y)), dis[id(x+1,y)] = dis[w] + 1;
if (y - 1 >= 1 && !~dis[id(x,y-1)] && mat[x][y-1] == 1) que.push(id(x,y-1)), dis[id(x,y-1)] = dis[w] + 1;
if (y + 1 <= m && !~dis[id(x,y+1)] && mat[x][y+1] == 1) que.push(id(x,y+1)), dis[id(x,y+1)] = dis[w] + 1;
}
}
int main(){
cin>>m>>n; S = 0; T = N-1; nod_cnt = n*m;
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++)
if (pat[i] == 'X') mat[i][j] = 2;
else if (pat[i] == '.') mat[i][j] = 1, vout++, Add_Edge(S,id(i,j),1);
else dor.push_back(id(i,j));
}
for (int i=0,lim=dor.size();i<lim;i++) for (int k=1;k<=n*m;k++) num[dor[i]].push_back(++nod_cnt);
for (int i=0,lim=dor.size();i<lim;i++) search(dor[i]);
for (int k=0,ret=0;k<n*m;k++) {
ret += Dinic();
if (ret == vout) printf("%d\n",k), exit(0);
for (int i=0,lim=dor.size();i<lim;i++)
Add_Edge(num[dor[i]][k],num[dor[i]][k+1],INF),
Add_Edge(num[dor[i]][k+1],T,1);
} puts("impossible");
return 0;
}
I really love your website.. Great colors & theme.
Did you build this website yourself? Please reply back as I’m wanting to create my own website and would love to
learn where you got this from or just what the theme is named.
Thank you!
Hi! This is my first visit to your blog! We are a group of volunteers
and starting a new initiative in a community in the same niche.
Your blog provided us valuable information to work on. You have
done a extraordinary job!
I’m really enjoying the design and layout
of your site. 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?
Outstanding work!
Heya i am for the first time here. I found this board and I find It truly useful & it helped me out a
lot. I hope to give something back and help others like you helped me.
This is a topic which is near to my heart… Many thanks!
Where are your contact details though?
What’s up to all, how is the whole thing, I think
every one is getting more from this site, and your views are pleasant for new users.
Heya! 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 protect against hackers?
Attractive section of content. I just stumbled upon your web site and in accession capital to assert
that I acquire in fact enjoyed account your blog posts. Anyway I’ll be subscribing to your augment and even I achievement you access consistently
fast.
Nice response in return of this difficulty with solid arguments and describing all regarding that.
Yes! Finally someone writes about quest bars cheap.
Hey! Someone in my Myspace group shared this site with us so I came
to check it out. I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my followers!
Wonderful blog and wonderful style and design.
Hey there! Quick question that’s totally off topic.
Do you know how to make your site mobile friendly? My weblog looks weird when viewing from my apple iphone.
I’m trying to find a theme or plugin that might be able to fix this issue.
If you have any recommendations, please share.
With thanks!
Remarkable! Its in fact awesome piece of writing, I have
got much clear idea about from this article.
Greetings from Ohio! I’m bored at work so I decided to browse your blog on my
iphone during lunch break. I love the knowledge you provide here and can’t wait to take a
look when I get home. I’m shocked at how fast your blog loaded on my cell phone
.. I’m not even using WIFI, just 3G .. Anyways, excellent
blog!
Thank you for every other excellent article. Where else may just anybody get that kind of info in such a perfect manner of writing? I have a presentation subsequent week, and I am on the search for such info.
I loved as much as you will receive carried out right here.
The sketch is attractive, your authored subject matter stylish.
nonetheless, you command get bought an shakiness over that you wish be delivering the following.
unwell unquestionably come more formerly again since exactly the same nearly a lot often inside case you shield this increase.
I couldn’t resist commenting. Well written!
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time
a comment is added I get three e-mails with the same comment.
Is there any way you can remove me from that
service? Thank you!
Thank you for some other magnificent post. Where else could anyone get that kind of information in such a perfect
manner of writing? I have a presentation subsequent week, and I’m on the search for such information.
What’s up, of course this post is actually fastidious and I have learned lot
of things from it on the topic of blogging. thanks.
Pretty component of content. I simply stumbled upon your website 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 success you get admission to
consistently quickly.
This post presents clear idea in support of the
new viewers of blogging, that truly how to do running a blog.
Undeniably consider that which you stated. Your favourite justification appeared to be on the
net the simplest factor to consider of. I say to you, I
definitely get irked while other folks consider concerns that they just do not realize about.
You managed to hit the nail upon the highest and also outlined
out the entire thing with no need side-effects , people could take a signal.
Will likely be back to get more. Thank you
Because the admin of this web site is working, no hesitation very quickly it will be famous, due to its feature contents.
Thanks for the post, how can I make is so that I get an alert email when you publish a new article?