关于网络流算法(2)

了解最大流解法：

网络流的相关基础知识很容易获得，详细的有《算导》，简单的有刘汝佳《算法竞赛入门》，这里选用的也是刘的书从Page207开始的内容。

这里要补充一些值得注意的基础：

最大流问题中的三个约束条件：容量限制条件、斜对成性条件、流量平衡条件；
网络流问题中边（Edge）的有向性。

1.1 BFS 算法

因为《算法竞赛入门》中的E-K算法是基于BFS遍历方法的，说是很容易找到让DFS很慢的例子所以改为BFS，自己又已经把以前看的书全部忘记了，无奈只能开这个1.1，非常惭愧。

BFS，Broad First Search，广度优先搜索算法，或，层序遍历算法。算法的理解部分只需要记住一句话：依次访问已经访问过的顶点的未访问临接顶点。、

实现层面，由于对于节点的遍历是顺序的、FIFO的，所以使用队列辅助进行顺序控制。

用邻接矩阵实现的BFS算法代码如下：

 1 void bfs(int s, bool edge[][maxn])
 2 {
 3     visit(s,visited);
 4     q.push(s);
 5     while(!q.empty()) 
 6     {
 7         s = q.front();
 8         q.pop();
 9         for(int w = next_Neighbor(s,0,edge);w>=0;w=next_Neighbor(s,w,edge))
10         {
11             if(!visited[w])
12             {
13                 visit(w,visited);
14                 q.push(w);
15             }            
16         }
17     }
18 }

1.2 Edmonds-Karp 算法（增广路算法）

E-K算法是最基础的最大流算法，主要思想是从最小流状态迭代增加流量，直到不能继续增加达到稳态。

其中迭代的过程称为“增广”，即对于某个s到t的流量通路，如果其上各边流量都没有达到各自的容量（流量上限），那么就在这条通路上增加这些边中的最小残量单位的流量。

E-K算法涉及到一个反向更新流量的问题，需要在代码中自己体会。

这里我贴个随笔，觉得写得很接地气。这篇文章中关于反向边权值的表达是“退回”，这个在《算法竞赛入门》也有部分表述，可以结合在一起看，另外补充一个比较全面的教程。

使用邻接矩阵实现的代码如下：

 1 /*
 2 不断寻找残量网络中汇点的可达路径，
 3 可达路径中的各条边每次迭代减少可达路径中所有边 capacity 最小值直到在残量网络中汇点不可达 
 4 */
 5 
 6 #include<iostream>
 7 #include<queue>
 8 using namespace std;
 9 const int arrsize = 10;
10 const int maxdata = INT_MAX;
11 
12 int cap[arrsize][arrsize];        //表示两个结点之间的最大可用流量 
13 int flow[arrsize],pre[arrsize];    //表示从原点到index结点的当前剩余可用流量 
14 queue<int> q;
15 
16 
17 int BFS(int src, int des)
18 //BFS函数，寻找可行通路 
19 {
20 //cout<<endl<<"进入BFS"<<endl; 
21     while(!q.empty())
22         q.pop();
23     
24     memset(pre,-1,sizeof(pre));
25     
26     pre[src] = 0;
27     flow[src] = maxdata;
28     
29     q.push(src);
30     while(!q.empty())
31     {
32         int index = q.front();
33         q.pop();
34         
35         if(index == des)
36             break;    
37         //层序寻找下一个可行通路
38         for(int i=0;i<arrsize;i++)
39         {
40             if(i!=src && cap[index][i]>0 && pre[i]==-1)
41             {
42                 pre[i]=index;                            //  保存当前结点的父结点 
43                 flow[i]=min(cap[index][i],flow[index]);    //★更新从源结点到当前结点的当前剩余可用流量 
44                 q.push(i);
45             }
46         }
47     }
48     if(pre[des]==-1)
49         return -1;
50     else
51         return flow[des];
52 }
53 
54 int maxFlow(int src, int des)
55 //s最大流函数，迭代残量网络 
56 {
57     int increasement,sumfolw = 0;
58     while((increasement = BFS(src,des)) != -1)
59     {        
60         int cur = des;
61         while(cur != src)
62         {
63             int last = pre[cur];
64             cap[last][cur] -= increasement;
65             cap[cur][last] += increasement;
66             cur=last; 
67         }
68         sumfolw += increasement;
69     }
70     return sumfolw;
71 }
72 
73 
74 
75 int main()
76 {
77     freopen("C:\Users\lenovo\Desktop\工作\华为挑战赛\数据_E-K.txt","r",stdin);
78     
79     for(short i=0;i<arrsize;i++)
80     for(short j=0;j<arrsize;j++)
81         cin>>cap[i][j];
82     
83     //打印邻接矩阵 
84     cout<<"邻接矩阵(有向图)为："<<endl;
85     for(short i=0;i<arrsize;i++)
86     for(short j=0;j<arrsize;j++)
87     {
88         cout<<cap[i][j]<<" ";
89         if(j==arrsize-1)
90             cout<<endl;
91     }
92     cout<<endl;
93     
94     memset(flow,0,sizeof(flow)); 
95     cout<<"最大流为："<<maxFlow(0,3)<<endl<<endl;
96 
97     fclose(stdin);
98 }

View Code: Edmonds-Karp

1.3 Bellman-Ford / SPFA 算法

由于在费用流中可能出现的负费用情况，必须考虑对含有负权边的有向图进行寻路的算法，一般采用Dijikstra或者Bellman-Ford算法，在这里也补充讨论下Bellman-Ford算法（下称B-F算法）。

基本的算法理解这篇文章对B-F算法介绍得已经很详细，另外《算导》Page379有更详细的证明可以参考。在刘汝佳的《算法竞赛入门》中有进阶的算法实现，即使用FIFO队列辅助剪枝（或SPFA），这个方法在这篇文章中解释得很详细。这里附上两段自己实现的代码。

 1 /*
 2 B-F算法是一个有固定迭代次数的寻路算法，在 m*n 次试探迭代中寻找更短路径（即寻找 A+B<C ）
 3 这个算得特点是可以判断负环路，因为算法的收敛过程是定长的，所以在完成迭代部分后很方便找到图中的负环而不会陷入其中。 
 4 */
 5 
 6 #include<iostream>  
 7 #include<cstdio>  
 8 using namespace std;
 9 const int arrsize=100;
10 const int maxnum=INT_MAX;
11 
12 typedef struct Edge
13 {
14     int u,v;
15     int evalue;
16 }Edge;
17 
18 Edge edge[arrsize];
19 int dist[arrsize],pre[arrsize];
20 
21 bool bellmanFord(int src, int dist[], int nodenum, int edgenum, Edge edge[])
22 {
23     for(int i=1; i<=nodenum; i++)
24         dist[i]=maxnum;
25     dist[src]=0;
26     
27     for(int i=1; i<=nodenum-1; i++)
28     for(int j=1; j<=edgenum; j++)
29     {
30         if(dist[edge[j].v] > dist[edge[j].u] + edge[j].evalue)
31         {
32             dist[edge[j].v] = dist[edge[j].u] + edge[j].evalue;
33             pre[edge[j].v] = edge[j].u;
34         }
35     }    
36     
37     for(int i=1;i<=edgenum;i++)
38     {
39         if(dist[edge[i].v] > dist[edge[i].u] + edge[i].evalue)
40             return false;
41         return true;
42     }
43 } 
44 
45 void printPath(int dest)
46 {
47     while(pre[dest]!=dest)
48     {
49         cout<<dest<<" -> ";
50         dest=pre[dest];
51     }
52     if(pre[dest]==dest)
53         cout<<dest;
54     cout<<endl<<endl;
55 }
56 
57 int main()
58 {
59     freopen("C:\Users\lenovo\Desktop\工作\华为挑战赛\数据_B-F.txt","r",stdin);
60 
61     int nodenum,edgenum,src;
62     
63     cin>>nodenum>>edgenum>>src;
64     for(int i=1; i<=edgenum; i++)
65         cin>>edge[i].u>>edge[i].v>>edge[i].evalue;
66     pre[src]=src;
67     
68     if(bellmanFord(src,dist,nodenum,edgenum,edge))
69     {
70         for(int i=1; i<=nodenum; i++)
71         {
72             cout<<"Distance of Node "<<i<<" : "<<dist[i]<<endl;
73             printPath(i);
74         }
75                     
76     }
77     
78     fclose(stdin);
79 }

View Code: Bellman-Ford 线性表边集

  1 /*
  2 模型理解： 
  3 B-F算法的进阶版本是使用一个FIFO队列维护最短路迭代过程，这样做的好处是可以屏蔽循环中的盲目试探：采用类似
  4 层序遍历的方法来试探更新最短路径，在这个过程中不会浪费资源考虑不在当前遍历层次上的结点（或者边），而这种
  5 遍历又可以保证对图搜索的完整性，每个结点都可以多次入队——这是根据当前遍历结点的出边来决定的。
  6 这个方法也被称为SPFA算法。 
  7 模型实现：
  8 数据结构上由于遍历需要，要新增 firstEdge数组、 inQueue数组、 inQueueTimes数组；
  9 判断负环的依据是负环会被重复遍历，其上的结点将多次入队，当有结点的入队次数大于 vertexNum-1（已经试探图中
 10 所有其他结点与之相连的边）则该结点一定存在于一个负环之中。 
 11 */
 12 
 13 #include<iostream>
 14 #include<queue>
 15 using namespace std;
 16 const int arrsize=100;
 17 const int INF=INT_MAX;
 18 
 19 typedef struct Edge
 20 {
 21     int u,v;
 22     int weight;
 23     int cost;
 24     int nextEdgeID;
 25 }Edge;
 26 
 27 Edge edge[arrsize];
 28 int firstEdge[arrsize];        //保存结点的第一出边 
 29 int pre[arrsize],dist[arrsize];
 30 bool inQueue[arrsize];        //记录结点的是否已经入队 
 31 int inQueueTimes[arrsize];    //记录结点的已经入队次数 
 32 queue<int> q;
 33 int vertexNum,edgeNum,src;
 34 
 35 bool bellmanFord(int src, int vertexNum, int edgeNum, Edge edge[], int dist[],bool inQueue[], int inQueueTimes[])
 36 {
 37     for(int i=1; i<=vertexNum; i++)
 38         dist[i]=INF;
 39     dist[src]=0;
 40     
 41     memset(inQueue,false,sizeof(inQueue));
 42     memset(inQueueTimes,0,sizeof(inQueueTimes));
 43     
 44     memset(pre,-1,sizeof(pre));
 45     pre[src]=src;
 46         
 47     
 48     while(!q.empty())
 49         q.pop();
 50     q.push(src);
 51     inQueueTimes[src]++;
 52     if( inQueueTimes[src]>vertexNum )
 53         return false;
 54     
 55     while(!q.empty())
 56     {
 57         int cur=q.front();
 58         q.pop();
 59         inQueue[cur]=false;
 60         
 61         for(int e=firstEdge[cur]; e!=-1; e=edge[e].nextEdgeID)
 62         if( dist[edge[e].v] > dist[cur] + edge[e].weight )
 63         {
 64             dist[edge[e].v] = dist[cur] + edge[e].weight;
 65             pre[edge[e].v]=cur;
 66             if( !inQueue[edge[e].v] )
 67             {
 68                 q.push(edge[e].v);
 69                 inQueueTimes[edge[e].v]++;
 70                 if( inQueueTimes[edge[e].v]>vertexNum )
 71                     return false;
 72                 inQueue[edge[e].v]=true;
 73             }
 74         }
 75     }
 76     return true;
 77 }
 78 
 79 void printPath(int vertex)
 80 {
 81     while(pre[vertex]!=vertex)
 82     {
 83         cout<<vertex<<" -> ";
 84         vertex=pre[vertex];
 85     }
 86     if( pre[vertex]==vertex )
 87         cout<<vertex;
 88     cout<<endl<<endl;
 89 }
 90 
 91 int main()
 92 {
 93     freopen("C:\Users\lenovo\Desktop\工作\华为挑战赛\数据_最小费用最大流.txt","r",stdin);
 94     
 95     cin>>vertexNum>>edgeNum>>src;
 96     
 97     //初始化edge数组 
 98     for(int i=1; i<=edgeNum; i++)
 99         cin>>edge[i].u>>edge[i].v>>edge[i].weight>>edge[i].cost>>edge[i].nextEdgeID;
100     
101     //初始化 firstEdge 数组 
102     memset(firstEdge,-1,sizeof(firstEdge));
103     for(int i=1; i<=edgeNum; i++)
104     {
105         if( firstEdge[edge[i].u] == -1 )
106             firstEdge[edge[i].u] = i;
107     }
108     
109     //运行 B-F算法 并输出结果 
110     if( bellmanFord(src, vertexNum, edgeNum, edge, dist, inQueue, inQueueTimes) )
111     {
112         for(int i=1; i<=vertexNum; i++)
113         {
114             cout<<"Distance of Node "<<i<<" : "<<dist[i]<<endl;
115             printPath(i);
116         }
117     }
118         
119     fclose(stdin);
120 }

View Code： B-F_FIFO/SPFA

1.4 MCMF算法

算法思想简单说就是在证明了最小费用最大流路径是由残量网络中费用最小的残量路径增广而来的基础上，使用 Dijikstra / Bellman-Ford / SPFA 算法查找最小路，并用 Edmonds-Karp 算法中的增广方法更新网络。

同学 netcan 大神推荐了一些很有效的模板，非常感激。