Dinic算法模板

详解：http://blog.****.net/wall_f/article/details/8207595

算法时间复杂度：O（E * V * V）

 #include <cstdio>
 #include <cstring>
 #include <queue>
 #include <vector>
 using namespace std;
 #define N 105
 #define M 1010
 #define INF 0x3f3f3f3f

 struct Edge {
     int u, v, cap;
     Edge () {}
     Edge (int u, int v, int cap) : u (u), v (v), cap (cap) {}
 }edge[N*N];
 vector<int> G[N];
 int S, T, cur[N], dis[N], tot;

 void Addedge(int u, int v, int cap) {
     G[u].push_back(tot);
     edge[tot++] = Edge(u, v, cap);
     G[v].push_back(tot);
     edge[tot++] = Edge(v, u, );
 }

 int BFS() { // 找层次图
     queue<int> que;
     while(!que.empty()) que.pop();
     memset(dis, INF, sizeof(dis));
     que.push(S);
     dis[S] = ;
     while(!que.empty()) {
         int u = que.front(); que.pop();
         for(int i = ; i < G[u].size(); i++) {
             Edge &e = edge[G[u][i]];
             if(dis[e.v] == INF && e.cap > ) {
                 dis[e.v] = dis[u] + ;
                 que.push(e.v);
             }
         }
     }
     return dis[T] != INF;
 }

 int DFS(int u, int maxflow) { // 找增广路
     if(u == T) return maxflow; //
     for(int i = cur[u]; i < G[u].size(); i++) {
         cur[u] = i;  // 当前弧优化
         Edge &e = edge[G[u][i]];
         if(dis[e.v] == dis[u] +  && e.cap > ) {
             int flow = DFS(e.v, min(e.cap, maxflow)); // 找到增广路上最小的流量增量
             if(flow) {
                 e.cap -= flow;
                 edge[G[u][i]^].cap += flow;
                 return flow;
             }
         }
     }
     return ; // 找不到增广路
 }

 int Dinic() {
     int ans = ;
     while(BFS()) {
         int flow;
         memset(cur, , sizeof(cur));
         while(flow = DFS(S, INF)) ans += flow;
     }
     return ans;
 }