题解 P3191 【[HNOI2007]紧急疏散EVACUATE】

· · 题解

前言:本弱鸡也是看了网上某dalao的博客才会写的,此博客链接:租酥雨

怎么写网络流呢,每个人向 mid 时间内可达之门连一张边吗?
题目要求:"每一秒钟只能有一个人移动到门的位置".为了解决这个唯一性,需要把每一扇门拆成 mid 个点. mid 个点各向T连一条1边.
(不熟悉拆点可以做一做SCOI2007修车)

怎么连人与门之间的边?我提供两种方法:

问题就解决了.

代码如下:

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline

#define _ 1001
#define A 23*23
#define INF 2139062143


using namespace std;


int n,m,pnum,dnum,Dis[21][21],ps,ds,D[A][A],ct=1,h[_*_],S,T,cur[_*_],dep[_*_];
int u[4]={-1,0,1,0};
int v[4]={0,1,0,-1};
char mp[21][21];
struct Dot
{
    int x,y;
}p[_],d[_];
struct ed{int t,nxt,w;}e[_*_];


void add(int fr,int t,int w)
{
    e[++ct]=(ed){t,h[fr],w};h[fr]=ct;
    e[++ct]=(ed){fr,h[t],0};h[t]=ct;
}


void Bfs(Dot pp,int ID)
{
    queue<Dot>Q;
    while(!Q.empty())Q.pop();
    Q.push(pp);
    memset(Dis,0x7f,sizeof(Dis));
    Dis[pp.x][pp.y]=0;
    while(!Q.empty())
    {
        Dot uo=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int xo=uo.x+u[i],yo=uo.y+v[i];
            if(xo<1||xo>n||yo<1||yo>m||mp[xo][yo]=='X')continue;
            if(Dis[xo][yo]>Dis[uo.x][uo.y]+1)
            {
                Dis[xo][yo]=Dis[uo.x][uo.y]+1;
                Q.push((Dot){xo,yo});
            }
        }
    }
    for(int i=1;i<=dnum;i++)
        D[ID][i]=Dis[d[i].x][d[i].y];//pipo->door
}


int bfs()
{
    memset(dep,0,sizeof(dep));
    dep[S]=1;
    queue<int>Q;Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=h[u];i;i=e[i].nxt)
        {
            int v=e[i].t;
            if(!dep[v]&&e[i].w>0)
            {
                dep[v]=dep[u]+1;Q.push(v);
            }
        }
    }
    return dep[T];
}


int dfs(int u,int flow)
{
    if(u==T)return flow;
    for(int &i=cur[u];i;i=e[i].nxt)
    {
        int v=e[i].t;
        if(e[i].w&&dep[v]==dep[u]+1)
        {
            int temp=dfs(v,min(flow,e[i].w));//is w,not t!!!
            if(temp)
            {
                e[i].w-=temp;
                e[i^1].w+=temp;
                return temp;
            }
        }
    }
    return 0;
}


int Dinic()
{
    int ret=0;
    while(bfs())
    {
        for(int i=ct;i;i--)cur[i]=h[i];
        while(int tp=dfs(S,INF))
        {
            ret+=tp;
        }
    }
    return ret;
}


bool check(int mid)
{
    S=dnum*mid+pnum+1,T=S+1;
    memset(h,0,sizeof(h));
    ct=1;

    for(int i=1;i<=dnum;i++)
    {
        for(int j=1;j<=mid;j++)
        {
            add((i-1)*mid+j,T,1);
            if(j^mid)
            {               
                add((i-1)*mid+j,(i-1)*mid+j+1,INF);
            }
        }
    }

    for(int i=1;i<=pnum;i++)
        add(S,dnum*mid+i,1);

    for(int i=1;i<=pnum;i++)
    {
        for(int j=1;j<=dnum;j++)
        {
            if(D[i][j]<=mid)
            {
                add(dnum*mid+i,(j-1)*mid+D[i][j],1);
            }
        }
    }

    return Dinic()==pnum;
}


void Mid()
{
    int l=1,r=20*20,ans=-1,mid;

    while(l<=r)check(mid=((l+r)>>1))?ans=mid,r=mid-1:l=mid+1;

    if(ans==-1)
        puts("impossible");
    else
        printf("%d\n",ans);
}


int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='.')
                p[++pnum]=(Dot){i,j};
            else
                if(mp[i][j]=='D')d[++dnum]=(Dot){i,j};
        }
    }

    for(int i=1;i<=pnum;i++)
        Bfs(p[i],i);

    Mid();

    return 0;
}

后记: //管理员应该看不到吧￣ω￣

Noip之前最后一篇题解,估计也是真·最后一篇了,让我如英雄末路一般说几句无关紧要的话吧:"本人不聪明却搞oi,学得晚却不甘心居于人后、刚认识到它的魅力时却要因为自己的辣鸡、学科的压力而离开了,离开这个纯净的机房,离开机房里我倾慕的男孩了...我希望朋友你能珍惜oi的时光,因为这是多少人为之神伤的世外桃源、宝贵之物啊..."