| | tú lùn zhōng de yī zhǒng lǐ lùn yǔ fāng fǎ， yán jiū wǎng luò shàng de yī lèi zuì yōu huà wèn tí。 1955 nián， T.E. hā lǐ sī zài yán jiū tiě lù zuì dà tōng liàng shí shǒu xiān tí chū zài yī gè gěi dìng de wǎng luò shàng xún qiú liǎng diǎn jiān zuì dà yùn shū liàng de wèn tí。 1956 nián， L.R. fú tè hé D.R. fù 'ěr kè sēn děng rén gěi chū liǎo jiě jué zhè lèi wèn tí de suàn fǎ， cóng 'ér jiàn lì liǎo wǎng luò liú lǐ lùn。 suǒ wèi wǎng luò huò róng liàng wǎng luò zhǐ de shì yī gè lián tōng de fù quán yòu xiàng tú D ＝（ V、 E、 C）， qí zhōng V shì gāi tú de dǐng diǎn jí， E shì yòu xiàng biān ( jí hú ) jí， C shì hú shàng de róng liàng。 cǐ wài dǐng diǎn jí zhōng bāo kuò yī gè qǐ diǎn hé yī gè zhōng diǎn。 wǎng luò shàng de liú jiù shì yóu qǐ diǎn liú xiàng zhōng diǎn de kě xíng liú， zhè shì dìng yì zài wǎng luò shàng de fēi fù hán shù， tā yī fāng miàn shòu dào róng liàng de xiàn zhì， lìng yī fāng miàn chú qù qǐ diǎn hé zhōng diǎn yǐ wài， zài suǒ yòu zhōng tú diǎn yào qiú bǎo chí liú rù liàng hé liú chū liàng shì píng héng de。 rú guǒ bǎ xià tú kàn zuò yī gè gōng lù wǎng， dǐng diǎn v1 … v6 biǎo shì 6 zuò chéng zhèn， měi tiáo biān shàng de quán shù biǎo shì liǎng chéng zhèn jiān de gōng lù cháng dù。 xiàn zài yào wèn： ruò cóng qǐ diǎn v1 jiāng wù zī yùn sòng dào zhōng diǎn v6 qù， yìng xuǎn zé nà tiáo lù xiàn cái néng shǐ zǒng yùn shū jù lí zuì duǎn � zhè yàng yī lèi wèn tí chēng wéi zuì duǎn lù wèn tí。 rú guǒ bǎ shàng tú kàn zuò yī gè shū yóu guǎn dào wǎng， v1 biǎo shì fā sòng diǎn， v6 biǎo shì jiē shōu diǎn， qí tā diǎn biǎo shì zhōng zhuǎn zhàn， gè biān de quán shù biǎo shì gāi duàn guǎn dào de zuì dà shū sòng liàng。 xiàn zài yào wèn zěn yàng 'ān pái shū yóu xiàn lù cái néng shǐ cóng v1 dào v6 de zǒng yùn shū liàng wéi zuì dà。 zhè yàng de wèn tí chēng wéi zuì dà liú wèn tí。
zuì dà liú lǐ lùn shì yóu fú tè hé fù 'ěr kè sēn yú 1956 nián chuàng lì de， tā men zhǐ chū zuì dà liú de liú zhí děng yú zuì xiǎo gē ( jié jí ) de róng liàng zhè gè zhòng yào de shì shí， bìng gēn jù zhè yī yuán lǐ shè jì liǎo yòng biāo hào fǎ qiú zuì dà liú de fāng fǎ， hòu lái yòu yòu rén jiā yǐ gǎi jìn， shǐ dé qiú jiě zuì dà liú de fāng fǎ gèng jiā fēng fù hé wán shàn。 zuì dà liú wèn tí de yán jiū mìqiè liǎo tú lùn hé yùn chóu xué， tè bié shì yǔ xiàn xìng guī huá de lián xì， kāipì liǎo tú lùn yìng yòng de xīn tú jìng。
mù qián wǎng luò liú de lǐ lùn hèyìng yòng zài bù duàn fā zhǎn， chū xiàn liǎo jù yòu zēng yì de liú、 duō zhōng duān liú、 duō shāng pǐn liú yǐ jí wǎng luò liú de fēn jiě yǔ hé chéng děng xīn kè tí。 wǎng luò liú de yìng yòng yǐ biàn jí tōng xùn、 yùn shū、 diàn lì、 gōng chéng guī huá、 rèn wù fēn pài、 shè bèi gēngxīn yǐ jí jì suàn jī fǔ zhù shè jì děng zhòng duō lǐng yù。 | | 1、 augment path， zhí yì wéi “ zēng guǎng lù ”， qí sī xiǎng dà zhì rú xià：
yuán yòu wǎng luò wéi G， shè yòu yī fǔ zhù tú G'， qí dìng yì wéi V(G')=V(G)， E(G') chū shǐ zhí（ yě jiù shì róng liàng） yǔ E(G) xiāng tóng。 měi cì cāo zuò shí cóng Source diǎn sōu suǒ chū yī tiáo dào Sink diǎn de lù jìng， rán hòu jiāng gāi lù jìng shàng suǒ yòu de róng liàng jiǎn qù gāi lù jìng shàng róng liàng de zuì xiǎo zhí， rán hòu duì lù jìng shàng měi yī tiáo biān <u,v> tiān jiā huò kuò dà fǎn fāng xiàng de róng liàng， dà xiǎo jiù shì gāng cái jiǎn qù de róng liàng。 yī zhí dào méi yòu lù wéi zhǐ。 cǐ shí fǔ zhù tú shàng de zhèng xiàng liú jiù shì zuì dà liú。
wǒ men hěn róng yì jué dé zhè gè suàn fǎ huì xiàn rù sǐ xún huán， dàn shì shí shàng bù shì zhè yàng de。 wǒ men zhǐ xū yào zhù yì dào měi cì wǎng luò zhōng yóu Source dào Sink de liú dū zēng jiā liǎo， ruò róng liàng dōushì zhěng shù， zé zhè gè suàn fǎ bì rán huì jié shù。
xún zhǎo tōng lù de shí hòu kě yǐ yòng DFS， BFS zuì duǎn lù děng suàn fǎ。 jiù zhè liǎng zhě lái shuō ,BFS yào bǐ DFS kuài dé duō， dàn shì biān mǎ liàng yě huì xiāng yìng shàng yī gè shù liàng jí。
zēng guǎng lù fāng fǎ kě yǐ jiě jué zuì dà liú wèn tí， rán 'ér tā yòu yī gè bù kě bì miǎn de quē xiàn， jiù shì zài jí duān qíng kuàng xià měi cì zhǐ néng jiāng liú kuò dà 1（ jiǎ shè róng liàng、 liú wéi zhěng shù）， zhè yàng huì zào chéng xìng néng shàng de hěn dà wèn tí， jiě jué zhè gè wèn tí yòu yī gè fù zá dé duō de suàn fǎ， jiù shì yù tuī jìn suàn fǎ。
2、 pushlabel， zhí yì wéi“ yù tuī jìn” suàn fǎ。
3、 yā rù yǔ zhòng biāo jì (Push-Relabel) suàn fǎ
chú liǎo yòng gè zhǒng fāng fǎ zài shèng yú wǎng luò zhōng bù duàn zhǎo zēng guǎng lù (augmenting) de Ford-Fulkerson xì de suàn fǎ wài， hái yòu yī zhǒng qiú zuì dà liú de suàn fǎ bèi chēng wéi yā rù yǔ zhòng biāo jì (Push-Relabel) suàn fǎ。 tā de jī běn cāo zuò yòu： yā rù， zuò yòng yú yī tiáo biān， jiāng biān de shǐ diǎn de yù liú jìn kě néng duō de yā xiàng zhōng diǎn； zhòng biāo jì， zuò yòng yú yī gè diǎn， jiāng tā de gāo dù（ yě jiù shì label） shè wéi suǒ yòu lín jiē diǎn de gāo dù de zuì xiǎo zhí jiā yī。 Push-Relabel xì de suàn fǎ pǔ biàn yào bǐ Ford-Fulkerson xì de suàn fǎ kuài， dàn shì quē diǎn shì xiāng duì nán yǐ lǐ jiě。
Relabel-to-Front shǐ yòng yī gè liàn biǎo bǎo cún yì chū dǐng diǎn， yòng Discharge cāo zuò bù duàn shǐ yì chū dǐng diǎn bù zài yì chū。 Discharge de cāo zuò guò chéng shì： ruò zhǎo bù dào kě bèi yā rù de lín biān， zé zhòng biāo jì， fǒu zé duì lín biān yā rù， zhí zhì diǎn bù zài yì chū。 suàn fǎ de zhù guò chéng shì： shǒu xiān jiāng yuán diǎn chū fā de suǒ yòu biān chōng mǎn， rán hòu jiāng chú yuán hé huì wài de suǒ yòu dǐng diǎn bǎo cún zài yī gè liàn biǎo lǐ， cóng liàn biǎo tóu kāi shǐ jìn xíng Discharge， rú guǒ wán chéng hòu dǐng diǎn de gāo dù yòu suǒ zēng jiā， zé jiāng zhè gè dǐng diǎn zhì yú liàn biǎo de tóu bù， duì xià yī gè dǐng diǎn kāi shǐ Discharge。
Relabel-to-Front suàn fǎ de shí jiān fù zá dù shì O(V^3)， hái yòu yī gè jiào HighestLabelPreflowPush de suàn fǎ fù zá dù jù shuō shì O(V^2*E^0.5)。 wǒ yán jiū liǎo yī xià HLPP， gǎn jué tā hé Relabel-to-Front běn zhì shàng méi yòu qū bié， yīn wéi Relabel-to-Front měi cì qián yí dedōu shì gāo dù zuì gāo de dǐng diǎn， suǒ yǐ yě xiāng dāng yú měi cì xuǎn zé zuì gāo de biāo hào jìn xíng gēngxīn。 hái yòu yī gè gǎn jué yě huì hěn hǎo shí xiàn de suàn fǎ shì shǐ yòng duì liè wéi hù yì chū dǐng diǎn， měi cì duì pop chū lái de dǐng diǎn discharge， chū xiàn liǎo xīn de yì chū dǐng diǎn shí rù duì。
Push-Relabel lèi de suàn fǎ yòu yī gè míng wéi gapheuristic de yōu huà， jiù shì dāng cún zài yī gè zhěng shù 0<k<V， méi yòu rèn hé dǐng diǎn mǎn zú h[v]=k shí， duì suǒ yòu h[v]>k de dǐng diǎn v zuò gēngxīn， ruò tā xiǎo yú V+1 jiù zhì wéi V+1。
cpp chéng xù :
#include<cstdio>
constlongmaxn=1000+10;
constlongmaxm=440000+100;
constlongmaxnum=100000000;
longn,m,s=0,tot=0,list[maxn],p[maxn],g[maxn],gg[maxn],dis[maxn];
boolmark[maxn];
structnode
{
longk,f,c,next,g;
}d[maxm<<1];
voidinsert(longu,longv,longc)
{
d[tot].k=v;
d[tot].f=0;
d[tot].c=c;
d[tot].next=g;
g=tot;
d[tot].g=tot+1;
tot++;
d[tot].k=u;
d[tot].f=0;
d[tot].c=0;
d[tot].next=g[v];
g[v]=tot;
d[tot].g=tot-1;
tot++;
}
voidbfs()
{
longx,u,v,h,t;
for(longi=0;i<n;i++)
dis=0;
h=0;
t=1;
list=0; | zuì xiǎo fèi yòng zuì dà liú | yī ． Ford hé Fulkerson dié jiā suàn fǎ .
jī běn sī lù： bǎ gè tiáo hú shàng dān wèi liú liàng de fèi yòng kàn chéng mǒu zhǒng cháng dù , yòng qiú jiě zuì duǎn lù wèn tí de fāng fǎ què dìng yī tiáo zì V1 zhì Vn de zuì duǎn lù ; zài jiāng zhè tiáo zuì duǎn lù zuò wéi kě kuò chōng lù , yòng qiú jiě zuì dà liú wèn tí de fāng fǎ jiāng qí shàng de liú liàng zēng zhì zuì dà kě néng zhí ; ér zhè tiáo zuì duǎn lù shàng de liú liàng zēng jiā hòu , qí shàng gè tiáo hú de dān wèi liú liàng de fèi yòng yào zhòng xīn què dìng , rú cǐ duō cì dié dài , zuì zhōng dé dào zuì xiǎo fèi yòng zuì dà liú .
dié jiā suàn fǎ：
1) gěi dìng mù biāo liú liàng F huò ∞ , gěi dìng zuì xiǎo fèi yòng de chū shǐ kě xíng liú =0
2) ruò V(f)=F, tíng zhǐ ,f wéi zuì xiǎo fèi yòng liú ; fǒu zé zhuǎn (3).
3) gòu zào xiāng yìng de xīn de fèi yòng yòu xiàng tú W(fij), zài W(fij) xún zhǎo Vs dào Vt de zuì xiǎo fèi yòng yòu xiàng lù P( zuì duǎn lù ), yán P zēng jiā liú f de liú liàng zhí dào F, zhuǎn (2); ruò bù cún zài cóng Vs dào Vt de zuì xiǎo fèi yòng de yòu xiàng lù P, tíng zhǐ .f jiù shì zuì xiǎo fèi yòng zuì dà liú .
jù tǐ jiě tí bù zhòu：
shè tú zhōng shuāng xiàn suǒ shì lù jìng wéi zuì duǎn lù jìng， fèi yòng yòu xiàng tú wéi W（ fij）．
zài tú (a) zhōng gěi chū líng liú f, zài tú (b) zhōng zhǎo dào zuì xiǎo fèi yòng yòu xiàng lù , xiū gǎi tú (a) zhōng de kě xíng liú ,δ=min{4,3,5}=3, dé tú (c), zài zuò chū (c) de tiáozhěng róng liàng tú , zài gòu zào xiāng yìng de xīn de zuì xiǎo fèi yòng yòu xiàng lù dé tú (d), xiū gǎi tú (c) zhōng de kě xíng liú ,δ=min{1,1,2,2}=1, dé tú (e), yǐ cǐ lèi tuī , yī zhí dé dào tú (h), zài tú (h) zhōng yǐ wú zuì xiǎo fèi yòng yòu xiàng lù , tíng zhǐ , jīng jì suàn :
tú (h) zhōng zuì xiǎo fèi yòng =1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
tú (g) zhōng zuì dà liú =5
zuì dà liú wèn tí jǐn zhù yì wǎng luò liú de liú tōng néng lì， méi yòu kǎo lǜ liú tōng de fèi yòng。 shí jì shàng fèi yòng yīn sù shì hěn zhòng yào de。 lì rú zài jiāo tōng yùn shū wèn tí zhōng， wǎng wǎng yào qiú zài wán chéng yùn shū rèn wù de qián tí xià， xún qiú yī gè shǐ zǒng yùn shū fèi yòng zuì shěng de yùn shū fāng 'àn， zhè jiù shì zuì xiǎo fèi yòng liú wèn tí。 rú guǒ zhǐ kǎo lǜ dān wèi huò wù de yùn shū fèi yòng， nà me zhè gè wèn tí jiù biàn chéng zuì duǎn lù wèn tí。 yóu cǐ kě jiàn， zuì duǎn lù wèn tí shì zuì xiǎo fèi yòng liú wèn tí de jī chǔ。 xiàn yǐ yòu yī xì liè qiú zuì duǎn lù de chéng gōng fāng fǎ。 zuì xiǎo fèi yòng liú ( huò zuì xiǎo fèi yòng zuì dà liú ) wèn tí， kě yǐ jiāo tì shǐ yòng qiú jiě zuì dà liú hé zuì duǎn lù liǎng zhǒng fāng fǎ， tōng guò dié dài dé dào jiě jué。
èr． juàn suàn fǎ：
1) lì yòng Ford hé Fulkson biāo hào suàn fǎ zhǎo chū liú liàng wéi F(<= zuì dà liú ) de liú f.
2) gòu zào f duì yìng de tiáozhěng róng liàng de liú wǎng luò N'(f).
3) sōu suǒ N'(f) zhōng de fù fèi yòng yòu xiàng tú C(Floyd suàn fǎ ), ruò méi yòu zé tíng zhǐ , fǒu zé zhuǎn (4).
4) zài C shàng zhǎo chū zuì dà de xún huán liú , bìng jiā dào N shàng qù , tóng shí xiū gǎi N'(F) zhōng C de róng liàng , zhuǎn (3).
jù tǐ jiě tí bù zhòu :
lì yòng Ford hé Fulkson biāo hào suàn fǎ , dé wǎng luò de zuì dà liú F=5, jiàn tú (a), yóu tú (a) gòu zào xiāng yìng de tiáozhěng róng liàng de liú wǎng luò (b), tú (b) zhōng bù cún zài fù fèi yòng yòu xiàng tú , gù tíng zhǐ． jīng jì suàn :
tú (b) zhōng zuì xiǎo fèi yòng =4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38
tú (a) zhōng zuì dà liú wéi F=5
type
szbest=record
v,l:integer;
end;
szmap=record
c,f,w:integer;
end;
var
map:array[0..1000,0..1000]ofszmap;
best:array[0..1000]ofszbest;
i,j,ans,n,k,a,b,c,d,s,t:integer;
functionfind:boolean;
vari,j:integer;
flag:boolean;
begin
fori:=1tondobest.v:=maxint;
best[s].v:=0;
repeat
flag:=true;
fori:=1tondo
ifbest.v<maxintthen
forj:=1tondo
if(map[i,j].f<map[i,j].c)and(best.v+map
[i,j].w<best[j].v)then
begin
best[j].v:=best.v+map[i,j].w;
best[j].l:=i;flag:=false;
end;
untilflag;
ifbest[t].v<maxintthenexit(true)elseexit(false);
end;
procedureupdata;
vari,j:integer;
begin
i:=t;
whilei<>sdobegin
j:=best.l;
inc(map[j,i].f);
map[i,j].f:=-map[j,i].f;
i:=j;
end;
inc(ans,best[t].v);
end;
begin
assign(input,'g4.in');reset(input);
readln(n);
repeat
readln(a,b,c,d);
ifa+b+c+d>0thenbegin
map[a,b].c:=c;map[b,a].c:=0;
map[a,b].w:=d;map[b,a].w:=-d;
end;
untila+b+c+d=0;
s:=1;t:=n;ans:=0;
whilefinddoupdata;
writeln(ans);
fori:=1tondo
forj:=1tondo
ifmap[i,j].f>0thenwriteln(i,'',j,'',map[i,j].w,'*',map
[i,j].f);
end. | | yī、 wǎng luò liú de jī běn gài niàn
xiān lái kàn yī gè shí lì。
xiàn zài xiǎng jiāng yī xiē wù zī cóng S yùn dǐ T， bì xū jīng guò yī xiē zhōng zhuǎn zhàn。 lián jiē zhōng zhuǎn zhàn de shì gōng lù， měi tiáo gōng lù dōuyòu zuì dà yùn zài liàng。 rú xià tú：
měi tiáo hú dài biǎo yī tiáo gōng lù， hú shàng de shù biǎo shì gāi gōng lù de zuì dà yùn zài liàng。 zuì duō néng jiāng duō shǎo huò wù cóng S yùn dǐ T？
zhè shì yī gè diǎn xíng de wǎng luò liú mó xíng。 wèile jiě dá cǐ tí， wǒ men xiān liǎo jiě wǎng luò liú de yòu guān dìng yì hé gài niàn。
ruò yòu xiàng tú G=(V,E) mǎn zú xià liè tiáo jiàn：
1、 yòu qiě jǐn yòu yī gè dǐng diǎn S， tā de rù dù wéi líng， jí d-(S)=0， zhè gè dǐng diǎn S biàn chēng wéi yuán diǎn， huò chēng wéi fā diǎn。
2、 yòu qiě jǐn yòu yī gè dǐng diǎn T， tā de chū dù wéi líng， jí d+(T)=0， zhè gè dǐng diǎn T biàn chēng wéi huì diǎn， huò chēng wéi shōu diǎn。
3、 měi yī tiáo hú dōuyòu fēi fù shù， jiào zuò gāi biān de róng liàng。 biān (vi,vj) de róng liàng yòng cij biǎo shì。
zé chēng zhī wéi wǎng luò liú tú， jì wéi G=(V,E,C)
pì rú tú 5-1 jiù shì yī gè wǎng luò liú tú。
1． kě xíng liú
duì yú wǎng luò liú tú G， měi yī tiáo hú (i,j) dū gěi dìng yī gè fēi fù shù fij， zhè yī zǔ shù mǎn zú xià liè sān tiáo jiàn shí chēng wéi zhè wǎng luò de kě xíng liú， yòng f biǎo shì tā。
1、 měi yī tiáo hú (i,j) yòu fij ≤ cij。
2、 chú yuán diǎn S hé huì diǎn T yǐ wài de suǒ yòu de diǎn vi， héng yòu：
gāi děng shì shuō míng zhōng jiān diǎn vi de liú liàng shǒu héng， shū rù yǔ shū chū liàng xiāng děng。
3、 duì yú yuán diǎn S hé huì diǎn T yòu：
zhè lǐ V(f) biǎo shì gāi kě xíng liú f de liú liàng。
lì rú duì tú 5-1 ér yán， tā de yī gè kě xíng liú rú xià：
liú liàng V(f)=5。
2． kě gǎi jìn lù
gěi dìng yī gè kě xíng liú f=。 ruò fij=cij， chēng <vi,vj> wéi bǎo hé hú； fǒu zé chēng <vi,vj> wéi fēi bǎo hé hú。 ruò fij=0， chēng <vi,vj> wéi líng liú hú； fǒu zé chēng <vi,vj> wéi fēi líng liú hú。
dìng yì yī tiáo dào lù P， qǐ diǎn shì S、 zhōng diǎn shì T。 bǎ P shàng suǒ yòu yǔ P fāng xiàng yī zhì de hú dìng yì wéi zhèng xiàng hú， zhèng xiàng hú de quán tǐ jì wéi P+； bǎ P shàng suǒ yòu yǔ P fāng xiàng xiāng bèi de hú dìng yì wéi fǎn xiàng hú， fǎn xiàng hú de quán tǐ jì wéi P-。
pì rú zài tú 5-1 zhōng， P=(S,V1,V2,V3,V4,T)， nà me
P+={<S,V1>,<V1,V2>,<V2,V3>,<V4,T>}
P-={<V4,V3>}
gěi dìng yī gè kě xíng liú f， P shì cóng S dào T de yī tiáo dào lù， rú guǒ mǎn zú：
nà me jiù chēng P shì f de yī tiáo kě gǎi jìn lù。（ yòu xiē shū shàng yòu chēng： kě zēng guǎng guǐ） zhī suǒ yǐ chēng zuò“ kě gǎi jìn”， shì yīn wéi kě gǎi jìn lù shàng hú de liú liàng tōng guò yī dìng de guī zé xiū gǎi， kě yǐ lìng zhěng gè liú liàng fàng dà。 jù tǐ fāng fǎ xià yī jié huì zhòng diǎn jiè shào， cǐ bù zhuì shù。
3． gē qiē
yào jiě jué wǎng luò zuì dà liú wèn tí， bì xū xiān xué xí gē qiē de gài niàn hé yòu guān zhī shí。
G=(V,E,C) shì yǐ zhī de wǎng luò liú tú， shè U shì V de yī gè zǐ jí， W=VU， mǎn zú SU， TW。 jí U、 W bǎ V fēn chéng liǎng gè bù xiāng jiāo de jí hé， qiě yuán diǎn hé huì diǎn fēn shǔ bù tóng de jí hé。
duì yú hú wěi zài U， hú tóu zài W de hú suǒ gòu chéng de jí hé chēng zhī wéi gē qiē， yòng（ U， W） biǎo shì。 bǎ gē qiē（ U， W） zhōng suǒ yòu hú de róng liàng zhī hé jiào zuò cǐ gē qiē de róng liàng， jì wéi C（ U， W）， jí：
lì rú tú 5-1 zhōng， lìng U={S,V1}， zé W={V2,V3,V4,T}， nà me
C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=17
dìng lǐ： duì yú yǐ zhī de wǎng luò liú tú， shè rèn yì yī kě xíng liú wéi f， rèn yì yī gē qiē wéi (U,W)， bì yòu： V(f)≤ C(U,W)。
tōng sú jiǎn míng de jiǎng：“ zuì dà liú xiǎo yú děng yú zuì xiǎo gē”。 zhè shì“ liú lǐ lùn” lǐ zuì jī chǔ zuì zhòng yào de dìng lǐ。 zhěng gè“ liú” de lǐ lùn xì tǒng dōushì zài zhè gè dìng lǐ shàng jiàn lì qǐ lái de， bì xū tè bié zhòng shì。
xià miàn wǒ men gěi chū zhèng míng。
wǎng luò liú 、 kě gǎi jìn lù、 gē qiēdōu shì jī chǔ de gài niàn， yīnggāi zhā shí zhǎng wò。 tā men sān zhě zhī jiān zhà yī kàn sì hū fēng mǎ niú bù xiāng gān， qí shí nèi zài lián xì shì shí fēn jǐn mì de。
èr、 qiú zuì dà liú
hé wèi zuì dà liú？ shǒu xiān tā bì xū shì yī gè kě xíng liú； qí cì， tā de liú liàng bì xū dá dào zuì dà。 zhè yàng de liú jiù chēng wéi zuì dà liú。 pì rú duì tú 5-1 ér yán， tā de zuì dà liú rú xià：
xià miàn tàn tǎo rú hé qiú dé zuì dà liú。
zài dìng yì“ kě gǎi jìn lù” gài niàn shí， tí dào kě yǐ tōng guò yī dìng guī zé xiū gǎi“ kě gǎi jìn lù” shàng hú de liú liàng， kě yǐ shǐ dé zǒng liú liàng fàng dà。 xià miàn wǒ men jiù jù tǐ kàn yī kàn shì shénme“ guī zé”。
duì kě gǎi jìn lù P shàng de hú <vi,vj>， fēn wéi liǎng zhǒng qíng kuàng tǎo lùn：
dì yī zhǒng qíng kuàng： <vi,vj> ∈ P+， kě yǐ lìng fij zēng jiā yī gè cháng shù delta。 bì xū mǎn zú fij+delta≤ cij， jí delta≤ cij – fij。
dì 'èr zhǒng qíng kuàng： <vi,vj>∈ P-， kě yǐ lìng fij jiǎn shǎo yī gè cháng shù delta。 bì xū mǎn zú fij-delta ≥ 0， jí delta≤ fij
gēn jù yǐ shàng fēn xī kě yǐ dé chū delta de jì suàn gōng shì：
yīn wéi P+ de měi tiáo hú dōushì fēi bǎo hé hú， P- de měi tiáo hú dōushì fēi líng liú hú， suǒ yǐ delta>0。
róng yì zhèng míng， àn zhào rú cǐ guī zé xiū zhèng liú liàng， jì kě yǐ shǐ suǒ yòu zhōng jiān diǎn dū mǎn zú“ liú liàng shǒu héng”（ jí shū rù liàng děng yú shū chū liàng）， yòu kě yǐ shǐ dé zǒng de liú liàng yòu suǒ zēng jiā（ yīn wéi delta>0）。
yīn cǐ wǒ men duì yú rèn yì de kě xíng liú f， zhǐ yào zài f zhōng néng zhǎo dào kě gǎi jìn lù， nà me bì rán kě yǐ jiāng f gǎi zào chéng wéi liú liàng gèng dà de yī gè kě xíng liú。 wǒ men yào qiú de shì zuì dà liú， xiàn zài de wèn tí shì： cháng ruò zài f zhōng zhǎo bù dào kě gǎi jìn lù， shì bù shì f jiù yī dìng shì zuì dà liú ní？
dá 'àn shì kěn dìng de。 xià miàn wǒ men gěi chū zhèng míng。
dìng lǐ 1 kě xíng liú f shì zuì dà liú de chōng fēn bì yào tiáo jiàn shì： f zhōng bù cún zài kě gǎi jìn lù。
zhèng míng：
shǒu xiān zhèng míng bì yào xìng： yǐ zhī zuì dà liú f， qiú zhèng f zhōng bù cún zài kě gǎi jìn lù。
ruò zuì dà liú f zhōng cún zài kě gǎi jìn lù P， nà me kě yǐ gēn jù yī dìng guī zé（ xiáng jiàn shàng wén） xiū gǎi P zhōng hú de liú liàng。 kě yǐ jiāng f de liú liàng fàng dà， zhè yǔ f shì zuì dà liú máo dùn。 gù bì yào xìng dé zhèng。
zài zhèng míng chōng fēn xìng： yǐ zhī liú f， bìng qiě f zhōng bù cún zài kě gǎi jìn lù， qiú zhèng f shì zuì dà liú。
wǒ men dìng yì dǐng diǎn jí hé U,W rú xià：
（ a） S∈ U，
（ b） ruò x∈ U， qiě fxy<cxy， zé y∈ U;
ruò x∈ U， qiě fyx>0， zé y∈ U。
（ zhè shí jì shàng jiù shì kě gǎi jìn lù de gòu zào guī zé）
（ c） W=VU。
yóu yú f zhōng bù cún zài kě gǎi jìn lù， suǒ yǐ T∈ W； yòu S∈ U， suǒ yǐ U、 W shì yī gè gē qiē（ U,W）。
àn zhào U de dìng yì， ruò x∈ U， y∈ W， zé fxy=cxy。 ruò x∈ W， y∈ U， zé fxy=0。
suǒ yǐ，
yòu yīn v(f)≤ C(U,W)
suǒ yǐ f shì zuì dà liú。 dé zhèng。
gēn jù chōng fēn xìng zhèng míng zhōng de yòu guān jié lùn， wǒ men kě yǐ dé dào lìng wài yī tiáo zhòng yào dìng lǐ：
zuì dà liú zuì xiǎo gē dìng lǐ： zuì dà liú děng yú zuì xiǎo gē， jí maxV(f)=minC(U,W)。
zhì cǐ， wǒ men kě yǐ qīng sōng shè jì chū qiú zuì dà liú de suàn fǎ：
step1. lìng suǒ yòu hú de liú liàng wéi 0， cóng 'ér gòu zào yī gè liú liàng wéi 0 de kě xíng liú f（ chēng zuò líng liú）。
step2. ruò f zhōng zhǎo bù dào kě gǎi jìn lù zé zhuǎn step5； fǒu zé zhǎo dào rèn yì yī tiáo kě gǎi jìn lù P。
step3. gēn jù P qiú delta。
step4. yǐ delta wéi gǎi jìn liàng， gēngxīn kě xíng liú f。 zhuǎn step2。
step5. suàn fǎ jié shù。 cǐ shí de f jí wéi zuì dà liú。
sān、 zuì xiǎo fèi yòng zuì dà liú
1． wèn tí de mó xíng
liú zuì zhòng yào de yìng yòng shì jìn kě néng duō de fēn liú wù zī， zhè yě jiù shì wǒ men yǐ jīng yán jiū guò de zuì dà liú wèn tí。 rán 'ér shí jì shēng huó zhōng， zuì dà pèi zhì fāng 'àn kěn dìng bù zhǐ yī zhǒng， yī dàn yòu liǎo xuǎn zé de yú dì， fèi yòng de yīn sù jiù zì rán cānyù dào jué cè zhōng lái。
tú 5-8 shì yī gè zuì jiǎn dān de lì zǐ： hú shàng biāo de liǎng gè shù zì dì yī gè shì róng liàng， dì 'èr gè shì fèi yòng。 zhè lǐ de fèi yòng shì dān wèi liú liàng de huā fèi， pì rú fs1=4， suǒ xū huā fèi wéi 3*4=12。
róng yì kàn chū， cǐ tú de zuì dà liú（ liú liàng shì 8） wéi： fs1=f1t=5,fs2=f2t=3。 suǒ yǐ tā de fèi yòng shì： 3*5+4*5+7*3+2*3=62。
yī bān de， shè yòu dài fèi yòng de wǎng luò liú tú G=(V,E,C,W)， měi tiáo hú <Vi,Vj> duì yìng liǎng gè fēi fù zhěng shù Cij、 Wij， biǎo shì gāi hú de róng liàng hé fèi yòng。 ruò liú f mǎn zú：
(a) liú liàng V(f) zuì dà。
(b) mǎn zú a de qián tí xià， liú de fèi yòng Cost(f)= zuì xiǎo。
jiù chēng f shì wǎng luò liú tú G de zuì xiǎo fèi yòng zuì dà liú。
2． suàn fǎ shè jì
wǒ men mó fǎng qiú zuì dà liú de suàn fǎ， zhǎo kě gǎi jìn lù lái qiú zuì xiǎo fèi yòng zuì dà liú。
shè P shì liú f de kě gǎi jìn lù， dìng yì wéi P de fèi yòng（ wèishénme rú cǐ dìng yì？）。 rú guǒ P shì guān yú f de kě gǎi jìn lù zhōng fèi yòng zuì xiǎo de， jiù chēng P shì f de zuì xiǎo fèi yòng kě gǎi jìn lù。
qiú zuì xiǎo fèi yòng zuì dà liú de jī běn sī xiǎng shì tān xīn fǎ。 jí： duì yú liú f， měi cì xuǎn zé zuì xiǎo fèi yòng kě gǎi jìn lù jìn xíng gǎi jìn， zhí dào bù cún zài kě gǎi jìn lù wéi zhǐ。 zhè yàng de dé dào de zuì dà liú bì rán shì fèi yòng zuì xiǎo de。
suàn fǎ kě miáo shù wéi：
step1. lìng f wéi líng liú。
step2. ruò wú kě gǎi jìn lù， zhuǎn step5； fǒu zé zhǎo dào zuì xiǎo fèi yòng kě gǎi jìn lù， shè wéi P。
step3. gēn jù P qiú delta（ gǎi jìn liàng）。
step4. fàng dà f。 zhuǎn step2。
step5. suàn fǎ jié shù。 cǐ shí de f jí zuì xiǎo fèi yòng zuì dà liú。
zhì yú suàn fǎ de zhèng què xìng， kě yǐ cóng lǐ lùn shàng zhèng míng。 dú zhě kě zì jǐ sī kǎo huò chá yuè yòu guān yùn chóu xué zī liào。
2． zuì xiǎo fèi yòng kě gǎi jìn lù de qiú jiě
qiú“ zuì xiǎo fèi yòng kě gǎi jìn lù” shì qiú zuì xiǎo fèi yòng zuì dà liú suàn fǎ de guān jiàn zhī suǒ zài， xià miàn wǒ men tàn tǎo qiú jiě de fāng fǎ。
shè dài fèi yòng de wǎng luò liú tú G=(V,E,C,W)， tā de yī gè kě xíng liú shì f。 wǒ men gòu zào dài quán yòu xiàng tú B=(V ’ ,E’ )， qí zhōng：
1、 V’ =V。
2、 ruò <Vi,Vj>∈ E， fij<Cij， nà me <Vi,Vj>∈ E’， quán wéi Wij。
ruò <Vi,Vj>∈ E， fij>0， nà me <Vj,Vi>∈ E’， quán wéi -Wij。
xiǎn rán， B zhōng cóng S dào T de měi yī tiáo dào lù dōuduì yìng guān yú f de yī tiáo kě gǎi jìn lù； fǎn zhī， guān yú f de měi tiáo kě gǎi jìn lù yě néng duì yìng B zhōng cóng S dào T de yī tiáo lù jìng。 jí liǎng zhě cún zài yī yī yìng shè de luó ji guān xì。
gù ruò B zhōng bù cún zài cóng S dào T de lù jìng， zé f bì rán méi yòu kě gǎi jìn lù； bù rán， B zhōng cóng S dào T de zuì duǎn lù jìng jí wéi f de zuì xiǎo fèi yòng kě gǎi jìn lù。
xiàn zài de wèn tí biàn chéng： gěi dìng dài quán yòu xiàng tú B=(V’ ,E’ )， qiú cóng S dào T de yī tiáo zuì duǎn lù jìng。
kǎo lǜ dào tú zhōng cún zài quán zhí wéi fù shù de hú， bù néng cǎi yòng Dijkstra suàn fǎ； Floyd suàn fǎ de xiàolǜ yòu bù jìn rú rén yì héng héng suǒ yǐ， zhè lǐ cǎi yòng yī zhǒng zhé zhōng de suàn fǎ： dié dài fǎ。
shè Short[k] biǎo shì cóng S dào k dǐng diǎn de zuì duǎn lù jìng cháng dù； cóng S dào dǐng diǎn k de zuì duǎn lù jìng zhōng， dǐng diǎn k de qián qū jì wéi Last[k]。 nà me dié dài suàn fǎ miáo shù rú xià：（ wèile biàn yú miáo shù， lìng n=|V’ |， S de biān hào wéi 0， T de biān hào wéi n+1）
step1. lìng Short[k]+∞（ 1≤ k≤ n+1）， Short0。
step2. biàn lì měi yī tiáo hú <Vk,Vj>。 ruò Short[k]+<k,j><Short[j]， zé lìng Short[j]Short[k]+<k,j>， tóng shí Last[j]k。 cháng bù cún zài rèn hé yī tiáo hú mǎn zú cǐ tiáo jiàn zé zhuǎn step4。
step3. zhuǎn step2.
step4. suàn fǎ jié shù。 ruò Short[n+1]=+∞， zé bù cún zài cóng S dào T de lù jìng； fǒu zé kě yǐ gēn jù Last jì lù de yòu guān xìn xī dé dào zuì duǎn lù jìng。
yī cì dié dài suàn fǎ de shí jiān fù zá dù wéi O(kn2)， qí zhōng k shì yī gè bù dà yú n de biàn liàng。 zài fèi yòng liú de qiú jiě guò chéng zhōng， k dà bù fēn qíng kuàng xià dū yuǎn xiǎo yú n。
3． sī wéi fā sàn yǔ tàn suǒ
1） kě gǎi jìn lù fèi yòng：“ dì zēng！ dì zēng？”
shè f cóng líng liú dào zuì dà liú gòng bèi gǎi jìn liǎo k cì， měi i cì xuǎn zé de kě gǎi jìn lù de fèi yòng wéi pi， nà me huì bù huì yòu p1≤ p2≤ p3≤……≤ pk ní？
2） dié dài fǎ：“ xiǎo xīn sǐ xún huán！ hēi hēi……”
dié dài fǎ huì chū xiàn sǐ xún huán má？ yě jiù shì shuō， gòu zào de dài quán yòu xiàng tú B zhōng huì cún zài fù huí lù má？
3） fèi yòng：“ nǐ zài hū wǒ shì fù shù má？”
wǎng luò liú tú zhōng de fèi yòng kě yǐ xiǎo yú líng má？
4） róng liàng：“ wǒ guǎn de kě bù jǐn shì hú。”
wǎng luò liú tú zhōng de“ róng liàng” dōushì duì hú 'ér yán de， dàn ruò shì gěi měi gè dǐng diǎn yě jiā shàng yī gè róng liàng xiàn zhì： jí tōng guò cǐ dǐng diǎn de liú liàng de shàng xiàn； rèn wù réng rán shì qiú cóng S dào T de zuì xiǎo fèi yòng zuì dà liú。 nǐ néng jiě jué má？
sì、 yòu shàng xià jiè de zuì dà liú
shàng miàn tǎo lùn de wǎng luò liú dū zhǐ duì měi tiáo hú dū xiàn dìng liǎo shàng jiè（ qí shí qí xià jiè kě yǐ kàn chéng 0）， xiàn zài gěi měi tiáo hú <Vi,Vj> jiā shàng yī gè xià jiè xiàn zhì Aij（ jí bì xū mǎn zú Aij≤ fij）。
lì rú tú 5-9：
hú shàng shù zì duì dì yī gè shì shàng jiè， dì 'èr gè shì xià jiè。 ruò shì piē kāi xià jiè bù kàn， cǐ tú de zuì dà liú rú tú 5-10(a) suǒ shì， liú liàng shì 6； dàn ruò shì jiā rù liǎo xià jiè de xiàn zhì， tā de zuì dà liú liàng jiù zhǐ yòu 5 liǎo， jù tǐ fāng 'àn jiàn tú 5-10(b)。
nà me yòu shàng xià jiè de wǎng luò zuì dà liú zěn me qiú ní？
yī zhǒng zì rán de xiǎng fǎ shì qù diào xià jiè， jiāng qí zhuǎn huà wéi zhǐ hán shàng jiè de wǎng luò liú tú。 zhè zhǒng měi hǎo de yuàn wàng shì kě yǐ shí xiàn de。 jù tǐ fāng fǎ rú xià：
shè yuán wǎng luò liú tú wéi G=(V,E,C,A)， gòu zào bù hán xià jiè de wǎng luò liú tú G’ =(V’ ,E’ ,C’ )：
1、 V’ =V ∪ {S’ ,T’ }
2、 duì měi gè dǐng diǎn x， lìng， ruò h-(x) ≠ 0， jiù tiān jiā yī tiáo hú <S’ ,x>， qí shàng jiè wéi h-(x)。
3、 duì měi gè dǐng diǎn x， lìng， ruò h+(x)≠ 0， jiù tiān jiā yī tiáo hú <x,T’ >， qí shàng jiè wéi h+(x)。
4、 duì yú rèn hé <Vi,Vj>∈ E， dōuyòu <Vi,Vj>∈ E’， qí shàng jiè C’ ij=Cij– Aij。
5、 xīn zēng <T,S>∈ E’， qí shàng jiè CTS=+∞。
zài G’ zhōng yǐ S’ wéi yuán diǎn、 T’ wéi huì diǎn qiú dé zuì dà liú f’。 ruò f’ zhōng cóng S’ fā chū de rèn yì yī tiáo hú shì fēi bǎo hé hú， zé yuán wǎng luò liú tú méi yòu kě xíng liú。 fǒu zé kě dé yuán tú de yī gè kě xíng liú f=f’ +A， jí suǒ yòu de fij=f’ ij+Aij。（ qí zhèng què xìng hěn róng yì zhèng míng， liú gěi dú zhě wán chéng）
rán hòu zài qiú kě gǎi jìn lù（ fǎn xiàng hú <Vi,Vj> bì xū mǎn zú fij≥ Aij， ér fēi fij≥ 0）， bù duàn fàng dà f， zhí dào qiú chū zuì dà liú。
wǒ men kàn dào， shàng jǐ jié suǒ tǎo lùn de yī zhǒng kě xíng wǎng luò liú shí jì shàng shì {Aij=0} de yī zhǒng tè shū wǎng luò liú ， zhè lǐ tí chū de mó xíng gèng yī bān huà liǎo。 jiě jué yī bān huà de fù zá wèn tí， wǒ men cǎi qǔ de sī lù shì jiāng qí zhuǎn huà wéi tè shū de jiǎn dān wèn tí， jiā yǐ yán jiū、 tuī guǎng， jìn 'ér jiě jué。 zhè shì yī zhǒng zhòng yào de jī běn sī xiǎng： huà guī héng héng jiǎn dān yòu xiào。 jī yú zhè zhǒng sī xiǎng， qǐng dú zhě zì xíng sī kǎo jiě jué：
1、 yòu shàng xià jiè de zuì xiǎo liú。
2、 yòu shàng xià jiè de zuì xiǎo fèi yòng zuì dà liú。
wǔ、 duō yuán diǎn、 duō huì diǎn de zuì dà liú
yǐ zhī wǎng luò liú tú yòu n gè yuán diǎn S1、 S2、……、 Sn， m gè huì diǎn T1、 T2、……、 Tm，， qiú gāi tú de zuì dà liú。 zhè yàng de wèn tí chēng wéi duō yuán diǎn、 duō huì diǎn zuì dà liú。
tā de jiě jué hěn jiǎn dān：
1、 zēng shè yī gè“ chāo jí yuán” S’， duì měi gè yuán diǎn Si， xīn zēng hú <S’ ,Si>， róng liàng wéi wú qióng dà。
2、 zēng shè yī gè“ chāo jí huì” T’， duì měi gè huì diǎn Ti， xīn zēng hú <Ti,T’ >， róng liàng wéi wú qióng dà。
3、 yǐ S’ wéi yuán diǎn、 T’ wéi huì diǎn qiú zuì dà liú f。
4、 jiāng f zhōng de S’ hé T’ qù diào， jí wéi yuán tú de zuì dà liú。
suàn fǎ zhèng què xìng xiǎn rán。
liù、 dǐng diǎn yòu róng liàng xiàn zhì de zuì dà liú
shàng yī jié yǐ jīng tí chū liǎo zhè gè wèn tí， jí duì yú jìn chū měi gè dǐng diǎn de liú liàng yě guī dìng yī gè shàng xiàn， zhè yàng de zuì dà liú rú hé qiú？
jì rán wǒ men yǐ jīng jiě jué liǎo“ biān xiàn zhì” wèn tí， xiàn zài hé bù bǎ“ diǎn xiàn zhì” wèn tí zhuǎn huà wéi“ biān xiàn zhì” ní？ jù tǐ bàn fǎ rú xià：
1、 duì chú yuán diǎn hé huì diǎn zhī wài de měi gè dǐng diǎn i chāi fēn chéng liǎng gè dǐng diǎn i’ hé i’’。 xīn zēng yī tiáo hú <i’ ,i’’ >， qí róng liàng wéi diǎn i de liú liàng xiàn zhì。
2、 duì yú yuán tú zhōng de hú <i,j>， wǒ men jiāng qí biàn huàn chéng <i’’ ,j’ >。
3、 duì biàn huàn hòu de tú qiú zuì dà liú jí kě。
zhè lǐ wǒ men yòu yī cì yùn yòng dào liǎo huà guī de sī xiǎng： jiāng wèi zhī de“ diǎn xiàn zhì” wèn tí zhuǎn huà wéi yǐ zhī de“ biān xiàn zhì” wèn tí。
qī、 wǎng luò liú yǔ 'èr bù tú de pǐ pèi
{ èr bù tú hé pǐ pèi de dìng yì kě cān jiàn běn shū zhuān mén jiè shào 'èr bù tú pǐ pèi de zhāng jié }
shè 'èr bù tú wéi G=(X,Y,E)。
zēng shè diǎn S’， duì yú suǒ yòu i∈ X， xīn zēng hú <S’ ,Xi>， róng liàng wéi 1； zēng shè diǎn T’， duì yú suǒ yòu i∈ Y， xīn zēng yī tiáo hú <Yi,T’ >， róng liàng yě wéi 1。 yuán tú zhōng suǒ yòu de hú yú yǐ bǎo liú， róng liàng jūn wéi +∞。 duì xīn gòu zào chū lái de wǎng luò liú tú yǐ S’ wéi yuán diǎn、 T’ wéi huì diǎn qiú zuì dà liú： liú liàng jí wéi zuì dà pǐ pèi shù； ruò hú <Xi,Yj>（ i∈ X， j∈ Y） de liú liàng fēi líng， tā jiù shì yī tiáo pǐ pèi biān。
èr bù tú zuì dà pǐ pèi wèn tí jiě jué。
nà me 'èr bù tú de zuì jiā pǐ pèi wèn tí yòu rú hé？
réng rán 'àn zhào shàng shù fāng fǎ gòu tú。 tóng shí lìng yuán tú zhōng hú de fèi yòng bǎo chí bù biàn； xīn zēng hú de fèi yòng zhì wéi 0。 rán hòu yǐ S’ wéi yuán diǎn、 T’ wéi huì diǎn qiú zuì xiǎo fèi yòng zuì dà liú jí kě。 zuì dà liú de fèi yòng jí wéi yuán 'èr bù tú zuì jiā pǐ pèi de fèi yòng。
bā、 wǎng luò liú de yìng yòng（ lüè） | | wangluoliu
wǎng luò liú
networkflows
tú lùn zhōng yī zhǒng lǐ lùn hé fāng fǎ， yán jiū wǎng luò shàng de yī lèi zuì yōu huà wèn tí。 T.E. hā lǐ sī yú 1955 nián yán jiū tiě lù wǎng de zuì dà tōng guò néng lì shí shǒu xiān tí chū， zài yī gè gěi dìng de wǎng luò shàng xún qiú mǒu liǎng diǎn jiān de zuì dà yùn shū liàng wèn tí。 1956 nián， L.R. fú tè hé D.R. fù 'ěr kè sēn gěi chū liǎo suàn fǎ， cóng 'ér jiàn lì liǎo wǎng luò liú lǐ lùn。
zài wǎng luò liú wèn tí zhōng， wǎng luò shì yóu yī gè yòu xiàng tú □＝ (□，□ ) hé yī gè dìng yì zài hú jí□ shàng de yǐ zhī fēi fù hán shù□ suǒ zǔ chéng， qí zhōng diǎn jí□ zhōng yòu liǎng gè zhǐ dìng de diǎn□□□ hé□□ , fēn bié chēng wéi fā diǎn hé shōu diǎn , ér□ zhōng qí tā de diǎn dū chēng wéi zhōng jiān diǎn；□ chēng wéi wǎng luò de róng liàng hán shù。 yòng□□ biǎo shì hán shù□ zài hú□＝ (□□，□□ ) shàng de hán shù zhí , bìng chēng zhī wéi hú (□□ ,□□ ) de róng liàng。
shè□ shì dìng yì zài jí hé□ shàng de fēi fù hán shù。 yòng□□□ biǎo shì□ zài hú□ =(□□ ,□□ ) shàng de hán shù zhí , bìng chēng wéi zài hú□ shàng cóng□□ dào□□ de liú liàng。 ruò hán shù□ mǎn zú yǐ xià liǎng gè tiáo jiàn , zé chēng hán shù□ wéi wǎng luò shàng de liú , jiǎn chēng wǎng luò liú ： ① zài měi yī tiáo hú shàng， liú liàng□□□ bù chāo guò róng liàng□□ , jí 0≤□□≤□□； ② zài rèn hé yī gè zhōng jiān diǎn□□ shàng， cóng□□ liú chū de zǒng liú liàng děng yú liú rù□□ de zǒng liú liàng， jí□， shì zhōng□ shì duì suǒ yòu yǐ□□ wéi qǐ diǎn de hú qiú hé ,□ shì duì suǒ yòu yǐ□□ wéi zhōng diǎn de hú qiú hé。 tiáo jiàn② chēng wéi liú de píng héng tiáo jiàn。
duì rèn yì gěi dìng de liú□ , yì jiàn， fā diǎn de jìng chū liàng děng yú shōu diǎn de jìng shōu liàng， jí□。 jìng chū liàng shì zhǐ cóng□□ liú chū de zǒng liú liàng jiǎn qù liú rù□□ de zǒng liú liàng de chā； jìng shōu liàng shì zhǐ cóng□□ liú rù de zǒng liú liàng jiǎn qù cóng□□ liú chū de zǒng liú liàng de chā。 yǐ□ (□ ) biǎo shì□□ de jìng chū liàng huò□□ de jìng shōu liàng， bìng chēng wéi□□ ( zài wǎng luò shàng ) de liú liàng。 rú tú 1 wǎng luò liú zhōng de a biǎo shì yī gè wǎng luò， jiàn tóu biǎo shì hú de fāng xiàng , hú shàng de shù biǎo shì róng liàng。 b、 c biǎo shì wǎng luò a shàng de liǎng gè liú， hú shàng de shù zì biǎo shì gāi hú de liú liàng。 b de liú liàng wéi 4， c de liú liàng wéi 5。
yóu wǎng luò zhōng de diǎn zǔ chéng de xù liè□ ruò duì měi yī duì xiāng jì diǎn□□、□□ huò zhě (□□ ,□□ ) huò zhě (□□ ,□□ ) shì wǎng luò zhōng de hú , zé chēng□ shì yī tiáo lián jié□□ dào□□ de liàn。 shè□ shì yī tiáo lián jiē□□ dào□□ de liàn , cóng□□ chū fā， yán□ zǒu dào□□ shí， zé liàn□ zhōng yǔ zǒu xiàng yòu xiāng tóng fāng xiàng de hú chēng wéi qián xiàng hú； yòu xiāng fǎn fāng xiàng de chēng wéi hòu xiàng hú。 rú guǒ duì yú gěi dìng de liú□ , tā zài□ de měi tiáo qián xiàng hú shàng de liú liàng dū xiǎo yú róng liàng， zài měi tiáo hòu xiàng hú shàng de liú liàng dōudà yú líng， zé chēng liàn□ shì guān yú liú□ de yī gè zēng guǎng liàn。 lì rú， zài tú 1 wǎng luò liú b zhōng ,□＝ {□□ ,□□ ,□□ ,□□ ,□□ } shì yī gè zēng guǎng liàn。 (□□ ,□□ )、 (□□ ,□□ ) shì qián xiàng hú， qí shàng de liú liàng dū xiǎo yú róng liàng； (□□ ,□□ ),(□□ ,□□ ) shì hòu xiàng hú， qí shàng de liú liàng dōudà yú líng。 rú guǒ zài cǐ zēng guǎng liàn de qián xiàng hú shàng， liú liàng dū zēng jiā 1, hòu xiàng hú shàng liú liàng dū jiǎn shǎo 1， jiù kě cóng b biàn dào c， cóng 'ér shǐ liú liàng cóng 4 zēng jiā dào 5。
zài wǎng luò shàng xún qiú yī gè shǐ liú liàng□ (□ ) dá dào zuì dà de liú□， chēng zhī wéi wǎng luò zuì dà liú wèn tí。 tā shì wǎng luò liú lǐ lùn zhōng de yī gè zhù yào yán jiū kè tí , yǐ huò dé yī xiē zhòng yào jiēguǒ：① liú□ shì zuì dà liú de chōng fēn bì yào tiáo jiàn shì , bù cún zài guān yú□ de zēng guǎng liàn。 cóng 'ér jiāng xún qiú zuì dà liú wèn tí huà wéi pàn duàn yòu wú zēng guǎng liàn wèn tí。 yì jiàn， tú 1 wǎng luò liú zhōng de b bù shì zuì dà liú。 fú tè hé fù 'ěr kè sēn tí chū liǎo yī zhǒng biāo hào fǎ， jí duì wǎng luò shàng de diǎn gěi yǐ biāo hào， cóng□□ chū fā yán wǎng luò shàng de hú xiàng□□ tàn xún zēng guǎng liàn de fāng fǎ。② ruò gè hú shàng de róng liàng dōushì zhèng zhěng shù， zé bì cún zài gè hú shàng de liú liàng dōushì zhěng shù de zuì dà liú。 ③ shè□ shì hán yòu□□ ér bù hán□□ de diǎn jí ,(X,□ ) biǎo shì qǐ diǎn zài□ zhōng 'ér zhōng diǎn bù zài□ zhōng de hú de jí hé， bìng chēng wéi fēn lí□□ hé□□ de jié jí， jiǎn chēng jié jí。 wǎng luò zhōng qù diào yī gè jié jí hòu , jiù méi yòu cóng□□ dào□□ de dìng xiàng liàn。 (X,□ ) zhōng suǒ yòu hú de róng liàng zhī hé , chēng wéi zhè gè jié jí de jié liàng , jì zuò□ (X,□ )。 shǐ jié liàng zuì xiǎo de jié jí chēng wéi zuì xiǎo jié jí。 wǎng luò liú lǐ lùn zhōng yòu yī gè jī běn de duì 'ǒu dìng lǐ : zuì dà liú de liú liàng děng yú zuì xiǎo jié jí de jié liàng。 tú 1 wǎng luò liú de c shì yī gè liú liàng dá dào zuì dà de liú（ liú liàng wéi 5）， jié jí {(□□ ,□□ ),(□□ ,□□ )} shì yī gè zuì xiǎo jié jí（ jié liàng wéi 5） , zhè lǐ□＝ {□□ ,□□ }。
zuì xiǎo fèi yòng liú wèn tí shì cháng jiàn de yī lèi zhòng yào de | | - : Network Flow
| | | jīng jì xué | suàn fǎ | guǎn lǐ xué | |
| | | wǎng luò liú liàng | wǎng luò liú máng | | wǎng luò liú xíng | wǎng luò liú yán | | wǎng luò liú liángqì | wǎng luò liú méi tǐ | | wǎng luò liú xíng zì | wǎng luò liú xíng yǔ | | wǎng luò liú xíng cí | wǎng luò liú lǐ lùn | | wǎng luò liú tōng liàng | zēng yì wǎng luò liú | | wǎng luò liú liàng fēn xī | wǎng luò liú liàng kòng zhì | | wǎng luò liú xíng yòng yǔ | wǎng luò liú xíng cí huì | | wǎng luò liú liàng guǎn lǐ | wǎng luò liú xíng yǔ yán | | wǎng luò liú xíng xīn cí | wǎng luò liú liàng jiān kòng | | wǎng luò liú liàng guǎn lǐ qì | wǎng luò liú liàng jiān kòng qì | | wǎng luò liú liàng kòng zhì qì | wǎng luò liú liàng jiān shì qì | | wǎng luò liú liàng fēn xī gōng jù | wǎng luò liú liàng jiān cè yǔ kòng zhì | | shí yòng wǎng luò liú liàng fēn xī jì shù | wǎng luò liú liàng jiān kòng v3.0 | | wǎng luò liú liàng jiān shì qì v1.1 | 1. wǎng luò liú xíng yǔ | | tōng xìn wǎng luò liú liàng kòng zhì yǔ jī lì jià kòng cè lüè yán jiū | nettank-- wǎng luò liú liàng fēn xī gōng jù v1.0 | |
|
|
|