Poj Solution 2516

http://poj.org/problem?id=2516

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef int type;
const type MAX_FEE = 1e8;
const int size = 210;
const int MAX = 1e8;
struct edge
{
    int c,f;
    type w;
    int from,to;
    int rev_i;
};
vector<edge> e[size];
type dis[size], fee, sum, rest;
bool sign[size];
edge *from[size];
int n, s, t;
int maxflow, add;
void clear()
{
    int i;
    for( i=0; i<n; i++ )
        e[i].clear();
    rest = 0;
}
bool dijstra( )
{
    int i, j, k, to, v;
    for( i=0; i<n; i++ )
        dis[i] = 999999;
    memset( sign, 0, sizeof(bool)*n );
    memset( from, 0, sizeof(edge * )*n );
    dis[ s ] = 0;
    for( i=0; i<n; i++ )
    {
        k = -1;
        for( j=0; j<n; j++ )
            if( !sign[j] && dis[j] < 999999 && ( k < 0 || dis[k] > dis[j] ) )
                k = j;
        if( k == -1 )
            break;
        sign[ k ] = true;
        for( j=0; j<e[k].size(); j++ )
        if( e[k][j].f != e[k][j].c )
        {    
            to = e[k][j].to;
            if( !sign[to] && e[k][j].f != e[k][j].c && dis[ to ] > ( v = dis[ k ] + e[k][j].w ) )
            {
                if( e[k][j].w < 0 )
                    while( printf( "ft" ) );

                dis[ to ] = v;
                from[ to ] = &e[k][j];
            }
        }
    }
    return sign[t] == true;
}
void increse( edge *ep, int d )
{
    ep->f += d;
    e[ep->to][ep->rev_i].f -= d;
}
void modify( )
{
    int i, j, temp;
    add = MAX; sum = 0;
    for( i=t; i!=s; i = from[i]->from )
    {
        sum += from[i]->w;
        if( ( temp = from[i]->c - from[i]->f ) < add )
            add = temp;
    }
    sum += rest;
    rest += dis[t];
    
    for( i=t; i!=s; i = from[i]->from )
        increse( from[i], add );

    for( i=0; i<n; i++ )
    for( j=0; j<e[i].size(); j++ )
        e[i][j].w = dis[i] - dis[ e[i][j].to ] + e[i][j].w;

    return;
}
void insert_edge( int from, int to, int c, type w )
{
    edge eg1 = { c, 0, w, from, to, e[to].size() }, eg2 = { 0, 0, -w, to, from, e[from].size() };
    e[from].push_back( eg1 );
    e[to].push_back( eg2 );
}
type min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

    fee = 0; maxflow = 0;
    n = nodenum, s = begin, t = end;    
    while( dijstra( ) )
    {
        modify( );
        fee += sum*add;
        maxflow += add;
    }    
    if( flow )
        *flow = maxflow;

    return fee;
}
int shop[50][50];
int t_s[50], t_n[50];
int need[50][50];
int main()
{
    int n, m, k, i, j, l, f, ans;
    bool key;
    while( 1 )
    {
        scanf( "%d %d %d", &n, &m, &k );
        if( n == 0 ) break;
        for( i=0; i<k; i++ )
            t_s[i] = t_n[i] = 0;
        for( i=0; i<n; i++ )
        for( j=0; j<k; j++ )
        {
            scanf( "%d", &need[i][j] );
            t_n[j] += need[i][j];
        }
        for( i=0; i<m; i++ )
        for( j=0; j<k; j++ )
        {
            scanf( "%d", &shop[i][j] );
            t_s[j] += shop[i][j];
        }        
        for( i=0; i<k; i++ )
            if( t_s[i] < t_n[i] )
                break;
        if( i < k ) key = false;
        else key = true;
        ans = 0;
        for( l=0; l<k; l++ )
        {
            clear();
            if( key )
            {
                for( i=0; i<m; i++ )
                if( shop[i][l] )insert_edge( 0, i+2, shop[i][l], 0 );
        
                for( i=0; i<n; i++ )
                if( need[i][l] )insert_edge( i+2+m, 1, need[i][l], 0 );
            }
            for( i=0; i<n; i++ )
            for( j=0; j<m; j++ )
            {
                scanf( "%d", &f );
                if( key )
                    insert_edge( j+2, i+2+m, 10000, f );
            }
            if( key )
                ans += min_fee_max_flow( n+m+2, 0, 1, 0 );
        }
        if( key )
            printf( "%dn", ans );
        else
            printf( "-1n" );
    }
    return 0;
}