UVALive 6557 Stampede!(最大流)

UVALive 6557 Stampede!(最大流)

枚举时间（即答案）加点，将所有的点，每个点分成进来的点和出去的点，建容量为1的边。一直跑到可行为止，即最大流为n

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std ;

const int N = 700000 ;
const int M = 4000000 ;
const int INF = 1111111111 ;
struct Edge {
    int from , to , cap , next ;
} edge[M] ;
int head[N] , tot ;

void new_edge ( int from , int to , int cap ) {
    edge[tot].from = from ;
    edge[tot].to = to ;
    edge[tot].cap = cap ;
    edge[tot].next = head[from] ;
    head[from] = tot ++ ;
    edge[tot].from = to ;
    edge[tot].to = from ;
    edge[tot].cap = 0 ;
    edge[tot].next = head[to] ;
    head[to] = tot ++ ;
}
struct Max_Flow {
    int dis[N] , s , t , cur[N] ;
    queue<int> Q ;
    bool bfs ( int n ) {
        int i , u , v ;
        for ( i = 1 ; i <= n ; i ++ ) dis[i] = INF ;
        dis[s] = 0 ; Q.push ( s ) ;
        while ( !Q.empty () ) {
            u = Q.front () ; Q.pop () ;
            for ( i = head[u] ; i != -1 ; i = edge[i].next ) {
                v = edge[i].to ;
                if ( dis[v] == INF && edge[i].cap ) {
                    dis[v] = dis[u] + 1 ;
                    Q.push ( v ) ;
                }
            }
        }
        return dis[t] != INF ;
    }
    int dfs ( int u , int a ) {
        if ( u == t || !a ) return a ;
        int f , flow = 0 ;
        for ( int& i = cur[u] ; i != -1 ; i = edge[i].next ) {
            int v = edge[i].to ;
            if ( dis[v] == dis[u] + 1 && ( f = dfs ( v , min ( a , edge[i].cap ) ) ) ) {
                flow += f ;
                edge[i].cap -= f ;
                edge[i^1].cap += f ;
                a -= f ;
                if ( a == 0 ) break ;
            }
        }
        return flow ;
    }
    int dinic ( int s , int t , int n ) {
        this->s = s ; this->t = t ;
        int flow = 0 ;
        while ( bfs ( n ) ) {
            for ( int i = 1 ; i <= n ; i ++ )
                cur[i] = head[i] ;
            flow += dfs ( s , INF ) ;
        }
        return flow ;
    }
} AC ;

int p[26][26][1111][2] , cnt , tail[26] ;
int tran ( int x , int y , int n ) {
    return ( x - 1 ) * n + y ;
}

char mp[55][55] ;
int dir[5][2] = { 1 , 0 , 0 , 1 , -1 , 0 , 0 , -1 , 0 , 0 } ;
int main () {
    int n , i , j , k ;
    int ca = 0 ;
    while ( scanf ( "%d" , &n ) && n ) {
        for ( i = 1 ; i <= n ; i ++ )
            scanf ( "%s" , mp[i] + 1 ) ;
        int s = 1 , t = 2 ;
        tot = 0 ;
        memset (head , -1 , sizeof ( head ) ) ;
        memset ( p , 0 , sizeof ( p ) ) ;
        cnt = 2 ;
        int ans = 0 ;
        for ( i = 1 ; i <= n ; i ++ ) {
            tail[i] = ++ cnt ;
            new_edge ( tail[i] , t , 1 ) ;
      //      printf ( "%d ----> %d\n" , tail[i] , t ) ;
        }
        for ( i = 1 ; i <= n ; i ++ ) {
            int v = tran ( i , 1 , n ) + cnt ;
     //       printf ( "%d ----> %d\n" , s , v ) ;
            new_edge ( s , v , 1 ) ;
        }
        for ( i = 1 ; ; i ++ ) {
            for ( j = 1 ; j <= n ; j ++ )
                for ( k = 1 ; k <= n ; k ++ ) {
                    if ( mp[j][k] == 'X' ) continue ;
                    int u = tran ( j , k , n ) + cnt ;
                    int v = u + n * n ;
             //       printf ( "%d ----> %d\n" , u , v ) ;
                    new_edge ( u , v , 1 ) ;
                }
            if ( i != 1 ) {
                for ( j = 1 ; j <= n ; j ++ )
                    for ( k = 1 ; k <= n ; k ++ ) {
                        if ( mp[j][k] == 'X' ) continue ;
                        int u = tran ( j , k , n ) + cnt - n * n ;
                        for ( int t = 0 ; t < 5 ; t ++ ) {
                            int x = j + dir[t][0] ;
                            int y = k + dir[t][1] ;
                            if ( x <= 0 || x > n || y <= 0 || y > n || mp[x][y] == 'X' ) continue ;
                            int v = tran ( x , y , n ) + cnt ;
                 //           printf ( "%d ----> %d\n" , u , v ) ;
                            new_edge ( u , v , 1 ) ;
                        }
                    }
            }
                for ( j = 1 ; j <= n ; j ++ ) {
                    int v = tran ( j , n , n ) + cnt + n * n ;
                    new_edge ( v , tail[j] , 1 ) ;
              //     printf ( "%d ----> %d\n" , v , tail[j] ) ;
                }
            cnt += 2 * n * n ;
            ans += AC.dinic ( s , t , cnt ) ;
            if ( ans == n ) break ;
        }
        printf ( "Case %d: %d\n" , ++ ca , i - 1 ) ;
    }
    return 0 ;
}
/*
1
.
2
..
..
3
...
.X.
...
4
....
.X..
.X..
.X..

4
....
.X..
....
..X.
5
.....
.X...
...X.
..X..
.....
5
.....
.XX..
...X.
..X..
.....
*/