最小费用最大流算法(二)
子的下标为mcase+j
G[mcase+j][vertex].c=G[mcase+j][vertex].c_f=1;//将从各个房子到超汇点之间的容量取为0，注意房子的下标为mcase+j
}
}
}
void SPFA(int s)//求最短路径的SPFA算法
{
queue Q;
int u;
for(int i=0; i<=vertex; i++)//初始化
{
dist[i]=MAX;
pre[i]=-1;
inq[i]=0;
}
dist[s]=0;
Q.push(s);
inq[s] = 1;
while(!Q.empty())
{
u=Q.front();
Q.pop();
inq[u]=0;
for(int i=0; i<=vertex; i++)//更新u的邻接点的dist[], pre[], inq[]
{
int v=i;
if(G[u][v].c_f==0) // 表示(u,v)没有边
continue;
if(G[u][v].v==MAX)
G[u][v].v=-G[v][u].v;
if(dist[v]>dist[u]+G[u][v].v)//松弛操作
{
dist[v]=dist[u]+G[u][v].v;
pre[v]=u;
if(inq[v]==0)
{
Q.push(v);
inq[v]=1;
}
}
}
}
}
void ford_fulkerson(int s,int t)
{
SPFA(s);
while(pre[t]!=-1)//pre为-1表示没有找到从s到t的增广路径
{
//cout<
sum+=dist[t];//将这一条最短路径的值加进sum
min_c_f=MAX;
int u=pre[t], v=t;//计算增广路径上的残留容量
while(u!=-1)
{
if(min_c_f > G[u][v].c_f)
min_c_f=G[u][v].c_f;
v=u;
u=pre[v];
}
u=pre[t], v=t;
while(u!=-1)
{
G[u][v].f+=min_c_f; //修改流
G[v][u].f=-G[u][v].f;
G[u][v].c_f=G[u][v].c-G[u][v].f; //修改残留容量
G[v][u].c_f=G[v][u].c-G[v][u].f;
v=u;
u=pre[v];
}
SPFA(s);
}
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
while(cin>>m>>n,m||n)
{
init();
ford_fulkerson(0,vertex);//计算从超源点0到超汇点vertex之间的最小费用最大流
cout<
}
return 0;
}