比如下面代码,spfa()过程最后一行为什么我改成注释掉的代码来return就变成了最小费用最大流,用原来的就是最小费用可行流?(费用为非正数)
bool spfa()
{
memset(cost,inf,sizeof(cost));memset(flow,inf,sizeof(flow));memset(bz,0,sizeof(bz));
queue<int>q;q.push(0);bz[0]=1;nxt[en]=-1;cost[0]=0;
while (!q.empty())
{
int u=q.front();q.pop();bz[u]=0;
for (R i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if (e[i].f && cost[v]>cost[u]+e[i].c)
{
cost[v]=cost[u]+e[i].c;nxt[v]=u;last[v]=i;flow[v]=min(flow[u],e[i].f);
if (!bz[v]) q.push(v),bz[v]=1;
}
}
}
return cost[en]<=0;
//return nxt[en]!=-1
}
void solve()
{
while (spfa())
{
int now=en;ans+=flow[now]*cost[now];
while (now)
{
e[last[now]].f-=flow[en];e[last[now]^1].f+=flow[en];
now=nxt[now];
}
}
}