1532 Drainage Ditches 超详解简单 EK算法经典模板最大流网络流基础.docVIP

下载本文档

0
0
约2.73千字
约 3页
2018-11-25 发布于河南
举报
版权申诉

1532 Drainage Ditches 超详解简单 EK算法经典模板最大流网络流基础.doc

1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
7、VIP文档为合作方或网友上传，每下载1次，网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

1532 Drainage Ditches 超详解简单 EK算法经典模板最大流网络流基础

Drainage Ditches 此题在hdu的1532题大致意思就是给m条边n个点，并给出其中有向边的最大流量，问终点最多可以得到多少来自起点的流量。这是最简单的最大流最小割问题，搞懂它，对于之后的学习是至关重要的，主要方法是EK（EK算法就是在福特福克森算法的基础上加上BFS），我把解释都放在每一句代码后面了，相信这样能更好的帮助你理解。。。 ? Sample Input 5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10 ? Sample Output 50 ? ? #include cstdlib#include queue#include iostream#include algorithmusing namespace std;const int MAXN=201;int c[MAXN][MAXN];int n;//下标从0开始int maxflow(int s,int t){??? int pre[MAXN];???????????? //用来存储某结点的前面的结点??? int i,u,v,flow=0,aug;??? while (true)??? {??????? queue int q;?????????????? //建立一个队列用来存储增广路径??????? memset(pre,-1,sizeof(pre));??????? q.push(s);??????? while (!q.empty())?????????? //由while来寻找一个增广路径，构成一个队列，从s到t??????? {//??????????? cout?? q.front() = q.front()?? q.back() = q.back()?? q.size() = q.size()endl;??????????? u=q.front();????????????????????????? //第一次把位于队头的（开始是s）给到u??????????? q.pop();??????????????????????????????? //之后叫位于队头的（开始是s）出队列??????????? for (v=0; vn pre[t]0 ;v++)// BFS遍历u的后继结点，遍历直到队尾或是遍历点数超过n个 ,对n个点同时有哪些信誉好的足球投注网站一步,构成一个树状，只有两层??????????? {??????????????? if (c[u][v]0 pre[v]0)????????? //如果到下一结点的正向边存在? 并且? 下一结点还没有被访问过??????????????? {??????????????????? pre[v]=u;???????????????????? //那么就叫下一个结点的‘父亲结点’为当前结点??????????????????? q.push(v);?????????????????? //并将下一个结点入队//??????????????????? cout?? q.front() = q.front()?? q.back() = q.back()?? q.size() = q.size()endl;?????????????????????????????????? }?????????????? }//??????????? for (v=0; vn ;v++)?????????//??????????? {//??????????????? cout?? pre[v] = pre[v];//??????????? }//??????????? coutendl;??????????? if (pre[t]=0)//??????????? {//?????????????????? cout当找到一条增广路径 break;endl;?????????????????? break;//当找到一条增广路径时跳出循环//??????????? }?????????????????? }??????? if (pre[t]0) break;//如果找不到可以从s到t的增广路径，结束查找??????????????? aug = INT_MAX;????? //令当前增广路径上最小的一段权值为aug，初始化为max??????????????? for (u=pre[v=t];v!=s;v=u,u=pre[u])??????? {??????????? if (c[u][v]aug) aug=c[u][v];????????? //从当前增广路径中找到最短的给到aug