这题的大意是有N个店主，有M个供应商，对于N个店主，每个主有一定的需求量（对应着K种商品），M个供应商也对应着一定的供应量。然后相应的供应是有一定的费用。最后问说是否能满足需求，不满足的话输出-1，满足的话输出最小的费用。模型是比较裸，这里对于每个商品，都建个图来费用流，相应的建个超级源点和超级汇点。每次spfa去找，复杂度是O(V*E*E)。
感谢：
http://www.cppblog.com/Icyflame/archive/2009/06/30/88891.html
代码 #include < iostream > #include < vector > #include < queue > using namespace std; const int MAX = 55 ; const int INF = INT_MAX; int N, M, K; int need[MAX][MAX]; int give[MAX][MAX]; int move[MAX][MAX][MAX]; int SS, TT; int mm[ 2 * MAX][ 2 * MAX]; // flow map int cc[ 2 * MAX][ 2 * MAX]; // cost map int prev[ 2 * MAX]; int flow[ 2 * MAX]; int dis[ 2 * MAX]; int in [ 2 * MAX]; void ready(){ for ( int i = 1 ; i <= N; i ++ ) for ( int j = 1 ; j <= K; j ++ ) scanf( " %d " , & need[i][j]); for ( int i = 1 ; i <= M; i ++ ) for ( int j = 1 ; j <= K; j ++ ) scanf( " %d " , & give[i][j]); for ( int k = 1 ; k <= K; k ++ ) for ( int i = 1 ; i <= N; i ++ ) for ( int j = 1 ; j <= M; j ++ ) scanf( " %d " , & move[k][i][j]);} void makeMap( int kind){ SS = 0 , TT = N + M + 1 ; // make the flow map memset(mm, 0 , sizeof (mm)); for ( int i = 1 ; i <= N; i ++ ) mm[SS][i] = need[i][kind]; for ( int i = 1 ; i <= M; i ++ ) mm[i + N][TT] = give[i][kind]; for ( int i = 1 ; i <= N; i ++ ) for ( int j = 1 ; j <= M; j ++ ) mm[i][j + N] = need[i][kind]; // make the cost map memset(cc, 0 , sizeof (cc)); for ( int i = 1 ; i <= N; i ++ ) for ( int j = 1 ; j <= M; j ++ ) { cc[i][j + N] = move[kind][i][j]; cc[j + N][i] = - move[kind][i][j]; }} int spfa(){ memset( in , 0 , sizeof ( in )); memset(dis, - 1 , sizeof (dis)); memset(prev, - 1 , sizeof (prev)); memset(flow, 0 , sizeof (flow)); in [SS] = 1 , dis[SS] = 0 , flow[SS] = INF; vector < int > v; v.push_back(SS); for ( int i = 0 ; i < v.size(); i ++ ) { int u = v[i]; in [u] = 0 ; for ( int j = SS; j <= TT; j ++ ) { if (mm[u][j] > 0 && (dis[j] == - 1 || dis[u] + cc[u][j] < dis[j])) { dis[j] = dis[u] + cc[u][j]; // in[j] = 1; prev[j] = u; flow[j] = min(flow[u], mm[u][j]); if ( in [j] == 0 ) in [j] = 1 , v.push_back(j); } } } return flow[TT];} int mcmf(){ int res = 0 ; while ( 1 ) { int now = spfa(); if (now == 0 ) break ; int u = TT; while (u != SS) { int v = prev[u]; mm[v][u] -= now; mm[u][v] += now; res += now * cc[v][u]; u = v; } } for ( int i = 1 ; i <= N; i ++ ) { if (mm[SS][i] > 0 ) return - 1 ; } return res;} int main(){ while (scanf( " %d%d%d " , & N, & M, & K), N) { int res = 0 ; ready(); for ( int k = 1 ; k <= K; k ++ ) { makeMap(k); int t = mcmf(); if (t == - 1 ) { res = - 1 ; break ; } res += t; } printf( " %d\n " , res); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/08/08/1795277.html
相关资源：数据结构—成绩单生成器