maxflow_cqf.dpr

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

Program MaxFlow_CQF;
Const
	MaxN = 35 ;
	MaxM = 35 ;
	MaxNodeNum = MaxN * MaxM + 2 ;
	MaxEdgeNum = MaxN * MaxM * 6 ;
	Infinity = MaxLongint Div 2;
Type
	TIndex = Longint;
	TCapacity = Longint;
	TEdge = Record
		Start,Target:TIndex;
		Flow,Capa:TCapacity;
		PrevEdge:TIndex;
	End;
	TLast = Array [1..MaxNodeNum] Of TIndex;
	TNetwork = Object
		NodeNum,EdgeNum:TIndex;
		Source,Sink:TIndex;
		Edge:Array [-MaxEdgeNum..MaxEdgeNum] Of TEdge;
		Last,LastBackup:TLast;
		TotalFlow,Delta:TCapacity;
		Visit:Array [1..MaxNodeNum] Of TIndex;
		Procedure ClearFlow;
		Procedure Initialize(FNodeNum,FSource,FSink:TIndex);
		Procedure InsertEdge(FStart,FTarget:TIndex;FCapa:TCapacity);
		Function Min(A,B:TIndex):TCapacity;
		Function FindPath(Cur:TIndex;Now:TCapacity):Boolean;
		Procedure Main;
		Function GetFlowValue:TCapacity;
	End;
	Procedure TNetwork.ClearFlow;
	Var
		I:TIndex;
	Begin
		For I := 1 To EdgeNum Do
			Edge[I].Flow := 0 ;
	End;
	Procedure TNetwork.Initialize(FNodeNum,FSource,FSink:TIndex);
	Begin
		NodeNum := FNodeNum ;
		EdgeNum := 0 ;
		Source := FSource ;
		Sink := FSink ;
		FillChar(Last,SizeOf(Last),0);
	End;
	Procedure TNetwork.InsertEdge(FStart,FTarget:TIndex;FCapa:TCapacity);
	Begin
		Inc(EdgeNum);
		Edge[EdgeNum].Start := FStart ;
		Edge[EdgeNum].Target := FTarget ;
		Edge[EdgeNum].Capa := FCapa ;
		Edge[EdgeNum].Flow := 0 ;
		Edge[EdgeNum].PrevEdge := Last[FStart] ;
		Last[FStart] := EdgeNum ;
		Edge[-EdgeNum].Start := FTarget ;
		Edge[-EdgeNum].Target := FStart ;
		Edge[-EdgeNum].Capa := 0 ;
		Edge[-EdgeNum].Flow := 0 ;
		Edge[-EdgeNum].PrevEdge := Last[FTarget] ;
		Last[FTarget] := -EdgeNum ;
	End;
	Function TNetwork.Min(A,B:TIndex):TCapacity;
	Begin
		If A < B Then
			Result := A
		Else
			Result := B ;
	End;
	Function TNetwork.FindPath(Cur:TIndex;Now:TCapacity):Boolean;
	Var
		CurEdge:TIndex;
	Begin
		Visit[Cur] := TotalFlow ;
		Result := True ;
		If Cur = Sink Then
		Begin
			Delta := Now ;
			Exit;
		End;
		CurEdge := Last[Cur] ;
		Repeat
			With Edge[CurEdge] Do
			Begin
				If (Visit[Target] < TotalFlow) And (Flow < Capa) Then
					If FindPath(Target,Min(Now,Capa - Flow)) Then
					Begin
						Last[Cur] := CurEdge ;
						Inc(Flow,Delta);
						Edge[-CurEdge].Flow := -Flow ;
						Exit;
					End;
				CurEdge := PrevEdge ;
				If CurEdge = 0 Then
					CurEdge := LastBackup[Cur] ;
			End;
		Until CurEdge = Last[Cur] ;
		Result := False ;
	End;
	Procedure TNetwork.Main;
	Begin
		TotalFlow := 0 ;
		LastBackup := Last ;
		FillChar(Visit,SizeOf(Visit),255);
		While FindPath(Source,Infinity) Do
			Inc(TotalFlow,Delta);
	End;
	Function TNetwork.GetFlowValue:TCapacity;
	Begin
		Result := TotalFlow ;
	End;