关于最大流和可行流
  • 板块学术版
  • 楼主冷笑叹秋萧
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/7/13 20:16
  • 上次更新2023/11/4 14:53:22
查看原帖
关于最大流和可行流
37885
冷笑叹秋萧楼主2021/7/13 20:16

比如下面代码,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];
        }
    }
}
2021/7/13 20:16
加载中...