## LUỒNG

# Edmonds Karp Max Flow

1.[Lưu lượng mạng](http://algobook.net/problem/63e66b7c3a9745d502cfb516)
<details>
<summary>Code</summary>

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=20;
const int M=1005;
int cnt;
int head[N],pre[N];
bool vis[N];
struct Edge{
   int v,next;
   int cap,flow;
}E[M<<1];

void init(){
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,int c){
    E[cnt].v=v;
    E[cnt].cap=c;
    E[cnt].flow=0;
    E[cnt].next=head[u];
    head[u]=cnt++;
}

bool bfs(int s,int t){
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=E[i].next){
        	int v=E[i].v;
        	if(!vis[v]&&E[i].cap>E[i].flow){
                vis[v]=1;
                pre[v]=i;//chỉ số cạnh 
				q.push(v);
				if(v==t)  return 1;
    //tìm một con đường tăng cường
			}	
		}
    }
    return 0;
}

int EK(int s,int t){
    int maxflow=0;
    while(bfs(s,t)){
    	int v=t,d=inf;
    	while(v!=s){//tìm số gia tăng
            int i=pre[v];
			d=min(d,E[i].cap-E[i].flow);
			v=E[i^1].v;
        }
		maxflow+=d;
		v=t;
        while(v!=s){//Luồng tăng cường dọc theo các đường dẫn có thể tăng cường
            int i=pre[v];
			E[i].flow+=d;
			E[i^1].flow-=d;
			v=E[i^1].v;
        }
    }
    return maxflow;
}

int main(){
    int T,n,m,u,v,w,cas=1;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=m;i++){
	        scanf("%d%d%d",&u,&v,&w);
	        add(u,v,w);
			add(v,u,0);
    	}
    	printf("Case %d: %d\n",cas++,EK(1,n));
	}
    return 0;
}

</details>

<br />

2.[Rãnh Thoát Nước](http://algobook.net/problem/63e66b033a9745d502cfb50d)
<details>
<summary>Code</summary>

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=205;
const int M=205;
int cnt;
int head[N],pre[N];
bool vis[N];
struct Edge{
   int v,next;
   int cap,flow;
}E[M<<1];

void init(){
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,int c){
    E[cnt].v=v;
    E[cnt].cap=c;
    E[cnt].flow=0;
    E[cnt].next=head[u];
    head[u]=cnt++;
}

bool bfs(int s,int t){
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=E[i].next){
        	int v=E[i].v;
        	if(!vis[v]&&E[i].cap>E[i].flow){
                vis[v]=1;
                pre[v]=i;
				q.push(v);
				if(v==t)  return 1;//tìm một con đường tăng cường
			}	
		}
    }
    return 0;
}

int EK(int s,int t){
    int maxflow=0;
    while(bfs(s,t)){
    	int v=t,d=inf;
    	while(v!=s){
            int i=pre[v];
			d=min(d,E[i].cap-E[i].flow);
			v=E[i^1].v;
        }
		maxflow+=d;
		v=t;
        while(v!=s){
            int i=pre[v];
			E[i].flow+=d;
			E[i^1].flow-=d;
			v=E[i^1].v;
        }
    }
    return maxflow;
}

int main(){
    int n,m,u,v,w;
	while(~scanf("%d%d",&m,&n)){
		init();
		for(int i=1;i<=m;i++){
	        scanf("%d%d%d",&u,&v,&w);
	        add(u,v,w);
			add(v,u,0);
    	}
    	printf("%d\n",EK(1,n));
	}
    return 0;
}

</details>d