轉(zhuǎn)載自這里
最小費用最大流
通過EK啸箫，Dinic提岔，ISAP算法可以得到網(wǎng)絡(luò)流圖中的最大流肛鹏，一個網(wǎng)絡(luò)流圖中最大流的流量max_flow是唯一的，但是達到最大流量max_flow時每條邊上的流量分配f是不唯一的荧呐。
如果給網(wǎng)絡(luò)流圖中的每條邊都設(shè)置一個費用cost，表示單位流量流經(jīng)該邊時會導(dǎo)致花費cost。那么在這些流量均為max_flow的流量分配f中，存在一個流量總花費最小的最大流方案亏吝。
即min{ sum( cost(i, j)*f(i,j) | (i, j) 屬于方案f中的邊， f(i,j)為 邊(i,j)上的流量盏混， f為某一個最大流方案}蔚鸥。此即為最小費用最大流。
算法思想
采用貪心的思想括饶，每次找到一條從源點到達匯點的路徑株茶，增加流量来涨，且該條路徑滿足使得增加的流量的花費最小图焰，直到無法找到一條從源點到達匯點的路徑，算法結(jié)束蹦掐。
由于最大流量有限技羔，每執(zhí)行一次循環(huán)流量都會增加，因此該算法肯定會結(jié)束卧抗，且同時流量也必定會達到網(wǎng)絡(luò)的最大流量藤滥；同時由于每次都是增加的最小的花費，即當(dāng)前的最小花費是所有到達當(dāng)前流量flow時的花費最小值社裆，因此最后的總花費最小拙绊。
求解步驟
（1）找到一條從源點到達匯點的“距離最短”的路徑，“距離”使用該路徑上的邊的單位費用之和來衡量泳秀。
（2）然后找出這條路徑上的邊的容量的最小值f标沪，則當(dāng)前最大流max_flow擴充f，同時當(dāng)前最小費用min_cost擴充 f*min_dist(s,t)嗜傅。
（3）將這條路徑上的每條正向邊的容量都減少f金句，每條反向邊的容量都增加f。
（4）重復(fù)（1）--（3）直到無法找到從源點到達匯點的路徑吕嘀。
需要注意幾點
1违寞、注意超級源點和超級終點的建立。
2偶房、初始化時趁曼，正向邊的單位流量費用為cost[u][v]，那么反向邊的單位流量費用就為-cost[u][v]棕洋。因為回流費用減少挡闰。
3、費用cost數(shù)組和容量cap數(shù)組每次都要初始化為0拍冠。
求解從源點到匯點的“最短”路徑時尿这，由于網(wǎng)絡(luò)中存在負權(quán)邊簇抵，因此使用SPFA來實現(xiàn)。
加上自己的一點見解:其實就是Edmonds_Karp算法中的BFS換成SPFA,同時邊上有單位流量流經(jīng)該邊時的花費cost射众。每次求出可行流時,當(dāng)前的最小費用就是最小距離*最大流流量碟摆。
A - Going Home
題意:
給出一個地圖，H代表房子叨橱，m代表人典蜕，兩者數(shù)量相等，人每移動一格花費1罗洗，每個房子只能住一個人,求所有人走到房子里所需要的最小花費愉舔。
題解:
很容易知道這是最優(yōu)匹配問題,所以可以像最大匹配那樣建圖:
超級源點連向人,容量為1,單位費用流為0;
房子連超級匯點,容量為1,單位費用流為0;
二分圖的邊容量也為1,單位費用流為房子和人的哈密頓距離;
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=250;
const int MAXE=21000;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,c,cost;
Node(){}
Node(int to,int next,int c,int cost):to(to),next(next),c(c),cost(cost){}
};
int head[MAXN],cnt;
Node edge[MAXE];
void addEdge(int u,int v,int c,int cost)
{
edge[cnt]=Node(v,head[u],c,cost);
head[u]=cnt++;
edge[cnt]=Node(u,head[v],0,-cost);
head[v]=cnt++;
}
int inque[MAXN],dis[MAXN],pre[MAXN];
bool BFS(int st,int ed,int &cost)
{
queue<int> que;
que.push(st);
memset(inque,0,sizeof(inque));
memset(dis,INF,sizeof(dis));
dis[st]=0;
pre[st]=pre[ed]=-1;
int u,v;
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(edge[i].c>0&&dis[v]>dis[u]+edge[i].cost)
{
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if(inque[v]==0)
{
inque[v]=1;
que.push(v);
}
}
}
}
if(pre[ed]==-1) return false;
int flow=INF;
for(int i=pre[ed];i!=-1;i=pre[edge[i^1].to])
{
flow=min(flow,edge[i].c);
}
for(int i=pre[ed];i!=-1;i=pre[edge[i^1].to])
{
edge[i].c-=flow;
edge[i^1].c+=flow;
}
cost+=dis[ed]*flow;//累加最小費用
return true;
}
struct Object
{
int x,y;
Object(int x=0,int y=0):x(x),y(y){}
};
Object man[110],house[110];
int mcnt,hcnt;
char graph[110][110];
int main()
{
int n,m,cost,st,ed;
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
memset(head,-1,sizeof(head));
cost=cnt=mcnt=hcnt=0;
for(int i=1;i<=n;i++)
{
scanf("%s",graph[i]+1);
for(int j=1;j<=m;j++)
{
if(graph[i][j]=='m')
{
man[++mcnt]=Object(i,j);
}
else if(graph[i][j]=='H')
{
house[++hcnt]=Object(i,j);
}
}
}
st=0;ed=mcnt*2+1;
for(int i=1;i<=mcnt;i++)
{
addEdge(st,i,1,0);
for(int j=1;j<=hcnt;j++)
{
addEdge(i,mcnt+j,1,abs(man[i].x-house[j].x)+abs(man[i].y-house[j].y));
}
}
for(int i=1;i<=hcnt;i++)
{
addEdge(i+mcnt,ed,1,0);
}
while(BFS(st,ed,cost));
printf("%d\n",cost);
}
}
