Minimum Cost-最小费用最大流
update@2011-09-19
///主要代码
#define MAX 60
#define INF 10000000
int need[MAX][MAX];//某个shopkeeper需要的
int supply[MAX][MAX];//某个供货点各商品的存储量
int cost[MAX][MAX][MAX];//cost[k][i][j] 从j运送第k种商品到j
int graph[MAX*3+1][MAX*2+1];
int head[MAX*3+1],count;
int pre_of[MAX*3+1];// edge(pre_of[i],i)
int N,M,K;
struct node{
int u,v,w,next;
}edge[MAX*MAX*10];
void add(int u,int v,int w){
edge[count].u = u;edge[count].v = v;edge[count].w = w;
edge[count].next = head[u];head[u] = count++;
}
int dist[MAX*2+1];
int SPFA(int k,int source,int sink){
for(int i = source; i <= sink;i++){
dist[i] = INF;
}dist[source] = 0;
memset(pre_of,-1,sizeof(pre_of));
bool in_queue[MAX*2+1] = {};//初始化为不在队列中
queue<int> my;my.push(source); in_queue[source] = true;
while(!my.empty()){
int start = my.front(); my.pop(); in_queue[start] = false;
for(int i = head[start]; i!= -1;i = edge[i].next){
int u = edge[i].u, v = edge[i].v ,w = edge[i].w;
if(graph[u][v] > 0 && dist[v] > dist[u] + w){
//printf("relax %d %d\n",u,v);
dist[v] = dist[u] + w; pre_of[v] = u;
if(!in_queue[v]){
in_queue[v] = true;my.push(v);
}
}
}
}
return dist[sink] < INF;
}
bool isOk(int sink){
int s = M+1;//每个商店
for(int i = s;i < sink;i++){
if(graph[i][sink] != 0)return false;
}
return true;
}
int minCost_maxFlow(int kind,int source,int sink){
//把每条边的费用权值作为边长
//每次求最短增广路径进行增流 直到找不到增广路径
int sum = 0;
while(SPFA(kind,source,sink)){
//增流
int min_flow = INF;
for(int i = sink;i != source;i = pre_of[i]){
if(graph[pre_of[i]][i] < min_flow)
min_flow = graph[pre_of[i]][i];
}
sum += dist[sink]*min_flow;
for(int i = sink; i != source;i = pre_of[i]){
int u = pre_of[i], v = i;
graph[u][v] -= min_flow;
graph[v][u] += min_flow;
}
}
if(!isOk(sink))return -1;
return sum;
}
int main(){
while(scanf("%d%d%d",&N,&M,&K) && N != 0){
///init
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",&supply[i][j]);
}
for(int k = 1;k <= K;k++){//第i种商品
for(int i = 1;i <= N;i++){
for(int j = 1;j <= M;j++){
scanf("%d",&cost[k][i][j]);//j供应给i
}
}
}
int total = 0;bool flag = true;
for(int k = 1;k <= K && flag;k++){//第i种商品
//供应商是 1 到 m,之后是m+1到m+n
count = 0;memset(head,-1,sizeof(head));memset(graph,0,sizeof(graph));
for(int i = 1;i <= M;i++){//供应商
for(int j = 1;j <= N;j++){//商店
graph[i][j+M] = INF;
add(i,j+M,cost[k][j][i]);
add(j+M,i,-cost[k][j][i]);
}
}
int source = 0,sink = M+N+1;
for(int t = 1;t <= M;t++){
graph[source][t] = supply[t][k];//从源点到某个供货点的流量表示供应
add(source,t,0);//从源点到每个供应点的距离
}
for(int t = 1;t <= N;t++){
graph[t+M][sink] = need[t][k];//第t个shopkeeper被供应的总量
add(t+M,sink,0);//从每个商店到汇点
}
int t = minCost_maxFlow(k,source,sink);
if(t == -1){printf("-1\n");flag = false;}
else total += t;
}
if(flag)printf("%d\n",total);
}
return 0;
}
题目链接:
Minimum Cost其实求最小费用最大流的思想很简单,就是每次选取最短增广路径(路径长度为单位流量的花费),然后计算这条路径中的最大可增的流量 进行增流.刚学SPFA所以就用SPFA写的,而且把费用图和流量图分开了。SPFA用的邻接表,所以加边的时候要加负边 否则不能回流。