首页 / 算法 / 网络流最经典的入门题 各种网络算法都能AC。

网络流最经典的入门题 各种网络算法都能AC。

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了网络流最经典的入门题 各种网络算法都能AC。，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2745字，纯文字阅读大概需要4分钟。

内容图文

Drainage Ditches

 

题目抽象：给你m条边u,v,c。   n个定点，源点1，汇点n.求最大流。  最好的入门题，各种算法都可以拿来练习

（1）：  一般增广路算法  ford()

              1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <string>
  7 #include <vector>
  8 #include <set>
  9 #include <map>
 10 #include <stack>
 11 #include <queue>
 12 #include <sstream>
 13 #include <iomanip>
 14usingnamespace std;
 15 typedef longlong LL;
 16constint INF = 0x4fffffff;
 17constdouble EXP = 1e-5;
 18constint MS = 10005;
 19constint SIZE = 10005;
 20 21struct edge
 22{
 23int c, f;
 24}edges[MS][MS];
 25 26int n, m;
 27 28int flag[MS];
 29int pre[MS];
 30int alpha[MS];
 31 32int que[SIZE];
 33 34int u;
 35int qs, qe;
 36int i, j;
 37 38void ford()
 39{
 40while (1)
 41    {
 42//  label method 43         memset(flag, 0xff, sizeof(flag));
 44         memset(pre, 0xff, sizeof(pre));
 45         memset(alpha, 0xff, sizeof(alpha));
 46         flag[1] = 0;
 47         pre[1] = 0;
 48         alpha[1] = INF;
 49         qs = qe = 0;
 50         que[qe++] = 1;
 51 52while (qs < qe&&flag[n ] == -1)
 53        {
 54             u = que[qs++];
 55for (int i = 1; i <= n; i++)
 56            {
 57if (flag[i] == -1)
 58                {
 59if (edges[u][i].c >0&&edges[u][i].f < edges[u][i].c)
 60                    {
 61                         flag[i] = 0; pre[i] = u;
 62                         alpha[i] = min(alpha[u], edges[u][i].c - edges[u][i].f);
 63                         que[qe++] = i;
 64                    }
 65elseif (edges[i][u].c>0&&edges[i][u].f>0)
 66                    {
 67                         flag[i] = 0; pre[i] = -u;
 68                         alpha[i] = min(alpha[u], edges[i][u].f);
 69                         que[qe++] = i;
 70                    }
 71                }
 72            }
 73             flag[u] = 1;
 74         }    //  END OF WHILE 75if (flag[n ] == -1 || alpha[n ] == 0)
 76break;       //  END OF WHILE 77 78int k1 = n , k2 = abs(pre[k1]);
 79int a = alpha[n ];
 80while (1)
 81        {
 82if (edges[k2][k1].c>0)         //用f是否==INF来判断正向 83                 edges[k2][k1].f += a;
 84else 85                 edges[k1][k2].f -= a;
 86if (k2 == 1)
 87break;
 88             k1 = k2;
 89             k2 = abs(pre[k1]);
 90         }     //  END OF WHILE 91     }  //  END OF WHILE 92 93int max_flow = 0;
 94for (int i = 1; i <=n; i++)
 95    {
 96for (int j = 1; j <=n; j++)
 97        {
 98if (i == 1 && edges[i][j].f >0)
 99                 max_flow += edges[i][j].f;
100//  if (edges[i][j].f > 0)
101//     printf("%d-->%d: %d\n", i, j, edges[i][j].f);102        }
103    }
104     printf("%d\n", max_flow);
105}
106107int main()
108{
109int u, v, c, f;
110while(scanf("%d%d",&m,&n)!=EOF)
111    {
112for (int i = 0; i <= n; i++)
113for (int j = 0; j <= n; j++)
114// edges[i][j].c = edges[i][j].f = INF;115                  edges[i][j].c=edges[i][j].f=0;
116for (int i = 0; i < m; i++)
117          {
118//scanf("%d%d%d%d", &u, &v, &c, &f);119               scanf("%d%d%d",&u,&v,&c);         //   这里是零流120               edges[u][v].c +=c;                           //  可能有重边
121// edges[u][v].f = f;122          }
123          ford();
124    }
125return0;
126 }

 

原文：http://www.cnblogs.com/767355675hutaishi/p/4423447.html

内容总结

以上是互联网集市为您收集整理的网络流最经典的入门题 各种网络算法都能AC。全部内容，希望文章能够帮你解决网络流最经典的入门题 各种网络算法都能AC。所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1101757.html

来源：【匿名】