mincostmaxflow_edmondskarp.dpr

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

Const
	MaxN =  ;
	MaxNodeNum =  ;
	MaxEdgeNum =  ;
	Infinity =  ;
	MaxTeamLen =  ;
Type
	TIndex = Longint ;
	TCapacity = Longint ;
	TCost = Longint ;
	EdgeType = record
		Start,Target:TIndex;
		Capa,Flow:TCapacity;
		Cost:TCost;
		Prev:TIndex;
	End;
	NetWorkType = object
	public
		Procedure Initialize(FSource,FSink,FTotalNode:TIndex);
		Procedure InsertEdge(FStart,FTarget:TIndex;FCapa:TCapacity;FCost:TCost;FFlow:TCapacity);
		Procedure EdmondsKarp;
		Function GetFlowValue:TCapacity;
		Function GetCostValue:TCost;
	private
		Source,Sink,TotalNode,TotalEdge:TIndex;
		MaxFlowValue:TIndex;
		TotalCost:TCost;
		Edge:array [1..MaxEdgeNum] of Edgetype;
		InUse: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..MaxTeamLen] of TIndex;
			Head,Tail:TIndex;
		Dist:array [1..MaxNodeNum] of TCost;
		Count:array [1..MaxNodeNum] of TIndex;
		Function SPFA:Boolean;
		Function Opposite(EdgeNum:TIndex):TIndex;
	End;
	Procedure NetWorkType.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 NetWorkType.InsertEdge(FStart,FTarget:TIndex;FCapa:TCapacity;FCost:TCost;FFlow:TCapacity);
	Begin
		Inc(TotalEdge);
		Edge[TotalEdge].Start := FStart ;
		Edge[TotalEdge].Target := FTarget ;
		Edge[TotalEdge].Capa := FCapa ;
		Edge[TotalEdge].Flow := FFlow ;
		Edge[TotalEdge].Cost := FCost ;
		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 := -FFlow ;
		Edge[TotalEdge].Cost := -FCost ;
		Edge[TotalEdge].Prev := Last[FTarget] ;
		Last[FTarget] := TotalEdge ;
	End;
	Function NetWorkType.Opposite(EdgeNum:TIndex):TIndex;
	Begin
		if Odd(EdgeNum) then
			Result := EdgeNum + 1
		Else
			Result := EdgeNum - 1 ;
	End;
	Function NetWorkType.SPFA:Boolean;
	Var
		Cur,CurEdge:TIndex;
	Begin
		Result := False ;
		For Cur := 1 To TotalNode Do
			Dist[Cur] := Infinity ;
		FillChar(InUse,SizeOf(InUse),False);
		FillChar(Count,SizeOf(Count),0);
		Head := 1 ;
		Tail := 2 ;
		Team[Head] := Source ;
		Dist[Source] := 0 ;
		InUse[Source] := True ;
		PrevEdge[Source] := 0 ;
		Count[Source] := 1 ;
		Delta[Source] := Infinity ;
		While Head <> Tail Do
		Begin
			Cur := Team[Head] ;
			CurEdge := Last[Cur] ;
			While CurEdge <> 0 Do
			Begin
				With Edge[CurEdge] Do
					If (Flow < Capa) And (Dist[Target] > Dist[Start] + Cost) Then
					Begin
						Dist[Target] := Dist[Start] + Cost ;
						PrevEdge[Target] := CurEdge ;
						Delta[Target] := Delta[Start] ;
						If Delta[Target] > Capa - Flow Then
							Delta[Target] := Capa - Flow ;
						If Not InUse[Target] Then
						Begin
							Inc(Count[Target]);
							If Count[Target] = TotalNode Then
								Exit;
							InUse[Target] := True ;
							Team[Tail] := Target ;
							Inc(Tail);
							If Tail > MaxTeamLen Then
								Tail := 1 ;
						End;
					End;
				CurEdge := Edge[CurEdge].Prev ;
			End;
			Inc(Head);
			If Head > MaxTeamLen Then
				Head := 1 ;
			InUse[Cur] := False ;
		End;
		Result := Dist[Sink] < Infinity ;
	End;
	Procedure NetWorkType.EdmondsKarp;
	Var
		Cur:TIndex;
		CurDelta:TCapacity;
	Begin
		MaxFlowValue := 0 ;
		TotalCost := 0 ;
		While SPFA do
		Begin
			CurDelta := Delta[Sink] ;
			Inc(MaxFlowValue,CurDelta);
			Inc(TotalCost,CurDelta * Dist[Sink]);
			Cur := Sink ;
			Repeat
				Inc(Edge[PrevEdge[Cur]].Flow,CurDelta);
				Dec(Edge[Opposite(PrevEdge[Cur])].Flow,CurDelta);
				Cur := Edge[PrevEdge[Cur]].Start ;
			Until Cur = Source ;
		End;
	End;
	Function NetWorkType.GetFlowValue:TCapacity;
	Begin
		Result := MaxFlowValue ;
	End;
	Function NetWorkType.GetCostValue:TCost;
	Begin
		Result := TotalCost ;
	End;
Var
	NetWork:NetWorkType;