POJ 3057 Evacuation 二分图匹配-白红宇

POJ 3057 Evacuation 二分图匹配

阅读量：5817 次

发布时间：2019-06-18

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

每个门每个时间只能出一个人，那就把每个门拆成多个，对应每个时间。

不断增加时间，然后增广，直到最大匹配。

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
                    
                      pii;#define pb(a) push(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template
                     
                       T min(const T& a,const T& b,const T& c){ return min(min(a,b),min(a,c));}template
                      
                        T max(const T& a,const T& b,const T& c){ return max(max(a,b),max(a,c));}void debug(){#ifdef ONLINE_JUDGE#else freopen("data.in","r",stdin); // freopen("d:\\out1.txt","w",stdout);#endif}int getch(){ int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}int DX[] = { 0, 1, 0, -1};int DY[] = { 1, 0, -1, 0};const int maxn = 15;char grid[maxn][maxn];int n, m;int dist[maxn][maxn][maxn][maxn];int vis[maxn][maxn];vector
                       
                         dx,dy,px,py;void bfs(int X,int Y){ queue
                        
                          qx,qy; qx.push(X); qy.push(Y); memset(vis, 0, sizeof(vis)); vis[X][Y] = true; while(!qx.empty()) { int x = qx.front(); qx.pop(); int y = qy.front(); qy.pop(); for(int d=0; d<4; d++) { int nx = x + DX[d]; int ny = y + DY[d]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&grid[nx][ny]=='.'&&!vis[nx][ny]) { vis[nx][ny] = true; dist[X][Y][nx][ny] = dist[X][Y][x][y] + 1; qx.push(nx); qy.push(ny); } } }}void prework(){ memset(dist, -1, sizeof(dist)); dx.clear(); dy.clear(); px.clear(); py.clear(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(grid[i][j]=='D') { dx.push_back(i); dy.push_back(j); dist[i][j][i][j]=0; bfs(i, j); }else if(grid[i][j]=='.') { px.push_back(i); py.push_back(j); } } //printf("prework: %d %d\n",dx.size(), px.size());}const int maxv = 101*50 + 110;int id[maxn][maxn][110];bool used[maxv];int match[maxv];int vcnt;vector
                         
                           g[maxv];int ID(int x, int y, int t){ int &a = id[x][y][t]; if(a==0) a=++vcnt; return a;}void add(int u,int v){ g[u].push_back(v); g[v].push_back(u);}void init(){ for(int i=1; i