Edmonds-Karp

• 从零流开始不断增加流量，保持每次都满足容量限制，斜对称性，和容量平衡
• 具体来说就是从残存网路中用bfs每次找到一条路（即a[t]>0）后减去这条路上的最小残余容量，一直重复，直到找不到新的路（a[t]在这一次操作后仍为0）。

struct Edge {  //Edge结构体
	int from, to, cap, flow;//from为出点，to为入点，cap为容量，flow为流量
	Edge(int u, int v, int c, int f):from(u),to(v),cap(c),flow(f) {} //为了方便赋值入队
};

struct EdmondsKarp {
	int n,m;//n个点，m条初始边
	vector<Edge>edges;//边数的两倍
	vector<int>G[maxn];//邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
	int a[maxn];//当起点到i的可改进量（一条路一条路搜索）
	int p[maxn];//最短路树上的入弧编号，用来bfs后的路的搜索/输出

	void init(int n) { //init
		for(int i = 0; i < n; i++) G[i].clear();
		edges.clear();
	}
	void AddEdges(int from, int to, int cap) {
		edges.push_back(Edge(from, to ,cap, 0));//出
		edges.push_back(Edge(to, from, 0 , 0));//回
		m = edges.size();//大小（一直累计）
		G[from].push_back(m-2);//编号 0 ，2 ，4 ，。。。，2n-2
		G[to].push_back(m-1);//编号 1， 3， 5， 。。。2n-1
	}

	int Maxflow(int s, int t) {
		int flow;//用来记录流，以便于输出最大流
		for( ; ; ) {
			memset(a, 0, sizeof(a));//重新找一条路时应该被清零
			queue<int>Q;//队列，用于bfs，自动重置
			Q.push(s);//起点入队
			a[s] = INF;//设置起点到起点的可改进量为INF，以便于后续min的更新
			while(!Q.empty()) { //遍历，直到队列为空或者到终点一条未被找到的路被找到
				int x = Q.front();
				Q.pop();//常规操作
				for(int i = 0; i < G[x].size(); i++) { //遍历
					Edge& e = edges[G[x][i]];//直接引用
					if(!a[e.to] && e.cap > e.flow) { //下一点没被找到过并且满足容量大于流 这里无所谓正向弧和反向弧的问题，因为需要反向弧容量为0，可以反悔时流量为负
						p[e.to] = G[x][i];//记录下一点序号，以便于用edges[p[u]].from查出前一点
						a[e.to] = min(a[x], e.cap - e.flow);//更新改进量
						Q.push(e.to);//bfs常规
					}
				}
				if(a[t]) break;
			}
			if(!a[t]) break;
			for(int u = t; u != s; u = edges[p[u]].from) {
				edges[p[u]].flow += a[t];
				edges[p[u]^1].flow -= a[t];
			}
			flow += a[t];
		}
		return flow;
	}
};