最大流模板

Isap模板：

const int maxn=100010;
const int maxm=400010;
struct Edge{
    int to,next,cap,flow;
    Edge(){};
    Edge(int _next,int _to,int _cap,int _flow){
        next=_next;to=_to;cap=_cap;flow=_flow;
    }
}edge[maxm];
int head[maxn],tol,gap[maxn],dep[maxn],cur[maxn];
void addedge(int u,int v,int flow){
    edge[tol]=Edge(head[u],v,flow,0);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0,0);head[v]=tol++;
}
int Q[maxn];
void bfs(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;int front=0,rear=0;
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;if(dep[v]==-1&&edge[i].cap)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
int S[maxn];
int sap(int start,int end,int N){
    bfs(start,end);
    memcpy(cur,head,sizeof(head));
    int top=0,u=start,ans=0;
    while(dep[start]<N){
        if(u==end){
            int MIN=INF,id;
            for(int i=0;i<top;i++)
                if(MIN>edge[S[i]].cap-edge[S[i]].flow)
                    MIN=edge[S[i]].cap-edge[S[i]].flow,id=i;
            for(int i=0;i<top;i++)
                edge[S[i]].flow+=MIN,edge[S[i]^1].flow-=MIN;
            ans+=MIN,top=id,u=edge[S[top]^1].to;
            continue;
        }
        bool flag=0;int v;
        for(int i=cur[u];i!=-1;i=edge[i].next){
            v=edge[i].to;
            if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
                flag=1;cur[u]=i;break;
            }
        }
        if(flag){
            S[top++]=cur[u];u=v;continue;
        }
        int MIN=N;
        for(int i=head[u];i!=-1;i=edge[i].next)
            if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<MIN)
                MIN=dep[edge[i].to],cur[u]=i;
        if(--gap[dep[u]]==0)break;gap[dep[u]=MIN+1]++;
        if(u!=start)u=edge[S[--top]^1].to;
    }
    return ans;
}

dinic模板：

const int maxn=1110;
const int maxm=400010;
struct Edge{
	int to,next,cap;
	Edge(){};
	Edge(int _next,int _to,int _cap){
		next=_next;to=_to;cap=_cap;
	}
}edge[maxm];
int head[maxn],tol,dep[maxn],cur[maxn],n;
void addedge(int u,int v,int flow){
	edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
	edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
int Q[maxn];
bool bfs(int start,int end){
	memset(dep,-1,sizeof(dep));
	int front=0,rear=0;
	dep[start]=0;Q[rear++]=start;
	while(front!=rear){
		int u=Q[front++];
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;if(dep[v]==-1&&edge[i].cap){
				Q[rear++]=v,dep[v]=dep[u]+1;
				if(v==end)return 1;
			}
		}
	}
	return 0;
}
int dinic(int s,int t){  
     int i,res=0,top;  
     int S[maxn],cur[maxn];  
     while(bfs(s,t)){  
          memcpy(cur,head,sizeof(head));  
          int u=s;top=0;  
          while(1){  
              if(u==t){  
                   int min=INF,loc;  
                   for(int i=0;i<top;i++)if(min>edge[S[i]].cap)  
		        	min=edge[S[i]].cap,loc=i;   
                  for(int i=0;i<top;i++)  
                   edge[S[i]].cap-=min,edge[S[i]^1].cap+=min, 
                    res+=min;top=loc;u=edge[S[top]^1].to;  
              }  
              for(int i=cur[u];i!=-1;cur[u]=i=edge[i].next)  
              if(edge[i].cap&&dep[u]+1==dep[edge[i].to])break;  
              if(cur[u]!=-1)S[top++]=cur[u],u=edge[cur[u]].to;  
              else{  
                   if(top==0)break;  
                   dep[u]=-1;u=edge[S[--top]^1].to;  
              }  
         }  
    }  
       return res;  
} 

最大流模板

原文：http://blog.csdn.net/xianxingwuguan1/article/details/19768137