初识网络流（EK and Dinic 模板） - Linux安全网 - Linux操作系统_Linux 命令_Linux教程

初识网络流（EK and Dinic 模板）

日期:2011-08-14 点击:26 来源: 未知分享至:

昨天由08的学长讲解了网络流的入门，加上自己之前看过算法导论里面的介绍，有了一点点粗浅的认识！学长给的话里最后一段我感觉很有意义！贴出来看看：

• 今天介绍的只是网络流中最基本一些问题，真正网络流博大精深，是研究生的一本必修课程。北邮的戴牛曾说过一切问题皆网络流，可见它的易用性。本人在有限的ACM生涯中也只是粗略入了门而已，大家练习做这种类型题目切忌百度，网络问题精华就在构图，图出来，什么都是浮云，如果一没思路马上百度，是无法入门，更别谈小成。受益匪浅啊！今天做最大流的问题，就遇到了建图苦难这个难题！认识了Dinic和EK两种算法！算是勉强会用,主要是学长留下的模板好用。贴出来大家分享一下先是EK的！

View Code

 1 int M,N;
 2 int map[NN][NN];
 3 int mark[NN];
 4 int pre[NN];
 5 bool Bfs()
 6 {
 7     int que[NN];
 8     memset(mark,0,sizeof(mark));
 9     mark[0]=1;
10     que[0]=0;
11     int cur,i;
12     int j,num=1;
13     for (j=0;j<num;j++) 
14     {
15         cur=que[j];
16         for(i=0;i<=N+1;i++)    //N+1 的位置代表总得点得个数
17             if(map[cur][i]>0&&!mark[i])
18             {
19                 mark[i]=1;
20                 pre[i]=cur; 
21                 if (i==N+1)   //走到最后了  返回1
22                     return true;
23                 que[num++]=i;
24             }
25     }
26     return false;
27 }
28 void Edmonds_Karp()
29 {
30     int maxFlow=0;
31     int flow,tmp;
32     while(Bfs())
33

Tags：

分享至: