1 #include<algorithm>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 const int MAX_V= 510;
  6 const int MAX_E= 60000;
  7 const int INF= 0x3f3f3f3f;
  8 struct ENode
  9 {
 10     int to;
 11     int c;  //容量;
 12     int Next;
 13 };
 14 ENode edegs[MAX_E];
 15 int Head[MAX_V], tnt;
 16 void Add_ENode(int a, int b, int c)
 17 {
 18     /**建边*/
 19     edegs[++ tnt].to= b;
 20     edegs[tnt].c= c;
 21     edegs[tnt].Next= Head[a];
 22     Head[a]= tnt;
 23     edegs[++ tnt].to= a;
 24     edegs[tnt].c= 0;
 25     edegs[tnt].Next= Head[b];
 26     Head[b]= tnt;
 27 }
 28 void into()
 29 {
 30     /**初始化*/
 31     memset(Head, -1, sizeof(Head));
 32     tnt= -1;
 33 }
 34 
 35 int level[MAX_V];
 36 bool bfs_level (int s, int t)
 37 {
 38     memset(level, -1, sizeof(level)); //所有点的等级初始化为-1;
 39     level[s]= 1; //源点的等级为1;
 40     int que[MAX_V];  //队列que：按序保存已搜索到的点;
 41     int iq= 0;
 42     que[iq ++]= s; //先将源点s 加入队列;
 43     for (int i= 0; i<= iq; i ++)
 44     {
 45         int u= que[i];  //取出队首元素;
 46         if (u== t)
 47         {
 48             /*找到汇点t,返回*/
 49             return true;
 50         }
 51         for (int k= Head[u]; k!= -1; k= edegs[k].Next)
 52         {
 53             /*遍历，查找到之前未找到的、可抵达的点便加入队列*/
 54             int v= edegs[k].to;
 55             if (-1== level[v]&& edegs[k].c)
 56             {
 57                 level[v]= level[u]+ 1; //深度 +1;
 58                 que[iq ++]= edegs[k].to;
 59             }
 60         }
 61     }
 62     return false;
 63 }
 64 int dfs(int now, int c_max, int t)
 65 {
 66     /**DFS 实现多路增广*/
 67     /*now：起点；c_max：从源点s到节点now的最大流量；t：汇点、dfs结束的终点*/
 68     if (now== t) return c_max; //当now== t时，c_max便是要求的最大流;
 69     int ret= 0, f;
 70     for (int k= Head[now]; k!= -1; k= edegs[k].Next)
 71     {
 72         if (edegs[k].c&& level[edegs[k] .to]== level[now]+ 1)
 73         {
 74             /**/
 75             f= dfs(edegs[k].to, min(c_max- ret, edegs[k].c), t);
 76             edegs[k].c-= f;
 77             edegs[k^1].c+= f;
 78             ret+= f;
 79             if(ret== c_max) return ret;
 80         }
 81     }
 82     return ret;
 83 }
 84 int dinic(int s, int t)
 85 {
 86     int ans= 0;
 87     while(bfs_level(s, t))
 88     {
 89         ans+= dfs(s, INF, t);
 90     }
 91     return ans;
 92 }
 93 
 94 int main()
 95 {
 96     /*建图（记得into()初始化）*/
 97     int answer= dinic(s, t);
 98     /*输出结果*/
 99     return 0;
100 }

View Code