题解：P3191 [HNOI2007] 紧急疏散（EVACUATE）

· · 题解

阅读本题解前建议先看一下这篇文章，讲的是此题弱化版的建图方式。

Solution

和 P3851 [TJOI2007] 脱险 很像，要求最小的时间，很容易想到可以二分。但是每一次都要重新建图并且重新跑网络流，很容易死，反正我自己没办法卡过去。

然后考虑从小到大枚举时间，每一次新加边，并在上一次的残留图上继续跑网络流，这样时间复杂度会大大降低。

:::success[code]


#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{int u,v,w;};
int T,n,m,s,t=7349,d[7350],flag[7350];
char ch[15][15];
int fx[5]={0,1,0,-1,0};
int fy[5]={0,0,1,0,-1};
vector<node> edges;
vector<int> e[7350];
queue<int> q;
int f(int T,int i,int j){return T*n*m+(i-1)*m+j;}
void add(int u,int v,int w){
    edges.push_back({u,v,w});
    edges.push_back({v,u,0});
    e[u].push_back(edges.size()-2);
    e[v].push_back(edges.size()-1);
}
bool bfs(){
    memset(d,0,sizeof d);
    while(!q.empty()) q.pop(); 
    d[s]=1,q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto to:e[u]){
            int v=edges[to].v;
            if(!d[v]&&edges[to].w){
                d[v]=d[u]+1;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int flow){
    if(u==t) return flow;
    int sum=0;
    for(int i = flag[u];i<e[u].size();i++){
        int v=edges[e[u][i]].v;
        if(edges[e[u][i]].w&&d[v]==d[u]+1){
            int tmp=dfs(v,min(flow,edges[e[u][i]].w));
            sum+=tmp,flow-=tmp,edges[e[u][i]].w-=tmp,edges[e[u][i]^1].w+=tmp;
            if(!flow) break;
        }
    }
    if(!sum) d[u]=-1;
    return sum;
}
int dinic(){
    int ans=0;
    while(bfs()){
        memset(flag,0,sizeof flag);
        ans+=dfs(s,1e18);
    }
    return ans;
}
signed main(){
    cin>>n>>m>>T;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin>>ch[i][j];
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            if(ch[i][j]=='P')
                add(s,f(0,i,j),1);
    for(int i = 0;i<=T;i++)
        for(int j = 1;j<=n;j++)
            for(int k = 1;k<=m;k++)
                if(ch[j][k]=='O')
                    add(f(i,j,k),t,1);
    for(int i = 0;i<T;i++)
        for(int j = 2;j<n;j++)
            for(int k = 2;k<m;k++){
                add(f(i,j,k),f(i+1,j,k),1e9);
                for(int kk = 1;kk<=4;kk++)
                    if((ch[j][k]=='P'||ch[j][k]=='.')&&ch[j+fx[kk]][k+fy[kk]]!='*')
                        add(f(i,j,k),f(i+1,j+fx[kk],k+fy[kk]),1e9);
            }
    cout<<dinic();
    return 0;
}