ZOJ 1994 Budget (staus 1st,happy~)

ZOJ 1994 Budget

这个题同时也还是POJ上的2396，经典的有上下界的可行流，我的模板已经经过好几个网络流题目的考验了，这道题排到zoj的第一版，实在是激动啊。刚开始我还想着是对于矩阵中的每一个格子都建立一个点，但是看过别人的建图，发现这个可以省略成行到列的弧。把每个行看成一个点，每个列也看成一个点，行到列的弧就可以看成是对应格子的流量。源点S到行点的弧容量上下界都是行的和（题目中给出），列点到汇T的容量同样是列的和，T到S再建立[0,inf]的弧，那么就可以用无源汇的可行流解决了。。

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
const int MAX = 200 + 20 + 4 + 1 ;
const int inf = 19901226;
using namespace std;

class Arc{
public:
    int to,w;
    int l,r;
    Arc *next,*anti;
    Arc *ass( int tt,int ll,int rr,Arc *&b ){
        to = tt; l = ll; r = rr;
        w = r - l;next = b; b = this; return this;
    }
};
int mat[ 201 ][ 21 ][ 2 ];

    int d[ MAX ],S,T,countt,N,M,bound;
    int in[ MAX ],out[ MAX ];
    Arc a[ MAX * 100 ],*biao[ MAX ];
    
    
    void init(int n){
        bound = n;//最多的点数。。。 
        for( int i = 1; i <= bound; i++ )
            biao[i] = NULL;
        memset( in, 0, sizeof(in) );
        memset( out,0,sizeof(out) );
        countt = 0;
    }
    
    void add( int from,int to, int l,int r ){
        Arc *p1 = a[ countt++ ].ass( to, l, r, biao[from] );
        Arc *p2 = a[ countt++ ].ass( from, 0, 0, biao[to] );
        p1->anti = p2;
        p2->anti = p1;
    }
    
    int bfs( void ){
        queue<int> q;
        fill( d, d+MAX, -1);
        d[ S ] = 0;
        q.push( S );
        while( !q.empty() ){
            int u = q.front();q.pop();
            for( Arc *p = biao[u]; p != NULL; p = p->next )
                if( d[ p->to ] == -1 && p->w > 0 )
                    d[ p->to] = d[u] + 1,q.push( p->to );
        }
        return d[ T ] != -1;
    }
    
    int dinic( int u,int sum ){
        int f,o = sum;
        if( u == T ) return sum;
        for( Arc *p = biao[u]; p != NULL&&sum; p = p->next )
            if( d[ p->to ] == d[u] + 1 && p->w > 0 ){
                f = dinic( p->to, min( p->w,sum));
                p->w -= f;
                p->anti->w += f;
                sum -= f;
            }
        return o-sum;
    }
    
    int maxflow( int s,int t ){
        S = s;T = t;
        int total = 0;
        while( bfs() )
            total += dinic( S, inf );
        return total;
    }

int max_flow(int s,int t){S=s;T=t;
    	int i,now_flow,total,min_dist;
    	Arc *ge[MAX],*di[MAX],*path[MAX];
    	int dist[MAX],countdist[MAX],his[MAX],pre[MAX],n=bound;
    	Arc *p,*locate;
    	bool flag;
    	memset( dist,0,sizeof(dist) );
    	memset( countdist,0,sizeof( countdist) );
    	countdist[0] = n;
    	for( i = 0; i <= n ; i++ ) di[i] = ge[i] = biao[i];
    	for( total = 0, now_flow = inf,i = S; dist[i] < n; ){
    		his[i] = now_flow;
    		for( flag = false,p=di[i]; p!=NULL; p= p->next){
    			if( p->w > 0 && dist[i] ==dist[p->to] + 1 ){
    				now_flow = min( now_flow,p->w );
    				pre[ p->to ] = i;
    				path[ p->to ] = p;
    				di[i] = p;
    				i = p->to;
    				if( i == T ){
    					for( total += now_flow; i != S; i = pre[i] )
    						path[i]->w -= now_flow, path[i]->anti->w += now_flow;
    					now_flow = inf;
    				}
    				flag = true;
    				break;
    			}
    		}
    		if( !flag ){
    			for( min_dist = n-1,p=ge[i];p!= NULL;p=p->next )
    				if( p->w > 0 && dist[p->to] < min_dist )
    					min_dist = dist[p->to],locate = p;
    			di[i] = locate;
    			if( !(--countdist[ dist[i] ] ) ) break;
    			countdist[ dist[i] = min_dist+1 ] ++;
    			if( i != S )
    				i = pre[i],now_flow = his[i];
    			
    		}
    	}
    	return total;
    }

    void construct( void ){
        for( int i = 1; i <= bound - 2; i++ )
            for( Arc *p = biao[i]; p != NULL; p = p->next ){
                if( !p->l && !p->r ) continue;
                in[ p->to ] += p->l;
                out[ i ] += p->l;
            }
        for( int i = 1; i <= bound - 2; i++ ){
            if( in[i] > out[i] )
                add( bound - 1, i, 0, in[i] - out[i] );
            if( in[i] < out[i] )
                add( i, bound, 0, out[i] - in[i]);
        }
    }
    
    bool full( void ){
        for( Arc *p = biao[bound-1]; p != NULL; p = p->next )
            if( p->w ) return false;
        return true;
    }

int ROW( int i ){ return i;}
int COL( int i ) { return N+i;}
void FU( int r,int c,char ch,int l ){
    if( ch == '<' )
        mat[r][1] = min( mat[r][1], l-1 );
    else if( ch == '>' )
        mat[r][0] = max( mat[r][0], l+1 );
    else if( ch == '=' ){
        mat[r][1] = min( mat[r][1], l );
        mat[r][0] = max( mat[r][0], l );
    }
}
int main(void){
    int cases,outstart;
    int i,j,k,t,c,r,l,to,from;
    scanf("%d",&cases);
    while( cases-- ){
        
        scanf("%d%d",&N,&M);
        for( i = 1; i <= N; i++ )
            for( j = 1; j <= M; j++ ){ 
                mat[i][j][0] = 0;
                mat[i][j][1] = inf;
            }
        S = N + M + 1;
        T = N + M + 2;
        
        init( N + M + 4 );
        
        for( i = 1; i <= N; i++ ){
            scanf("%d",&t );
            add( S, ROW(i), t, t );
        }
        
        for( i = 1; i <= M; i++ ){
            scanf("%d",&t );
            add( COL(i), T, t, t );
        }
        
        scanf("%d",&c);
        while( c-- ){
            int col,row,limit;
            char temp[ 5 ];
            scanf("%d%d%s%d",&row,&col,temp,&limit);
            if( row == 0 && col == 0 ){
                for( i = 1; i <= N; i++ )
                    for( j = 1; j <= M; j++ )
                        FU( i, j, temp[0], limit );
                continue;
            }
            if( row == 0 ){
                for( i = 1; i <= N; i++ )
                    FU( i, col, temp[0], limit );
                continue;
            }
            if( col == 0 ){
                for( i = 1; i <= M; i++ )
                    FU( row, i, temp[0], limit );
                continue;
            }
            FU( row, col, temp[0], limit );
        }
        outstart = countt;
        for( i = 1; i <= N; i++ )
            for( j = 1; j <= M; j++ )
                add( ROW(i), COL(j), mat[i][j][0], mat[i][j][1] );
        
        add( T, S, 0, inf );
        
        construct();
        
        max_flow(S+2,T+2);
        
        if( !full() ){
            puts( "IMPOSSIBLE" );if( cases ) puts( "" );continue;
        }
        
        for( i = 1; i <= N; i++ ){
            for( j = 1; j <= M; j++ ){
                if( j != 1 ) putchar(' ');
                printf("%d",a[outstart].r - a[outstart].w);
                outstart += 2;
            }
            puts( "" );
        }
        
        if( cases ) puts( "" );
    }
    return 0;
}