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;
}