枚举日期day,把每一天拆成day个点跑网络流,具体做法和星际转移问题差不多

我看了题解一圈发现全是什么二分答案+拆门,感觉写起来有点麻烦就懒得写了

#include<bits/stdc++.h>
using namespace std;
const int N=1500000+5,inf=0x3f3f3f3f;
struct edge{
	int to,nxt,val,cost;
}e[N<<5];
int head[N],cnt,maxflow,vis[N],dis[N],nxt[N];
int s,t;
void add_edge(int x,int y,int z){
	e[++cnt].to=y; e[cnt].val=z; e[cnt].nxt=head[x]; head[x]=cnt;
}
void add(int x,int y,int z){
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
//	cout<<dis[0]<<" "<<-inf<<endl;
	dis[s]=0; q.push(s);
	while(!q.empty()){
		int u=q.front(); q.pop(); vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
			if(e[i].val && dis[e[i].to]>dis[u]+1){
				dis[e[i].to]=dis[u]+1;
				if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
			}
	}
	return (dis[t])^inf;
}
bool flag[N];
int dfs(int u,int limit){
	if(u==t) return limit;
	int flow=0;
	for(int i=head[u];i&&limit;i=e[i].nxt)
		if(e[i].val &&dis[e[i].to]==dis[u]+1){
			int k=dfs(e[i].to,min(limit,e[i].val));
			if(k>0){
				e[i].val-=k; e[i^1].val+=k;
				limit-=k; flow+=k;			
			}
		}
	if(!flow) dis[u]=inf;
	return flow;
}
void Dinic(){
	while(spfa()) maxflow+=dfs(s,inf);
}
int a[105][105],n,m;
int num(int i,int j,int k){
	return (i-1)*m+j+k*n*m;
}
int di[4]={0,1,0,-1};
int dj[4]={1,0,-1,0};
char ch;
int main(){
	cin>>n>>m;
	int tot=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			cin>>ch;
			if(ch=='.') ++tot,a[i][j]=0;
			if(ch=='X') a[i][j]=1;
			if(ch=='D') a[i][j]=2; 
		}
	int day=0;
	s=0; t=1145140;
	while(day<500){
		if(day==0){
			for(int i=1;i<=n;++i)
				for(int j=1;j<=m;++j)
					if(a[i][j]==0) add(s,num(i,j,day),1);
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(a[i][j]==2) add(num(i,j,day),t,1);		
		if(day){
			for(int i=1;i<=n;++i)
				for(int j=1;j<=m;++j){
					if(a[i][j]==0) add(num(i,j,day-1),num(i,j,day),inf);
					for(int k=0;k<4;++k){
						int ti=i+di[k],tj=j+dj[k];
						if(1<=ti&&ti<=n&&1<=tj&&tj<=m&&a[ti][tj]!=1) add(num(i,j,day-1),num(ti,tj,day),1);
					}
				}
		}
		Dinic();
		if(maxflow>=tot) return cout<<day,0; 
		++day;
	}
	cout<<"impossible";
	return 0;
}