( )
, (1) (8) .
1-2-4-6-8. 4. 2-4 4-6 . , 1-3-5-7-8 4. . , . , .
2
, 1 8 1-3-2-5-4-7-6-8, 2. 1-3, 2-5, 4-7.
3
1 8 . 1-3 ( ), 1-2 2, .
( ).
1 8, , , , 1 8 , , . 1-2-3-5-7-6-8. . 1, 1. , - .
4
1, 8. , . . . 11. .
. , , ( -) Gf (V,Ef).
2.
- .
:
;
,
;
.
.
3.
3.1 :
(G, a), s , t , a:EN( a). , ( )
1) 2
 |
1 2
s 4 t
2) 2
 |
|
|
|
3 4
4 7
s 5 t
1 2
3)
3 2
3 4
s 7
3
4 t
4)
4
6
5 t
s 4 5
5)
2 6
7 t
s 5 5
2 9
6)
3 6
2 5
1 t
s 6 4
7)
3 7
1
s t
5 2 5
3.2
:
 |
, .
3.
( -)
FindPath(source, target) - , , (i,j) c[i][j] - f[i][j]
// f -
// f[i,j] - i j
// kv
//
public int MaxFlow(int source, int target) // source - , target -
{
// :
for (int j = 0; j < kv; j++)//
for (int r = 0; r < kv; r++)
f[j, r] = 0;
int MaxFl = 0; //
int AddFlow;
do
{
// -
//
AddFlow = FindPath(source, target);
MaxFl += AddFlow;
} while (AddFlow > 0); //
return MaxFl;
}
Pascal
#include <stdio.h>
#include <math.h>
int C[202][202],F[202][202],P[202][2],oo=(1<<25),;
bool fl;
int MIN(int A,int B)
{
if(A<B) return A;
return B;
}
void Stream(int N,int i)
{
if(P[i][0]>0) F[P[i][0]-1][i]+=P[N-1][1];
else F[i][abs(P[i][0])-1]-=P[N-1][1];
if(abs(P[i][0])!=N-1) Stream(N,abs(P[i][0])-1);
}
void Mark(int N)
{
bool *Nnew=new bool[N];
int i,seek=N-2;
for(i=0;i<N;i++) Nnew[i]=1;
P[seek][0]=seek+1;
P[seek][1]=oo;
while(!P[N-1][0] && fl)
{
for(i=0;i<N;i++)
if(!P[i][0] && (C[seek][i] || C[i][seek]))
{
if(F[seek][i]<C[seek][i])
{
P[i][0]=seek+1;
P[i][1]=MIN(P[seek][1],C[seek][i]-F[seek][i]);
}
else if(F[i][seek]>0)
{
P[i][0]=-seek-1;
P[i][1]=MIN(P[seek][1],F[i][seek]);
}
}
Nnew[seek]=0;
seek=0;
while(seek<N && (!Nnew[seek] ||!P[seek][0])) seek++;
if(seek>=N) fl=0;
}
}
bool FordF(int N)
{
while(1)
{
for(i=0;i<N;i++) P[i][0]=0;
Mark(N);
if(!fl) break;
Stream(N,N-1);
}
}
C :
.
#include <iostream.h>#include <stdlib.h> // abs().#define TRUE 1#define FALSE 0#define MaxNodes 5 // .#define MaxInt 1000 // .// .struct Uzel{ int Element; // . int Propusk; // . int Metka; // .};class Spisok{ private: int C[MaxNodes][MaxNodes]; // . int c[MaxNodes][MaxNodes]; // . int Put[MaxNodes][MaxNodes]; // . int Potok [MaxNodes]; //. int Est (Uzel*,int,int); int Tpk (int*,int,int); public: void Vvod_Ves(); int Reshenie (); void Vyvod(int); };void main(){ Spisok A; A.Vvod_Ves(); A.Vyvod(A.Reshenie());} void Spisok::Vvod_Ves()// .{ cout << " :\n"; for (int i=0;i<MaxNodes;i++) for (int j=0;j<MaxNodes;j++) { cout << " C[" << (i+1) << "," << (j+1) << "]: "; cin >> C[i][j]; c[i][j] = C[i][j]; }} void Spisok::Vyvod(int n)// .{ // . for (int i=0,sum=0;i<=n;sum+=Potok[i++]); cout << "\n : " << sum; cout << "\n :\n"; for (i=0;i<MaxNodes;i++) for (int j=i;j<MaxNodes;j++) if (C[i][j]) { cout << " (" << (i+1) << "," << (j+1) <<"): "; cout << "(" << C[i][j] << "," << C[j][i] << ")-("; cout << c[i][j] << "," << c[j][i] << ")=("; cout << (C[i][j]-c[i][j]) << "," << (C[j][i]-c[j][i]) << ") "; cout << ": " << abs(C[i][j]-c[i][j]) << " "; if (C[i][j]-c[i][j]!=0) { cout << ": "; if (C[i][j]-c[i][j]>0) cout << (i+1) << "->" << (j+1); else cout << (j+1) << "->" << (i+1); } cout << endl; }} int Spisok::Reshenie(){ Uzel SS[MaxNodes]; // , . Uzel S[MaxNodes]; //. int i,j=0,k,el,mx,mn; int m; // . int nomer=-1; // . int Tupik[MaxNodes]; // "" . int N_Tupik; // . while (j!=-1) { i=m=0; S[i].Element=0; S[i].Propusk=MaxInt; S[i].Metka=TRUE; el=0; N_Tupik=-1; while (el!=MaxNodes-1) { j=-1; for (k=0;k<MaxNodes;k++) if (c[i][k]!=0) // ... if (i>0) // ... { if (!Est(&S[0],m,k) &&!Tpk(&Tupik[0],N_Tupik,k)) // , // "". { SS[++j].Element=k; SS[j].Propusk=c[i][k]; SS[j].Metka=FALSE; } } else if (!Tpk(&Tupik[0],N_Tupik,k)) // ? // , . { // . SS[++j].Element=k; SS[j].Propusk=c[i][k]; SS[j].Metka=FALSE; } if (j!=-1) // . { mx=SS[0].Propusk; el=0; for (k=1;k<=j;k++) if (SS[k].Propusk>mx) { el=k; mx=SS[k].Propusk; } S[++m].Element=SS[el].Element; S[m].Propusk=mx; S[m].Metka=TRUE; if (SS[el].Element==MaxNodes-1) // . { nomer++; // . for (k=0;k<=m;k++) Put[nomer][k]=S[k].Element; // . mn=S[0].Propusk; el=0; for (k=1;k<=m;k++) if (S[k].Propusk<mn) { el=k; mn=S[k].Propusk; } Potok[nomer]=mn; // . // . for (k=0;k<m;k++) { c[S[k].Element][S[k+1].Element] -= Potok[nomer]; c[S[k+1].Element][S[k].Element] += Potok[nomer]; } el=MaxNodes-1; // . j=0; } else i=S[m].Element; } else // . , : { if (i==0) //) . // - el=MaxNodes-1; else //) . // . { Tupik[++N_Tupik]=S[m].Element; m--; i=S[m].Element; } } } } return nomer; // .} int Spisok::Est(Uzel S[], int m, int k)// , k S.//m - .// 1, , 0 - .{ for (int l=0;l<=m;l++) if (S[l].Element==k) return 1; return 0;} int Spisok::Tpk(int Tupik[],int N_Tupik, int k) // , k "" .//N_Tupik - .// 1, , 0 - .{ if (N_Tupik==-1) return 0; for (int l=0;l<=N_Tupik;l++) if (Tupik[l]==k) return 1; return 0;}
0 z:
|
|
|
|
|
|
k:=0;
j:=1;
usl:=0;
repeat
if graf[i,1]=j then
begin
if graf[i,5]=0 then
begin
inc(k);
mas[k]:=i;
j:=graf[i,2];
l:=i;
i:=1;
end
else
begin
inc(i);
end;
end else inc(i);
if i>count-1 then
if graf[l,2]<>n then
begin
j:=graf[l,1];
graf[l,5]:=1;
mas[k]:=0;
i:=1;
dec(k);
if k=0 then j:=1;
end
until (graf[l,2]=n)or(k<0);
graf[i,j] .
Mas[i] ( 0 z).
.
:
for i:=1 to count-1 do
if graf[i,3]=graf[i,4] then
graf[i,5]:=1 else graf[i,5]:=0;
end;
graf[i,5] (0- , 1- ).
:
usl:=0; { }
if k>=0 then
repeat
for i:=1 to k do
begin
l:=mas[i];
graf[l,4]:=graf[l,4]+1;
end;
for i:=1 to k do
begin
l:=mas[i];
if graf[l,4]=graf[l,3] then usl:=1;
end;
until usl=1;
5.
, ;
;
;
( );
.
6.
1. ?
2. .
3. ?
4. ?
5. .
6. .
7. ? .
8. ?
9. .
10. . 5 .
5
11. ?
7.
1. . . : . / . ., . ., . . ., . . 3- ., . .: - . , 2004. 743 .
2. . . : . . . . .; , 2003 447 ( )
3. . . , . . - . - .: , 1988 479, [1] .: ., 22 .
4. , / . . . . . . . 2- . . .: , 1980.-336
1. ., . . .: , 1974. 368c.
2. . . . .: , 2004. . 664. ISBN 5-9502-0057-8(.: , 1987. 383c.)
3. . . . VI. // : = Introduction to Algorithms. 2- .. .: , 2006. . 1296. ISBN 0-07-013151-1
|
|
|
