算法笔记之线性规划网络流问题（5）

最大收益问题

问题分析

经过分析，又根据最大流最小割定理，最大流的流值等于最小割容量。即：实验方案净收益=所有实验项目收益-最大流值。所以只需要求出最大流值即可、

算法设计

1. 构建网络。根据输入的数据，添加源点和汇点，从源点s到每个实验项目E_i有一条有向边，容量是项目产生的收益p_i。从每个实验仪器I_j到汇点t有一条有向边，容量是仪器费用c_j，每个实验项目到该实验项目用到的仪器有一条有向边容量是
   ∞，创建混合网络。
2. 基于ISAP算法求网络最大流。
3. 输出最大收益及实验方案。最大收益实验方案就是最小割中的S集合去掉源点。在最大流对应的混合网络中，从选点开始，沿着cap>flow的边深度优先遍历，遍历到的结点就是S集合，即对应的实验项目和仪器就是选中的实验方案。

代码实现

1. 输出最大收益方案

void DFS(int s)//深度搜索最大获益方案
{
   for(int i=V[s].first;~i;i=E[i].next)//读当前结点的邻接表
       if(E[i].cap>E[i].flow)
       {
           int u=E[i].v;
           if(!flag[u])
           {
               flag[u]=true;
               DFS(u);
           }
       }
}
void print(int m,int n)//输出最佳方案
{
   cout<<"----------最大获益方案如下：----------"<<endl;
   DFS(0);
   cout<<"选中的实验编号："<<endl;
   for(int i=1;i<=m;i++)
       if(flag[i])
          cout<<i<<"  ";
   cout<<endl;
   cout<<"选中的仪器编号："<<endl;
   for(int i=m+1;i<=m+n;i++)
      if(flag[i])
          cout<<i-m<<"  ";
}

2. 构建混合网络

cout<<"请输入实验数m和仪器数n:"<<endl;
    cin>>m>>n;
    init();
    total=m+n;
    cout<<"请依次输入实验产生的效益和该实验需要的仪器编号(为0结束):"<<endl;
    for(int i=1;i<=m;i++)
    {
        cin>>cost;
        sum+=cost;
        add(0, i, cost);//源点到实验项目的边，容量为该项目效益
        while(cin>>num,num) //num为该项目需要的仪器编号
            add(i, m+num, INF);//实验项目到需要仪器的边，容量为无穷大
    }
    cout<<"请依次输入所有仪器的费用:"<<endl;
    for(int j=m+1;j<=total;j++)
    {
        cin>>cost;
        add(j, total+1, cost);//实验仪器到汇点的边，容量为实验仪器费用
    }

算法复杂度

时间复杂度：找到一条可增广路时间为O(V)，最多会执行O(VE)次，因为关键边的总数为O(VE)，因此总的时间复杂度为O(V²E)，其中V为结点个数，E为边的数量。

空间复杂度O(V)。

方格取数问题

问题简介

从一个矩阵中选取一些数，要求满足任意两个数不相邻，使这些数的和最大。实际上就是讲矩阵中的数分为两部分，对矩阵中的点进行黑白着色。

问题分析

黑色方格作为一个集合X，白色方格作为一个集合Y，可以将一个图分为两部分，构成一个二分图。添加源点和汇点，从源点向黑色方格连一条边，容量为该黑色方格的权值，从白色方格向汇点连一条边，容量为该白色方格的权值，对于每一对相邻的黑白方格，从黑方格向白方格连一条边，容量为无穷大。

同样是求出最小割，选中方格的最大权值=所有方格权值之和-最小割容量。

算法设计

1. 构建网络
2. 求网络最大流。
3. 输出选中物品的最大价值、物品选择方案。

选中物品的最大价值=所有物品价值之和-最大流值
注意：切割线切到的边容量是没选中的方格权值。

物品选择方案就是最小割中的S集合中的黑色方格和T集合中的白色方格。找到最小割后，从源点出发，沿着cap>flow的边DFS，遍历到的结点就是S集合，没有遍历到的结点就是T集合。输出S集合中的黑色方格和T集合中的白色方格。如上图所示。

算法详解

假设整个图如下图所示。

1. 构建网络，根据输入的数据，绘制二分图，添加源点s和汇点t，从黑方格向白方格连一条边，容量为∞，创建网络。

2. 在混合网络上用ISAP算法求网络最大流，找到如下6条增广路径。
   • 增广路径：10-6-9-0.增流5。
   • 增广路径：10-8-9-0.增流15。
   • 增广路径：10-4-7-0.增流34。
   • 增广路径：10-2-5-0.增流70。
   • 增广路径：10-2-3-0.增流21。
   • 增广路径：10-2-1-0.增流75。

切割线中被选中的就是红色圈圈的结点，选择的道路是从源点出发，按照cap>flow的结点（这里面只有7和9两个结点）去深度遍历，这就是S集合；1、3、5和2是T集合。
所以选中的黑点为7、9，白色为2。

代码实现

（1）构建网络

//创建混合网络
for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        if((i+j)%2==0)//染黑色
        {
            add(0,(i-1)*n+j,map[i][j]);//从源点到当前物品加边，容量为物品价值
            flag[(i-1)*n+j]=1;//染色
            //当前物品结点到四个相邻物品结点发出一条有向边，容量为无穷大
            for(int k=0;k<4;k++)
            {
                int x=i+dir[k][0];
                int y=j+dir[k][1];
                if(x<=m && x>0 && y<=n && y>0)
                    add((i-1)*n+j,(x-1)*n+y,INF);
            }
        }
        else
            //染白色，也就相当于flag为0，不需要专门的语句
        //从源点到当前物品加边，容量为物品价值
            add((i-1)*n+j,total+1,map[i][j]);
    }

（2）输出挑选物品的最大价值

cout<<"挑选物品的最大价值："<<sum-Isap(0,total+1,total+2)<<endl;

（3）输出选中的物品编号。

void DFS(int s)
{
    //读取当前结点的邻接表
    for(int i=V[s].first;~i;i=E[i].next)
    {
        if(E[i].cap>E[i].flow)
        {
            int u=E[i].v;
            if(!dfsflag[u])
            {
                dfsflag[u]=true;
                DFS(u);
            }
        }
    }
}
//输出最佳方案
void print(int m,int n)
{
    cout<<"-----最佳方案：-----"<<endl;
    cout<<"选中物品编号<<endl;
    DFS(0);
    for(int i=1;i<=m*n;i++)
        if(())
}

算法复杂度

时间复杂度：找到一条可增广路时间为O(V)，最多会执行O(VE)次，因为关键边的总数为O(VE)，因此总的时间复杂度为O(V²E)，其中V为结点个数，E为边的数量。

空间复杂度O(V)。

旅游路线问题

问题分析

给定一张地图，图中结点代表景点，边代表景点可以直达。现要求找到满足下面要求且途径景点最多的一条旅游线路：

1. 从最东端起点出发，从东往西经过若干个景点到达最西端的景点，然后再从西向东回到家（可途径若干景点）；
2. 除起点外，任何景点只能访问1次。

算法设计

1. 构建网络。根据输入的数据，按顺序对景点进行编号，即景点i对应结点i，对每个结点拆点，拆为两个结点i和i'，且从i到i'连接一条边，边容量为1，单位流量费用为0；源点和终点拆点时，边的容量为2，单位流量费用为0；如果景点i到景点j可以直达，则从结点i'到结点j连接一条边，边的容量为1，单位流量费用为-1，创建混合网络。
2. 求网络最小费用最大流。
3. 求出最优的旅游线路。从源点出发，沿着flow>0且cost≤0的方向深度优先遍历，到达终点后，再沿着flow＜0且cost≥0的方向深度优先遍历，返回源点。

代码实现

1. 构建网络

cout<<"请输入景点个数n和直达线路数m:"<<endl;
    cin>>n>>m;
    init();//初始化
    maze.clear();
    cout<<"请输入景点名str"<<endl;
    for(i=1;i<=n;i++)
    {
       cin>>str[i];
       maze[str[i]]=i;
       if(i==1||i==n)
         add(i,i+n,2,0);
       else
         add(i,i+n,1,0);
    }
    cout<<"请输入可以直达的两个景点名str1,str2"<<endl;
    for(i=1;i<=m;i++)
    {
        cin>>str1>>str2;
        int a=maze[str1],b=maze[str2];
        if(a<b)
        {
          if(a==1&&b==n)
            add(a+n,b,2,-1);
          else
            add(a+n,b,1,-1);
        }
        else
        {
           if(b==1&&a==n)
             add(b+n,a,2,-1);
           else
             add(b+n,a,1,-1);
         }
    }

2. 求网络最小费用最大流

bool SPFA(int s, int t, int n)//求最小费用路的SPFA
{
    int i, u, v;
    queue <int> qu; // 队列，STL实现
    memset(vis,0,sizeof(vis));//访问标记初始化
    memset(c,0,sizeof(c));   //入队次数初始化
    memset(pre,-1,sizeof(pre)); //前驱初始化
    for(i=1;i<=n;i++)
    {
        dist[i]=INF; //距离初始化
    }
    vis[s]=true; //结点入队vis要做标记
    c[s]++;     //要统计结点的入队次数
    dist[s]=0;
    qu.push(s);
    while(!qu.empty())
    {
        u=qu.front();
        qu.pop();
        vis[u]=false;
        //队头元素出队，并且消除标记
        for(i=V[u].first; i!=-1; i=E[i].next)//遍历结点u的邻接表
        {
            v=E[i].v;
            if(E[i].cap>E[i].flow && dist[v]>dist[u]+E[i].cost)//松弛操作
            {
                dist[v]=dist[u]+E[i].cost;
                pre[v]=i; //记录前驱
                if(!vis[v]) //结点v不在队内
                {
                    c[v]++;
                    qu.push(v);   //入队
                    vis[v]=true; //标记
                    if(c[v]>n) //超过入队上限，说明有负环
                        return false;
                }
            }
        }
    }
    cout<<"最短路数组"<<endl;
    cout<<"dist[ ]=";
    for(int i=1;i<=n;i++)
       cout<<"  "<<dist[i];
    cout<<endl;
    if(dist[t]==INF)
        return false; //如果距离为INF，说明无法到达，返回false
    return true;
}
int MCMF(int s,int t,int n) //minCostMaxFlow
{
    int d; //可增流量
    maxflow=mincost=0;//maxflow 当前最大流量，mincost当前最小费用
    while(SPFA(s,t,n))//表示找到了从s到t的最短路
    {
        d=INF;
        cout<<endl;
        cout<<"增广路径："<<t;
        for(int i=pre[t]; i!=-1; i=pre[E[i^1].v])
        {
            d=min(d, E[i].cap-E[i].flow); //找最小可增流量
            cout<<"--"<<E[i^1].v;
        }
        cout<<"增流："<<d<<endl;
        cout<<endl;
        for(int i=pre[t]; i!=-1; i=pre[E[i^1].v])//修改残余网络，增加增广路上相应弧的容量，并减少其反向边容量
        {
            E[i].flow+=d;
            E[i^1].flow-=d;
        }
        maxflow+=d; //更新最大流
        mincost+=dist[t]*d; //dist[t]为该路径上单位流量费用之和 ，最小费用更新
   }
   return maxflow;
}

3. 输出最优的旅游路线

void print(int s,int t)
{
    int v;
    vis[s]=1;
    for(int i=V[s].first;~i;i=E[i].next)
      if(!vis[v=E[i].v]&&((E[i].flow>0&&E[i].cost<=0)||(E[i].flow<0&&E[i].cost>=0)))
      {
         print(v,t);
         if(v<=t)
           cout<<str[v]<<endl;
      }
}