UOJ Logo kczno1的博客

博客

bzoj1189: [HNOI2007]紧急疏散evacuate

2017-04-15 11:37:50 By kczno1

看到有题解说二分,但其实不用二分(二分多一个log)。

从小到达枚举时间p,对每个时间给每个door新建一个点i,
从i向T连一条容量为1的边。
从它p-1的i向p的i连一条容量为inf的边,表示更早的人也可以选择。
从所有跟该door距离为p的人向i连一条容量为1的边,表示他从此时开始可以选择了。
如果满流就退出,否则就接着枚举,并保留当前的那个网络。
(一开始从S向每个人连一条容量为1的边)

处理跟该door距离为p的点 就是 一开始从每个door为起点bfs一遍,处理出距离,再存到vector里面。

我还加了一个剪枝,就是如果没有人和这个door距离为p,就不新建点,把原来的点连向T的边的容量+=1。

(由于很久调试不出来,代码加了一些注释。。)

#include<bits/stdc++.h>
using std::vector;
using std::min;
using std::cerr;using std::endl;

const int N=30,inf=100000000;
const int fx[4]={0,-1,0,1},fy[4]={-1,0,1,0};//四个方向

int door[N<<2],d;//d=door的个数
int now[N<<2],nowe[N<<2];//now=当前时间建的点i,nowe=i连向T的边
int n,m,i,j,x,y,need;//need是还需要流的量
int dy[N][N];//dy[i][j]就是(i,j)对应的点 
char ch[N][N];
vector<int> st[N<<2][N*N];//st[x][p]表示和door[x]距离为p的点

int q[N*N],head,tail;bool vis[N*N];int g[N*N];//g[x]为x到rt的距离
void bfs(vector<int> *a,int rt)
{
    for(;tail>1;--tail)vis[q[tail]]=0;
    g[q[tail=1]=rt]=0;
    for(head=1;head<=tail;++head)
    {
        x=q[head];
        if(head>1) a[g[x]].push_back(x);
        int X=(x-1)/m+1,Y=(x-1)%m+1;
        for(i=0;i<4;++i)
        {
            y=dy[X+fx[i]][Y+fy[i]];
            if(vis[y])continue;//vis[0],vis[墙],vis[门]都=1
            vis[y]=1;q[++tail]=y;
            g[y]=g[x]+1;
        }
    }
}

namespace kcz
{
    const int N=101000,S=N-1,T=N-2;
    int n;
    int t[N];
    struct edge
    {
        int to,next,f;
    }l[1000000];int e=1;
    void add_e(int x,int y,int f)
    {
        l[++e]=(edge){y,t[x],f};t[x]=e;
        l[++e]=(edge){x,t[y]};t[y]=e;
    }

    int q[N],head,tail,i,x,y,g[N],_t[N];//_t是当前弧
    bool bfs()
    {
        q[tail=1]=T;
        for(i=1;i<=n;++i) g[i]=inf;g[S]=inf;
        for(head=1;head<=tail;++head)
        {
            x=q[head];_t[x]=t[x];
            if(g[x]>=g[S])continue;
            for(i=t[x];y=l[i].to;i=l[i].next)
            if(l[i^1].f&&g[y]==inf) 
            {
                g[y]=g[x]+1;q[++tail]=y;
            }
        }
        return g[S]!=inf; 
    }
    int dfs(int x,int f0)
    {
        if(x==T)return f0;
        int f=f0;
        for(int &i=_t[x];y=l[i].to;i=l[i].next)
        if(l[i].f&&g[y]==g[x]-1)
        {
            int del=dfs(y,min(f,l[i].f));
            l[i].f-=del;l[i^1].f+=del;
            f-=del;
            if(!f)return f0;
        }
        return f0-f;
    }

    void solve(int mx)
    {
        int p;
        for(p=1;need&&p<=mx;++p)
        {
            for(x=1;x<=d;++x)
            {
                if(!st[x][p].size()){ ++l[nowe[x]].f;continue; } 
                ++n; 
               if(now[x]) add_e(now[x],++n,inf);
               add_e(n,T,1);
               now[x]=n;nowe[x]=t[n];
               for(j=0;j<st[x][p].size();++j)
                 add_e(st[x][p][j],n,1);
            }        
            while(bfs()) 
             need-=dfs(S,inf);
        }
        if(need)puts("impossible");
        else printf("%d\n",p-1);
    }
};

int main()
{ freopen("1.in","r",stdin);freopen("1.out","w",stdout);
        scanf("%d%d",&n,&m);
    int i,j,x;
    for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
     dy[i][j]=++kcz::n;
    for(i=1;i<=n;++i) 
    {scanf("%s",ch[i]+1);
     for(j=1;j<=m;++j)
     {
         x=dy[i][j];
        if(ch[i][j]=='X') {vis[x]=1;continue;}
        if(ch[i][j]=='D') {door[++d]=x;vis[x]=1;}
        else {kcz::add_e(kcz::S,x,1);++need;}
     }
    } 
    vis[0]=1;
    for(x=1;x<=d;++x) 
     bfs(st[x],door[x]);
    kcz::solve(n*m);
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。