网络流——最大流-Dinic算法

  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 ++]= v;
 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 }

Dinic 1

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

Dinic 2