题意：给出N的商店，M个仓库，K种物品，从这M个仓库给这N个商店供货，每条船有一定的载重量，商店和仓库间每一单元距离花费一定钱，求载货量最大而花费最小的情况。
思路：典型的最小费用最大流，虽然是第一次做这样的题，但在昨天好好又把求最大流的方法看了一遍，所以感觉做这题不是很难，但是题目中的输入很让人纠结，建图建了很久。
首先判断是否需求大于供应，如果是就直接输出-1，如果不是，直接用spfa求最小费用，将每种货物的最小花费加起来就是了。
代码：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <math.h> #define N 105 #define M 55 #define INF 100000000 using namespace std ; int cap[N][N] , cost[N][N] ; int n , m , k , s , e , sum ; int dis[N] , pre[N] , vist[N] ; int q[N] , top ; //通过一次BFS遍历找出费用最小一条路。 int spfa ( ) { int i , u , v ; for ( i = s ; i <= e ; i++ ) { dis[i] = INF ; vist[i] = 0 ; } top = 0 ; q[top++] = s ; vist[s] = 1 ; dis[s] = 0 ; pre[s] = 0 ; while ( top ) { u = q[--top] ; vist[u] = 0 ; for ( v = s ; v <= e ; v++ ) { if ( cap[u][v] > 0 && dis[v] > dis[u] + cost[u][v] ) { dis[v] = dis[u] + cost[u][v] ; pre[v] = u ; if ( !vist[v] ) { vist[v] = 1 ; q[top++] = v ; } } } } if ( dis[e] == INF ) return 0 ; return 1; } void cal () { int u ; int minn = INF ; //找出条路中最小的容量 for ( u = e ; u != s ; u = pre[u] ) { minn = minn < cap[pre[u]][u] ? minn : cap[pre[u]][u] ; } for ( u = e ; u != s; u = pre[u] ) { cap[pre[u]][u] -= minn ; cap[u][pre[u]] += minn ; sum += cost[pre[u]][u] * minn ; } } int main() { int need[N][N] , needx[N] , have[N][N] , havex[N] ; int i , j , c ; while ( scanf ( "%d%d%d" , &n , &m , &k ) != EOF ) { if ( n == 0 && m == 0 && k == 0 ) break; //n个商店要求的k中货物的总量 memset( needx , 0 , sizeof( needx )); for ( i = 1 ; i <= n ; i++ ) { for ( j = 1 ; j <= k ; j++ ) { scanf ( "%d" , &need[i][j] ); needx[j] += need[i][j] ; } } //m个仓库所存储的货物总量 memset( havex , 0 , sizeof( havex )); for ( i = 1 ; i <= m ; i++ ) { for ( j = 1 ; j <= k ; j++ ) { scanf ( "%d" , &have[i][j] ); havex[j] += have[i][j] ; } } //判断是否有货物的存储量小于需求量 int flag = 0 ; for ( i = 1 ; i <= k ; i++ ) if ( needx[i] > havex[i] ) { flag = 1 ;break; } s = 0 ;//超级源点 e = n + m + 1;//超级汇点 sum = 0; for ( c = 1 ; c <= k ; c++ ) { memset( cap , 0 , sizeof ( cap )); memset( cost , 0 , sizeof ( cost )); //输入仓库j到i的费用 for ( i = 1 ; i <= n ; i++ ) { for ( j = 1 ; j <= m ; j++ ) { scanf( "%d" , &cost[j][m+i] ); cost[m+i][j] = -cost[j][m+i] ; cap[j][m+i] = INF ; } } if ( flag ) continue ; //将所有仓库与超级源点相连。 for ( i = 1 ; i <= m ; i++ ) { cost[s][i] = cost[i][s] = 0 ; cap[s][i] = have[i][c] ; } //所有商店与超级汇点相连 for ( i = 1; i <= n ; i++ ) { cost[m+i][e] = cost[e][m+i] = 0 ; cap[m+i][e] = need[i][c] ; } //sum = 0 ; while ( spfa ()) cal(); } if ( flag ) printf ( "-1\n" ); else printf ( "%d\n" , sum ); } return 0 ; }