POJ 3057 Evacuation（二分匹配）-白红宇

POJ 3057 Evacuation（二分匹配）

阅读量：6305 次

发布时间：2019-06-22

本文共 2338 字，大约阅读时间需要 7 分钟。

分析：

这是一个时间和门的二元组(t,d)和人p匹配的问题，当我们固定d₀时，(t,d₀)匹配的人数和t具有单调性。

t增加看成是多增加了边就行了，所以bfs处理出p到每个d的最短时间，然后把(t,d)和p连边，按t从小到大

枚举点增广就好了。无解的情况只有一种，某个人无论如何都无法出去。

/**********************************************************      --Sakura hirahira mai orite ochite--              **   author AbyssalFish                                   ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long ll;const int XY = 12, MAX_D = 44, MAX_P = 100;//..MAX_Tchar maz[XY][XY+1];const int maxv = MAX_D*MAX_P, maxe = maxv*MAX_P;int hd[maxv],to[maxe],nx[maxe],ec;#define eachEage int i = hd[u]; ~i; i = nx[i]void add(int u,int v){ nx[ec] = hd[u]; to[ec] = v; hd[u] = ec++;}#define PB push_back#define resv(x,n) x.reserve(n);#define PS pushvector
                 
                   pX, pY, dX, dY;const int dx[] = { 0,0,-1,1}, dy[] = { 1,-1,0,0};int dist[XY][XY][XY][XY];int X,Y;void bfs(int x,int y){ int (* const d)[XY] = dist[x][y]; memset(d,0xff,sizeof(dist[x][y])); queue
                  
                    qx, qy; d[x][y] = 0; qx.PS(x); qy.PS(y); while(qx.size()){ x = qx.front(); qx.pop(); y = qy.front(); qy.pop(); for(int k = 4; k--;){ int nx = x+dx[k], ny = y+dy[k]; if(0<=nx && nx
                   
                    >T; while(T--){ scanf("%d%d",&X,&Y); pX.clear(); pY.clear(); dX.clear(); dY.clear(); for(int i = 0; i < X; i++){ scanf("%s", maz[i]); for(int j = 0; j < Y; j++){ if(maz[i][j] == 'D'){ dX.PB(i); dY.PB(j); } else if(maz[i][j] == '.'){ pX.PB(i); pY.PB(j); } } } int d = dX.size(), p = pX.size(); if(p == 0){ puts("0"); continue; } for(int i = 0; i < d; i++){ bfs(dX[i],dY[i]); } int n = (X-2)*(Y-2); bool fail = false; memset(hd,0xff,sizeof(int)*n*d); ec = 0; for(int i = 0; i < p; i++){ bool escape = false; for(int j = 0; j < d; j++){ if(dist[dX[j]][dY[j]][pX[i]][pY[i]] > 0){ if(!escape) escape = true; for(int k = dist[dX[j]][dY[j]][pX[i]][pY[i]]-1; k < n; k++){ add(k*d+j, i); } } } if(!escape){ fail = true; break; } } if(fail){ puts("impossible"); continue; } memset(link,-1,sizeof(int)*p); int cnt = 0, ans; for(int i = 0; i < n*d; i++){ clk++; if(aug(i) && ++cnt == p) { ans = i/d+1; } } printf("%d\n", ans); } return 0;}