网络流EK算法数据结构：队列主要操作:广搜 记录路径 更新能解决的问题：最大流（最小割）复杂度：O(MV)v指最大容量，M指边数。新名词：    1.增广路：从源点source到tink的一条简单路，如果路上的每条边（u，v）的可改进量均大于0，则称这条路为一条增广路。    增广路定理：网络达到最大流量当且仅当不存在增广路。    增广路算法：从一个可行流开始不断的寻找可增广路，然后沿着它增广，直到它不存在。    2.反向弧：如果有一条弧(u,v),那么再进行网络流算法时，要对它建立反向弧(v,u),反向弧的容量为0，与正向弧相反，正向弧减少容量时，反向弧增加容量。建立反向弧能更多的增广，使网络流算法正确。（无法给出证明）    3.可行弧：在EK算法中指可从u到v增加流量（也就是容量不为0）。    4.可行路：从源点source到tink的有可行弧构成的路径叫做可行路。    具体操作：    1.建立网络（正向弧+反向弧）    2.从源点出发，广搜一条最短可行路（即最先到达汇点tink的那条路），每次到达一个点用pre数组记录是由那条边过来的（为后面减小流量做准备）    3.到达汇点tink时，按照pre数组记录的，从可行路中找一条容量最小的进行容量减少。即找到了一条割边。    4.重复操作2.3，直到无法到达汇点，算法结束，即找到了最大流，算法结束。推荐水题：USACO 4.2.1 纯网络流算法，可用来试EK的正确性，但EK只能拿50分！

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6   7 #define INF 1000000    8   9 struct    Edge 10 { 11     int x,y,flow,next,op;//flow表示当前边的容量  op表示正向弧所对应的反向弧在边表中的位置 12 }; 13  14 Edge map[200]; 15 int que[20000]; 16 bool b[500];//用b数组记录是否入队，可以防止重复入队，因为有反向弧和环！！ 17 int source,tink,n,m,tot,ans,head,tail; 18 int first[500]; 19 int pre[500]; 20  21 int fmin(int x ,int y) 22 { 23     if (x
         
          0) 70         { 71             int y=map[t].y;             72             if (map[t].flow>0    &&    b[y]==false)//找到一条可行弧 73             {                 74                 tail++; 75                 que[tail]=y; 76                 b[y]=true; 77                 pre[y]=t;//路径记录 78                 if (y==tink)    return true;//到达汇点，退出广搜 79             } 80             t=map[t].next; 81         } 82         head++; 83         b[x]=false; 84     }     85     return false; 86 } 87  88 void updata() 89 {     90     int Min=INF; 91     for (int p=pre[tink];p!=-1;p=pre[map[p].x])     92     { 93         Min=fmin(Min , map[p].flow);//找可行路中的最小容量 94     } 95     for (int p=pre[tink];p!=-1;p=pre[map[p].x])//更新容量过程     96     { 97         map[p].flow-=Min; 98         map[map[p].op].flow+=Min;//反向弧增加容量 99     }100     ans+=Min;    101 }102 103 void EK()104 {105     106     while (Bfs()==true)107     {108         updata();    109     }110     printf("%d\n",ans);    111 }112 113 int main()114 {115     freopen("ditch.in","r",stdin);116     freopen("ditch.out","w",stdout);117     init();118     EK();    119     return 0;    120     fclose(stdin); fclose(stdout);121 }