EK算法封装版

师兄的模板，盗用一下，哈哈哈

//Edmonds_Karp算法
//此版本保护原始容量，但要消耗更多内存flow, 时间复杂度不变
//邻接矩阵
//#include <iostream>
//#include <queue>
//#include <algorithm>
//#define maxn 210
//
//using namespace std;
//const int inf = 0x3f3f3f3f;
//
//struct EK {
// int cap[maxn][maxn];
// int flow[maxn][maxn];
// int n;
// void init(int n) {
//  this->n = n;
//  memset(cap, 0, sizeof(cap));
// }
// void addCap(int i, int j, int val) {
//  cap[i][j] += val;
// }
// int solve(int source, int sink) {
//  if(source == sink) 
//   return inf;///源=汇, 流量无穷大！
//  static int que[maxn], pre[maxn], d[maxn];
//  ///bfs时的队列; bfs时某点的前驱; 增光路径的流量
//  int p, q, t;///bfs时的队列底、顶; bfs时当前元素
//  memset(flow, 0, sizeof(flow));
//  while(true) {
//   memset(pre, 255, sizeof(pre));
//   d[source] = inf;
//   p = q = 0;
//   que[q ++] = source;
//
//   while(p<q && pre[sink]==-1) {
//    t = que[p ++];
//    for(int i = 0; i < n; i ++) {
//     if(pre[i]==-1 && cap[t][i]-flow[t][i]>0) {
//      ///残余=cap-flow
//      pre[i] = t;
//      que[q++]=i;
//      d[i] = min(d[t], cap[t][i]-flow[t][i]);
//     }
//    }
//   }
//   if(pre[sink]==-1) break;///没有增广路径了！
//   for(int i = sink; i != source; i = pre[i]) {
//    flow[pre[i]][i] += d[sink];
//    flow[i][pre[i]] -= d[sink];
//   }
//  }
//  t = 0;///当做网络流量
//  for(int i = 0; i < n; i ++)
//   t += flow[source][i];
//  return t;
// }
//};

//邻接表
#include <iostream>
#define th(x) this->x = x
using namespace std;

const int maxn = 1005;
const int maxm = 100005;
const int inf = 0x7fffffff;

struct Nod {
 int b, next;
 int cap, flow;
 void init(int b, int cap, int next) {
  th(b); th(cap); th(next);
 }
};

struct SAP {
 int E[maxn], n;
 int h[maxn], vh[maxn], source, sink;
 Nod buf[maxm]; int len; //资源所在
 void init(int n) {
  this->n = n;
  len = 0;
  memset(E, 255, sizeof(E));
 }
 void addCap(int i, int j, int cap1, int cap2 = 0) {
  buf[len].init(j, cap1, E[i]);
  E[i] = len++;
  buf[len].init(i, cap2, E[j]);
  E[j] = len++;
 }

 int sap(const int idx, const int maxCap) {
  if(idx == sink)
   return maxCap;
  int l = maxCap, d, minH = n;
  for(int i = E[idx]; i != -1; i = buf[i].next) {
   Nod & nod = buf[i];
   if(nod.cap-nod.flow > 0) {
    if(h[idx]==h[nod.b]+1) {
     d = sap(nod.b, min(l, nod.cap-nod.flow));
     nod.flow += d;
     buf[i ^ 1].flow -= d;//i^1是i的伙伴
     l -= d;
     if(h[source]==n||l==0) return maxCap-l;
    }
    minH=min(minH, h[nod.b]+1);
   }
  }
  if(l == maxCap) {
   vh[h[idx]] --;
   vh[minH] ++;
   if(vh[h[idx]] == 0)
    h[source] = n;
   h[idx] = minH;
  }
  return maxCap - l;
 }

 int solve(int source, int sink) {
  if(source == sink) return inf;
  th(source); th(sink);
  memset(h, 0, sizeof(h));
  memset(vh, 0, sizeof(vh));
  for(int i = 0; i < len; i ++) buf[i].flow = 0;
  int ans = 0;
  while(h[source] != n)
   ans += sap(source, inf);
  return ans;
 }
};

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358879

原文：http://8590696.blog.51cto.com/8580696/1358879