算法笔记之线性规划网络流问题(5)

最大收益问题

问题分析

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

算法设计

  1. 构建网络。根据输入的数据,添加源点和汇点,从源点s到每个实验项目Ei有一条有向边,容量是项目产生的收益pi。从每个实验仪器Ij到汇点t有一条有向边,容量是仪器费用cj,每个实验项目到该实验项目用到的仪器有一条有向边容量是
    ∞,创建混合网络。
  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<<"  ";
}

  1. 构建混合网络
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(V2E),其中V为结点个数,E为边的数量。

空间复杂度O(V)。

方格取数问题

问题简介

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

问题分析

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

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

算法设计

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

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

方格取数1

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

算法详解

假设整个图如下图所示。

方格取数1

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

方格取数3

  1. 在混合网络上用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。

方格取数4

切割线中被选中的就是红色圈圈的结点,选择的道路是从源点出发,按照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(V2E),其中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);
         }
    }
  1. 求网络最小费用最大流
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;
}
  1. 输出最优的旅游路线
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;
      }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注