[关闭]
@rg070836rg 2015-12-28T12:35:36.000000Z 字数 4940 阅读 1404

算法概论实验十二

算法概论实验

  1. 实验十二
  3. 实验目的与要求：
  4. （1） 理解与掌握求解最大流与最小割的基本算法。
  5. （2） 学会应用最大流与最小割算法解决实际问题。
  7. 1．实现Ford-Fulkerson算法，求出给定图中从源点s到汇点t的最大流，并输出最小割。
  9. 2. 设计与实现二部图匹配（Bipartite Matching）问题的算法。

1．Ford-Fulkerson算法

  1. //void *memset(void *s,int c,size_t n)将已开辟内存空间 s 的首 n 个字节的值设为值 c
  2. //#include <Ford_Fulkerson>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <list>
  6. #include <queue>
  7. #include <iostream>
  8. using namespace std;
  10. #define INFI 1000
  11. typedef struct _mark
  12. {
  13.     int pre_suc;
  14.     int max_incr;
  15. }MARK;
  17. int iteration = 0;//增光路径数目
  18. const int N = 100;
  19. list<int> setS;
  20. bool isMark[N], isCheck[N], isDone;
  21. MARK markList[N];
  22. int c[N][N], f[N][N];
  23. int n; //顶点数
  26. int Maxflow()
  27. {
  28.     int flow = 0;
  29.     for (int i = 0; i<n; i++)
  30.     {
  31.         flow += f[0][i];
  32.     }
  33.     return flow;
  34. }
  35. void Mincut()//isMark的点就是最小割
  36. {
  37.     int i = 0;
  38.     while (i<n)
  39.     {
  40.         if (isMark[i])
  41.             setS.push_back(i);
  42.         i++;
  43.     }
  44. }
  45. int IncrFlowAuxi(int index)//计算增广路径中的最大可增量
  46. {
  47.     if (index == 0)
  48.         return markList[index].max_incr;
  50.     int prev = markList[index].pre_suc;
  51.     int maxIncr = markList[index].max_incr;
  52.     return min(maxIncr, IncrFlowAuxi(prev));//递归求瓶颈值为最大增量
  53. }
  54. void IncrFlow()//增广路径的增加
  55. {
  56.     iteration++;
  57.     int incr = IncrFlowAuxi(n - 1); //最大可增量
  58.     int index = n - 1;
  59.     int prev;
  60.     while (index != 0)
  61.     {
  62.         prev = markList[index].pre_suc;
  63.         f[prev][index] += incr; //增广路径增加后，相应的流量进行更新
  64.         index = prev;
  65.     }
  66. }
  68. void Mark(int index, int pre_suc, int max_incr)//被标记表示可能被纳入新路径
  69. {
  70.     isMark[index] = true;
  72.     markList[index].pre_suc = pre_suc;//前驱
  73.     markList[index].max_incr = max_incr;//当前路径的流值
  74. }
  75. void Check(int i)//被mark且被check的点表示已经被纳入新路径
  76. {
  77.     isCheck[i] = true;
  79.     for (int j = 0; j<n; j++)
  80.     {
  81.         if (c[i][j]>0 && !isMark[j] && c[i][j]>f[i][j])//forward 边
  82.             Mark(j, i, min(markList[i].max_incr, c[i][j] - f[i][j]));
  83.         if (c[j][i]>0 && !isMark[j] && f[j][i]>0)//reverse 边
  84.             Mark(j, i, min(markList[i].max_incr, f[j][i]));
  85.     }
  86. }
  88. //ford_fulkerson算法
  89. int ford_fulkerson()
  90. {
  92.     int i;
  93.     while (1)//一次循环找到一个新路径
  94.     {
  96.         isDone = true;
  97.         i = 0;
  98.         while (i<n)//一次循环判断上次循环是否有找到新路径，若无则表明没有新路径，终止算法
  99.         {
  100.             if (isMark[i] && !isCheck[i])  //判断是否所有标记的点都已被检查：若是，结束整个算法
  101.             {
  102.                 isDone = false;
  103.                 break;
  104.             }
  105.             i++;
  106.         }
  108.         if (isDone) //算法结束，则计算最小割和最大流
  109.         {
  110.             Mincut();
  111.             return Maxflow();
  112.         }
  114.         while (i<n)//贪心法构建新路径
  115.         {
  116.             if (isMark[i] && !isCheck[i]) {
  117.                 Check(i);
  118.                 i = 0;
  119.             }
  120.             if (isMark[n - 1]) //如果汇t被标记，说明找到了一条增广路径，则增加该条路径的最大可增加量
  121.             {
  122.                 IncrFlow();
  123.                 memset(isMark + 1, false, n - 1); //增加该增广路径后，除了源s，其余标记抹去
  124.                 memset(isCheck, false, n);
  125.             }
  126.             else i++;
  127.         }
  128.     }
  129. }
  131. int main()
  132. {
  133.     /*
  134.     测试值：ppt上的例子
  135.     0  20 10 0
  136.     0  0  30 10
  137.     0  0  0  20
  138.     0  0  0  0
  139.     */
  140.     n = 4;
  141.     for (int k = 0; k < n; ++k)
  142.     {
  143.         memset(c[k], 0, sizeof(c[0][0])*n);
  144.         memset(f[k], 0, sizeof(f[0][0])*n);  //初始各分支流量为0
  145.         memset(isMark, false, n);
  146.         memset(isCheck, false, n);
  147.     }
  148.     isMark[0] = true; //给源做永久标记
  149.     markList[0].max_incr = INFI;
  150.     markList[0].pre_suc = INFI;
  152.     c[0][1] = 20;
  153.     c[0][2] = 10;
  154.     c[1][2] = 30;
  155.     c[1][3] = 10;
  156.     c[2][3] = 20;
  158.     cout << "最大流为：" << ford_fulkerson() << endl;
  159.     cout << "最大割的S集合为：{";
  160.     for (list<int>::iterator i = setS.begin(); i != setS.end(); i++)
  161.     {
  162.         printf("%d  ", *i);
  163.     }
  164.     cout << "}" << endl;
  165.     cout << "增广路径个数为：" << iteration << endl;
  166.     system("PAUSE");
  167. }

2. 二部图匹配

  1. //void *memset(void *s,int c,size_t n)将已开辟内存空间 s 的首 n 个字节的值设为值 c
  2. //#include <Ford_Fulkerson>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <list>
  6. #include <queue>
  7. #include <iostream>
  8. using namespace std;
  10. #define INFI 1000
  11. typedef struct _mark
  12. {
  13.     int pre_suc;
  14.     int max_incr;
  15. }MARK;
  17. int iteration = 0;//增光路径数目
  18. const int N = 100;
  19. list<int> setS;
  20. bool isMark[N], isCheck[N], isDone;
  21. MARK markList[N];
  22. int c[N][N], f[N][N];
  23. int n; //顶点数
  26. int Maxflow()
  27. {
  28.     int flow = 0;
  29.     for (int i = 0; i<n; i++)
  30.     {
  31.         flow += f[0][i];
  32.     }
  33.     return flow;
  34. }
  35. void Mincut()//isMark的点就是最小割
  36. {
  37.     int i = 0;
  38.     while (i<n)
  39.     {
  40.         if (isMark[i])
  41.             setS.push_back(i);
  42.         i++;
  43.     }
  44. }
  45. int IncrFlowAuxi(int index)//计算增广路径中的最大可增量
  46. {
  47.     if (index == 0)
  48.         return markList[index].max_incr;
  50.     int prev = markList[index].pre_suc;
  51.     int maxIncr = markList[index].max_incr;
  52.     return min(maxIncr, IncrFlowAuxi(prev));//递归求瓶颈值为最大增量
  53. }
  54. void IncrFlow()//增广路径的增加
  55. {
  56.     iteration++;
  57.     int incr = IncrFlowAuxi(n - 1); //最大可增量
  58.     int index = n - 1;
  59.     int prev;
  60.     while (index != 0)
  61.     {
  62.         if (index != n - 1)
  63.             cout << index << " ";
  64.         prev = markList[index].pre_suc;
  65.         f[prev][index] += incr; //增广路径增加后，相应的流量进行更新
  66.         index = prev;
  67.     }
  68.     cout << endl;
  69. }
  71. void Mark(int index, int pre_suc, int max_incr)//被标记表示可能被纳入新路径
  72. {
  73.     isMark[index] = true;
  75.     markList[index].pre_suc = pre_suc;//前驱
  76.     markList[index].max_incr = max_incr;//当前路径的流值
  77. }
  78. void Check(int i)//被mark且被check的点表示已经被纳入新路径
  79. {
  80.     isCheck[i] = true;
  82.     for (int j = 0; j<n; j++)
  83.     {
  84.         if (c[i][j]>0 && !isMark[j] && c[i][j]>f[i][j])//forward 边
  85.             Mark(j, i, min(markList[i].max_incr, c[i][j] - f[i][j]));
  86.         if (c[j][i]>0 && !isMark[j] && f[j][i]>0)//reverse 边
  87.             Mark(j, i, min(markList[i].max_incr, f[j][i]));
  88.     }
  89. }
  91. //ford_fulkerson算法
  92. int ford_fulkerson()
  93. {
  95.     int i;
  96.     while (1)//一次循环找到一个新路径
  97.     {
  99.         isDone = true;
  100.         i = 0;
  101.         while (i<n)//一次循环判断上次循环是否有找到新路径，若无则表明没有新路径，终止算法
  102.         {
  103.             if (isMark[i] && !isCheck[i])  //判断是否所有标记的点都已被检查：若是，结束整个算法
  104.             {
  105.                 isDone = false;
  106.                 break;
  107.             }
  108.             i++;
  109.         }
  111.         if (isDone) //算法结束，则计算最小割和最大流
  112.         {
  113.             Mincut();
  114.             return Maxflow();
  115.         }
  117.         while (i<n)//贪心法构建新路径
  118.         {
  119.             if (isMark[i] && !isCheck[i]) {
  120.                 Check(i);
  121.                 i = 0;
  122.             }
  123.             if (isMark[n - 1]) //如果汇t被标记，说明找到了一条增广路径，则增加该条路径的最大可增加量
  124.             {
  125.                 IncrFlow();
  126.                 memset(isMark + 1, false, n - 1); //增加该增广路径后，除了源s，其余标记抹去
  127.                 memset(isCheck, false, n);
  128.             }
  129.             else i++;
  130.         }
  131.     }
  132. }
  134. int main()
  135. {
  136.     //测试数据为ppt第40页的图，只实现了二部图的最大匹配
  137.     n = 12;
  138.     for (int k = 0; k < n; ++k)
  139.     {
  140.         memset(c[k], 0, sizeof(c[0][0])*n);
  141.         memset(f[k], 0, sizeof(f[0][0])*n);  //初始各分支流量为0
  142.         memset(isMark, false, n);
  143.         memset(isCheck, false, n);
  144.     }
  145.     isMark[0] = true; //给源做永久标记
  146.     markList[0].max_incr = INFI;
  147.     markList[0].pre_suc = INFI;
  149.     c[1][6] = INFI;
  150.     c[1][7] = INFI;
  151.     c[2][7] = INFI;
  152.     c[3][6] = INFI;
  153.     c[3][8] = INFI;
  154.     c[3][9] = INFI;
  155.     c[4][7] = INFI;
  156.     c[4][10] = INFI;
  157.     c[5][7] = INFI;
  158.     c[5][10] = INFI;
  160.     for (int i = 1; i < n / 2; i++)
  161.         c[0][i] = 1;
  162.     for (int i = n/2; i < n-1; i++)
  163.         c[i][n-1] = 1;
  165.     cout << "最大匹配结果为：" << endl;
  166.     int result= ford_fulkerson();
  167.     cout << "匹配边个数为：" << result << endl;
  168.     system("PAUSE");
  169. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注