学步园

九野的博客，转载请注明出处 ：

http://blog.csdn.net/acmmmm/article/details/11199941

struct Edge{
	int from,to,flow,cap, nex;
}edge[M*2];//双向边，注意RE 注意这个模版是 相同起末点的边 合并而不是去重
int head[N],edgenum;//2个要初始化-1和0
void addedge(int u,int v,int cap){//网络流要加反向弧
	Edge E={u,v,0,cap,head[u]};
	edge[edgenum]=E;
	head[u]=edgenum++;
	Edge E2={v,u,0,cap,head[v]}; //这里的cap若是单向边要为0
	edge[edgenum]=E2;
	head[v]=edgenum++;
}


int dis[N],cur[N];//距离起点的距离 cur[i]表示i点正在考虑的边 优化不再考虑已经用过的点 初始化为head
bool vis[N];
bool BFS(int Start,int End){
	memset(vis,0,sizeof(vis)); 
	memset(dis,-1,sizeof(dis));
	queue<int>Q;	while(!Q.empty())Q.pop();
	Q.push(Start);	dis[Start]=0;	vis[Start]=1;
	while(!Q.empty())
	{
		int u = Q.front(); Q.pop();
		for(int i=head[u];i!=-1;i=edge[i].nex){
			Edge E =edge[i];
			if(!vis[E.to] && E.cap>E.flow)
			{
				vis[E.to]=1;
				dis[E.to]=dis[u]+1;
				if(E.to==End)return true;
				Q.push(E.to);
			}
		}
	}
	return false;
}
int DFS(int x, int a,int End){//流入x 的流量是a
	if(x==End || a==0)return a;
	int flow = 0, f;
	for(int& i=cur[x];i!=-1;i=edge[i].nex)
	{
		Edge& E = edge[i];
		if(dis[x]+1 == dis[E.to] && (f = DFS(E.to , Min(a, E.cap-E.flow), End))>0 )
		{
			E.flow += f;
			edge[ i^1 ].flow -= f;//反向边要减掉
			flow += f;
			a -= f;
			if(a==0)break;
		}
	}
	return flow;
}
int Maxflow(int Start,int End){
	int flow=0; 
	while(BFS(Start,End)){
		memcpy(cur,head,sizeof(head));//把head的数组复制过去
		flow += DFS(Start, inf, End);
	}
	return flow;
}