Posted on 2012-05-01 18:02
lenohoo 閱讀(131)
評論(0) 編輯 收藏 引用
在網(wǎng)絡(luò)中，若每條邊【
vi，vj】除容量c
ij外,還給一個數(shù)
aij，表示從
vi到
vj運輸單位物資所需支付的費用,則問題便是尋找一個可行流{
fij},其流值為給定的數(shù)值
r*,并使總費用取最小值。這樣的可行流稱為最小費用流。最小費用流問題可用對應(yīng)于線性規(guī)劃的原始算法和對偶算法求解。例如,若對偶算法是：從各邊流
fij=0和流值
r=0的最小費用流開始,如果
r<
r*，則采用以費用作邊長求最短路徑的方法尋找關(guān)于{fij}的增廣鏈，把{fij}調(diào)整為流值r′(r<r′≤r*)的最小費用流，直到流值為r*為止。
MCF
#define re(i,n) for(int i=0;i<n;i++)
#define MAXN 1001
#define MAXM 40010
#define inf (1<<29)
int N,M,pre[MAXM],first[MAXN],dist[MAXN];
bool vi[MAXN];
struct Edge{
int u,v,f,c,next;
}e[MAXM];
inline void _add(int u,int v,int f,int c){
e[M].u=u;e[M].v=v;e[M].f=f;e[M].c=c;
e[M].next=first[u];first[u]=M++;
}
inline void add(int u,int v,int f,int c){
_add(u,v,f,c);_add(v,u,0,-c);
}
inline bool spfa(int s,int t){
queue<int> Q;
re(i,N) dist[i]=inf,vi[i]=0,pre[i]=-1;
dist[s]=0;vi[s]=1;Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();vi[u]=0;
for(int i=first[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(e[i].f && dist[u]+e[i].c<dist[v]){
dist[v]=dist[u]+e[i].c;
pre[v]=i;
if(!vi[v]) { Q.push(v);vi[v]=1; }
}
}
}
return dist[t]!=inf;
}
int MCF(int s,int t){
int sum=0;
N+=2;
while(spfa(s,t)) {
sum+=dist[t];
int delta=inf;
for(int i=pre[t];i!=-1;i=pre[e[i].u])
delta=min(delta,e[i].f);
for(int i=pre[t];i!=-1;i=pre[e[i].u]) //easy wrong
e[i].f-=delta,e[i^1].f+=delta;
}
return sum;
}