relabel2front_maxflow_adjlist_liuctic.h

ACM经典算法ACM经典算法ACM经典算法

/**************************************************
邻接表可重边可有回路最大流 relabel to front  O(V^3)

created: 2007-11-27  by: liuctic

仍然在测试中。。基本正确。。因为做了
一些改进，目前不能完全证明其正确性。

包含头文件： list, vector, iostream 
使用方法：   定义Lgraph 的对象g
            给g.N赋值, 顶点数 
			g.insert(a,b,c) 插入a->b  一条容量为c的边
			g.maxflow 返回 最大流值
***************************************************/

#define TYPE long long

const int MAXV=1000; //最大顶点数
struct edge
{
	int v,pos;// pos: [v][pos] is the opposite edge of this
	TYPE c,f;
	edge(){}
	edge(int v0,int p0,TYPE c0)
	{
		v=v0; pos=p0; c=c0;
	}
};
class Lgraph
{
public:
	vector< edge > eg[MAXV];
	int h[MAXV],N;
	TYPE e[MAXV],flow;
	void insert(int u,int v,int c)
	{
		int s1=eg[u].size(),s2=eg[v].size();
		eg[u].push_back(edge(v,s2,c));
		eg[v].push_back(edge(u,s1,0));
	}
	void init_preflow(int s)
	{
		int i,j,u;
		for(i=0;i<N;i++) h[i]=e[i]=0;
		for(i=0;i<N;i++) for(j=0;j<eg[i].size();j++) eg[i][j].f=0;
		h[s]=N;
		for(j=0;j<eg[s].size();j++)
		{
			u=eg[s][j].v;
			eg[s][j].f=eg[s][j].c;
			eg[u][eg[s][j].pos].f=-eg[s][j].c;
			e[u]=eg[s][j].c;
			e[s]-=eg[s][j].c;
		}
	}
	void push(int u,int v,int idx)
	{
		TYPE temp=e[u]<(eg[u][idx].c-eg[u][idx].f)?e[u]:(eg[u][idx].c-eg[u][idx].f);
		eg[u][idx].f+=temp;
		eg[v][eg[u][idx].pos].f=-eg[u][idx].f;
		e[u]-=temp; e[v]+=temp;
	}
	void relabel(int u,int mn)
	{
		h[u]=mn+1;
	}
	void discharge(int u)
	{
		int i=0,v,mn=2*N;
		while(e[u]>0)
		{
			if(i==eg[u].size())
			{
				relabel(u,mn);
				i=0;
				mn=2*N;
			}
			else
			{
				v=eg[u][i].v;
				if(eg[u][i].c>eg[u][i].f&&(h[v]+1==h[u]))
					push(u,v,i);
				if(eg[u][i].c>eg[u][i].f&&mn>h[v]) mn=h[v];
				/*else*/ i++;
			}
		}
	}
	void relabel2front(int s,int t)
	{
		int i,j,u;
		list<int> L;
		for(i=0;i<N;i++) if(i!=s&&i!=t) L.push_back(i);
		list<int>::iterator ite=L.begin();
		for(ite=L.begin();ite!=L.end();ite++)
		{
			u=*ite;
			int oldheight=h[u];
			discharge(u);
			if(h[u]>oldheight)
			{
				L.erase(ite);
				L.push_front(u);
				ite=L.begin();
			}
		}
	}
	TYPE maxflow(int s,int t)
	{
		init_preflow(s);
		relabel2front(s,t);
		flow=0;
		int i;
		for(i=0;i<eg[s].size();i++)
			if(eg[s][i].c) flow+=eg[s][i].f;
		return flow;
	}
};