1189: [HNOI 2007] 긴급 대피 evacuate 이분 답 + 네트워크 흐름

수수께끼 의 WA 야.데이터 가 현지에서 다 지 나 갔 군요.(내 가 불복 하 는 한 조 한 조 ctrl + v 들 어 갔 어...)
인터넷 흐름 문제.그래서 최 우성 문 제 는 판정 적 인 문제 로 바 뀌 었 다.판사 할 때마다 인터넷 이 흘러 와 서건 도: S - > '.' flow = 1; '.' - > 'D’ flow=1 (d[‘.’][‘D’]<=mid); ‘D’->T flow=mid; 비교적 신기 한 데 이 터 는 지나 갈 수 없다. XXDXX XX. XX X. X XXDXX 의 답 은 분명히 3 이 고 나의 프로그램 은 2 이다.그러나.그런 데 이 터 는 없습니다.QAQ。
수수께끼 의 WA 코드:

#include
#include
#include
#define inf 1000000007
using namespace std;
char s[25];
int n,m,dfn,S,T,cnt,cnt1,cnt2;
int next[1000005],key[1000005],list[1000005];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int mp[25][25],id[25][25],mark[25][25];
int inq[505],q[505][3],dis[505],human[505],door[505],head[505],d[505][505];
inline int read()
{
    int a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}
inline void insert(int x,int y,int z)
{
    next[++cnt]=head[x];
    head[x]=cnt;
    list[cnt]=y;
    key[cnt]=z;
}
inline void bfs(int sx,int sy)
{
    int t=0,w=1,x,y,xi,yi;
    q[1][0]=sx; q[1][1]=sy; q[1][2]=0;
    while (tx=q[++t][0]; y=q[t][1];
        for (int k=0;k<4;k++)
        {
            xi=x+dx[k]; yi=y+dy[k];
            if (xi<1||xi>n||yi<1||yi>m||mp[xi][yi]==0||mark[xi][yi]==dfn) continue;
            q[++w][0]=xi; q[w][1]=yi; q[w][2]=q[t][2]+1; mark[xi][yi]=dfn;
            if (mp[xi][yi]==2) d[id[sx][sy]][id[xi][yi]]=q[w][2];
        }
    }
}
inline void build(int mid)
{
    cnt=1;
    memset(head,0,sizeof(head));
    for (int i=1;i<=cnt1;i++) insert(S,human[i],1),insert(human[i],S,0);
    for (int i=1;i<=cnt2;i++) insert(door[i],T,mid),insert(T,door[i],0);
    for (int i=1;i<=cnt1;i++)
        for (int j=1;j<=cnt2;j++)
            if (d[human[i]][door[j]]<=mid) 
                insert(human[i],door[j],1),insert(door[j],human[i],0);
}
inline bool BFS()
{
    memset(dis,-1,sizeof(dis));
    dis[S]=1; inq[1]=S;
    int t=0,w=1,x;
    while (tx=inq[++t];
        for (int i=head[x];i;i=next[i]) 
            if (key[i]&&dis[list[i]]==-1)
            {
                dis[list[i]]=dis[x]+1;
                inq[++w]=list[i];
            }
    }
    return dis[T]!=-1;
}
int find(int x,int flow)
{
    if (x==T) return flow;
    int w,used=0;
    for (int i=head[x];i;i=next[i])
        if (key[i]&&dis[list[i]]==dis[x]+1)
        {
            w=find(list[i],min(key[i],flow-used));
            key[i]-=w; key[i^1]+=w; used+=w;
            if (used==flow) return flow;
        }
    if (!used) dis[x]=-1;
    return used;
}
inline bool judge()
{
    int tmp=0;
    while (BFS()) tmp+=find(S,inf);
    return tmp==cnt1;
}
int main()
{
    n=read(); m=read(); T=n*m+1;
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for (int j=1;j<=m;j++)
            switch(s[j])
            {
                case 'X':
                    mp[i][j]=0;
                    break;
                case '.':
                    mp[i][j]=1;
                    break;
                case 'D':
                    mp[i][j]=2;
                    break;
            }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            id[i][j]=(i-1)*m+j;
            if (mp[i][j]==1) human[++cnt1]=id[i][j];
            if (mp[i][j]==2) door[++cnt2]=id[i][j];
        }
    for (int i=1;i<=cnt1;i++)
        for (int j=1;j<=cnt2;j++)
            d[human[i]][door[j]]=inf;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            dfn++;
            if (mp[i][j]==1) bfs(i,j);
        }
    int l=0,r=inf,ans=inf;
    while (l<=r)
    {
        int mid=l+r>>1;
        build(mid);
        if (judge()) ans=mid,r=mid-1; else l=mid+1;
    }
    if (ans==inf) puts("impossible"); else printf("%d
",ans);
    return 0;
}