题解：P3851 [TJOI2007] 脱险

· · 题解

Soluition

和 P2754 [CTSC1999] 家园 / 星际转移问题很像，都是分层图网络流。

看到出口每个时刻只能通过一个人，人傻了，这该怎么做啊？很简单，把一张图拆成 T 个图，表示每个时刻的节点。一个人走到相邻的点，并花费 1 的时间，就相当于走到了下一张图里，然后每个时刻的出口向汇点连容量为 1 的边，意为每个时刻仅能通过一人。

:::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;
}