maxflow_edmondskarp.dpr

CQF大牛关于网络流方面的程序代码

Const
	MaxN = ;
	MaxM = ;
	MaxNodeNum = ;
	MaxEdgeNum = ;
	Infinity = ;
Type
	TIndex = Longint;
	TCapacity = Longint;
	EdgeType = record
		Start,Target:TIndex;
		Capa,Flow:TCapacity;
		Prev:TIndex;
	End;
	TNetwork = object
	public
		Procedure Initialize(FSource,FSink,FTotalNode:TIndex);
		Procedure InsertEdge(FStart,FTarget:TIndex;FCapa:TCapacity);
		Procedure EdmondsKarp;
	private
		Source,Sink,TotalNode:TIndex;
		TotalEdge:TIndex;
		MaxFlowValue:TCapacity;
		Edge:array [1..MaxEdgeNum] of Edgetype;
		Visit:array [1..MaxNodeNum] of Boolean;
		PrevEdge:array [1..MaxNodeNum] of TIndex;
		Delta:array [1..MaxNodeNum] of TCapacity;
		Last:array [1..MaxNodeNum] of TIndex;
		Team:array [1..MaxNodeNum] of TIndex;
		Head,Tail:TIndex;
		Function Opposite(EdgeNum:TIndex):TIndex;
		Function GetFlowValue:TCapacity;
	End;
	Procedure TNetwork.Initialize(FSource,FSink,FTotalNode:TIndex);
	Begin
		Source := FSource ;
		Sink := FSink ;
		TotalNode := FTotalNode ;
		TotalEdge := 0 ;
		Fillchar(Edge,Sizeof(Edge),0);
		Fillchar(Last,Sizeof(Last),0);
	End;
	Procedure TNetwork.InsertEdge(FStart,FTarget:TIndex;FCapa:TCapacity);
	Begin
		Inc(TotalEdge);
		Edge[TotalEdge].Start := FStart ;
		Edge[TotalEdge].Target := FTarget ;
		Edge[TotalEdge].Capa := FCapa ;
		Edge[TotalEdge].Flow := 0 ;
		Edge[TotalEdge].Prev := Last[FStart] ;
		Last[FStart] := TotalEdge ;
		Inc(TotalEdge);
		Edge[TotalEdge].Start := FTarget ;
		Edge[TotalEdge].Target := FStart ;
		Edge[TotalEdge].Capa := 0 ;
		Edge[TotalEdge].Flow := 0 ;
		Edge[TotalEdge].Prev := Last[FTarget] ;
		Last[FTarget] := TotalEdge ;
	End;
	Function TNetwork.Opposite(EdgeNum:TIndex):TIndex;
	Begin
		if odd(EdgeNum) then
			Result := EdgeNum + 1
		Else
			Result := EdgeNum - 1 ;
	End;
	Procedure TNetwork.EdmondsKarp;
	Var
		Cur:TIndex;
		CurDelta:TCapacity;
	Begin
		While True do
		Begin
			Fillchar(Visit,Sizeof(Visit),False);
			Fillchar(PrevEdge,Sizeof(PrevEdge),0);
			Fillchar(Delta,Sizeof(Delta),0);
			Fillchar(Team,Sizeof(Team),0);
			Head := 0 ;
			Tail := 1 ;
			Team[Tail] := Source ;
			Delta[Source] := Infinity ;
			Visit[Source] := True ;
			Repeat
				Inc(Head);
				Cur := Last[Team[Head]] ;
				While Cur <> 0 do
				Begin
					If not Visit[Edge[Cur].Target] and (Edge[Cur].Flow < Edge[Cur].Capa) then
					Begin
						Inc(Tail);
						Team[Tail] := Edge[Cur].Target ;
						Delta[Team[Tail]] := Delta[Team[Head]] ;
						If Delta[Team[Tail]] > Edge[Cur].Capa - Edge[Cur].Flow then
							Delta[Team[Tail]] := Edge[Cur].Capa - Edge[Cur].Flow ;
						PrevEdge[Team[Tail]] := Cur ;
						Visit[Edge[Cur].Target] := True ;
					End;
					Cur := Edge[Cur].Prev ;
				End;
			Until Visit[Sink] or (Head = Tail) ;
			If not Visit[Sink] then	Exit;

			Cur := Sink ;
			CurDelta := Delta[Sink] ;
			Repeat
				Inc(Edge[PrevEdge[Cur]].Flow,CurDelta);
				Dec(Edge[Opposite(PrevEdge[Cur])].Flow,CurDelta);
				Cur := Edge[PrevEdge[Cur]].Start ;
			Until Cur = Source ;
			Inc(MaxFlowValue,CurDelta);
		End;
	End;
	Function TNetwork.GetFlowValue:TCapacity;
	Begin
		Result := MaxFlowValue ;
	End;
Var
	Network:TNetwork;