当前位置:首页 >> 学科竞赛 >> 2015中国国家集训队论文

2015中国国家集训队论文


f!?

? ?{9?A^

?g?? ? ?

f!?

?

?{9?A^
?

?g?? ?

? ?
? ? ? ?{?&E??m?~^ o(§oN????? ?{§kX2? ??? ? A^" ?é? ?{?1 ü??§z??k0

??? ‰{§2???J????? ‰{§?J? ? ???A^"

1

?

k'??
? G = (V, E )§?? V ?:8§ E ?>8" : >8 M ( M ∈ E ) ??ù?? ??? " ???> ê?§>ê?? ? >???? > ???? " >" à:" 3? ? : ?

3???§ ?????

?|üüvkú

??>‘ ?§> ??? ? ??? ? " ? ? >??? >§?3? ? ·????:3? ?§ …= ??? :§?3? ? :???X:" AO/§¤k:??? : ? §?? éu? X?A?`?§ ? " ó" ? ?^> (u, v)§·?? u ? v p? §?,^?

e5?^ n 5L?? :ê§m 5L?? >ê"

2015c&E?c

???II[è??è

??

1

f!?

? ?{9?A^

?g?? ? ?

2

O2?
P ????^{ü??§XJ÷v? 1. P ?:! ?:???X:" > ??y"

2. P ?L >?? >! ?? K? P ??^O2?" AO/§·?r÷v^? 2 O2???? ? >'?

{ü????

O?" ? 1 §K c?

>ê?? 1§XJrù^?? ¤k:?ò???

+1 …?,?{" ·??rO2? ?ù?L§?O2" ÷O2?O2§??? :§???O2 ù?L§ 8?"

???*?? : ?n 1. ??? y? 1.

M ?? G

??? §??^?? G ???3O2?"

du ?O2?? ? ?? M ????? ? ??? >?O5g M ? M "

+1§7?5 y" M é? D = M ⊕ M = ( M ∪ M ) \ ( M ∩ M )" ?ê–?? 2§…?? 2 > :ü^

???±í? D ?z?:

ù`? D deZ?! ó|¤§…z??! ó? M, M O??????óê§?? M, M ? ¤k >?y ?? > ê???"

O?y" z?

O?§d?ATEk | M | > | M |§K D ????3?^ M ? Oó§Tóéu M 5`???^O2?" ? §??kO2?§??5 ??????? é? O2?" l?X: x ?u O2?§KO2?g §?, y"

?d§???3?? d???n·??±

?{?e?zgq???¤k

?X:§éO2??O2§? ??§XJ,?gé? vkl x ?u O2?"
1

r???

?

>C¤??

>! ??

>C¤?

>" ?

???B§

??

/r?

?

?0 ! /r????0??ù??g"

2015c&E?c

???II[è??è ??

2

f!?

? ?{9?A^

?g?? ? ?

b

,??÷O2? a ? b O2

§ ?y

± x ??:

O2? P x § K P x O?§ ,?:§ a, b ?

?????? a ? b k " ?? P x 1?g-??? a ? b§du a ? b ? K>:üà >a.??§ù??X3O2c x ???Ur =,??X:§`?3d?c????3l x ?u O2?§g?"

^ù?(??±é???{?e???`z?q?z??X:§?é?g l§?u O2?"

2015c&E?c

???II[è??è

??

3

f!?

? ?{9?A^

?g?? ? ?

3
3.1
3.1.1

?????
? ?{

O2??{
???B§·?r ?? :?¤?! mü??§¤k>????? ?:?:?????mü?§?”l?> >! 1óêgr? >" ?k???§l‰? >§ù`?? m

? m "

??O2?????ê§?? z??X:éO2?" 5?

O2??1?êgr?? >! m ?r ???

r ????

?d·??±‰ 0 du/U ‰

??U??????§?KC¤

?:é?^{ü??r ????

,??X:" ?Juyk???/U?L{ü??r

r 0 §?d?I'%??5?K" § q??>???X: u§ l u m? DFS§ z?:P?? é ,??X:?(?H{" E,?? O(m)"

?–?IP§± y–?–??g§ ?dé?gO2?

?é O2??§·????

DFS ??

??" "

???q? O(n) ??X:§???{

oE,?? O(nm)

3.1.2

Dinic ????
????? ?±=z? ?6 ."

2015c&E?c

???II[è??è

??

4

f!?

? ?{9?A^

?g?? ? ?

#? l§ 5



??>z?:?N?? 1 m?N?? 1

l§ m>z?:???N?? 1

z^>l?

l" ??? " g ?§

??6=???? §?m ÷6>éA ?? >" √ ·??^ Dinic ?{ 1 §?±3 O(m n) ?mE,?S? ù?E,??X? Dinic ? { éu O(m)" ?? 1 ??^ O(nm) ? Q? z ? ? ? ? ü ?" 1 ? ? ? ^ O(m) ?m DFS ?1??O2" .§duz^>N??? 1§1 ? DFS

? m BFS ? á

E,??±‰

√ √ éuc n ?§oE,?? O(m n)" √ n ? §?? Dinic ?{z??-? g? S √ ??4O 2 §@oz^O2? ????áu n" ??? §????? ? c? é?

T

?áO2??l?

§=eZ?p?? O √ ?! Oó" z?^ OóéA?^O2?§??– ? n§?dù ó √ ê???L n ^" √ ù??X c? ?? O( n) ^O2?§??? e5 Dinic ???? √ √ ?1 O( n) ?§oE,?? O(m n)"
1

??

?6?{§??

??ê????T?{§?u???3d?m?[0 )?á " ?§ Dinic ??

§?

)

???±????] g1?S" 2 ^?y{?±y?÷?á?O2?g?? O2?? ?O2 § e5???k??

.??X

c??

2015c&E?c

???II[è??è ??

5

f!?

? ?{9?A^

?g?? ? ?

3.2

?

??
M, M ?ü??? O?! ??? §- D ? M, M é? " §?! ó? ó ó! Oó|¤§…du M, M ????? Oó“LkO2?¤ " § ? ? ? ? ± ? L ? ? ?e Z ? ? ?keZ??

????§ K D deZ

???óê????ê ó? ,??" ?

ù ` ?§ ? ? ü ? ? ? ? AO/§ü? ?????óê

é?

O?" ??,?? ? "

Oó § ó

,à:ò¤??X:§`???

3.2.1

?????

'…:
? :" '…:" :" ?? M ? D = M ⊕ M §K '…:d?????? ??? …= § é?

'…:?? ??3??? du ??? k???????? : p§

???mü??é? §·????é?? M § ?é M ?,???? p : s UC¤?? :§

D ????3?^± p ?à: @o??? >?u ·? ? ?????¤ " L5??§k‰ Oó§?

ó Oó§ù^ó,?à?3 M ?" lù?:?uUé?^±?

?:?,??X: t" duó??óê§t ? s áu? ?????? ?@ >lm ?! ?? >l? m§

l??z??X:?u DFS§‰ ,? O(n + m)"

:??IP" ????z?vkIP

:=?'…:" ???'%??5§w,z?:?I–?–??g§E

3.2.2

?????

'…>
?" ?3,????

·?I?é

= >??3??? M?

? /§k???????? '…>???? ?e ??? M, M ó O?" M" é?

M"

>§éu?^> e(e ∈ M )§b

?§e ???3§K?oáu??ó

Oó! ?oáu??

2015c&E?c

???II[è??è

??

6

f!?

? ?{9?A^

?g?? ? ?

éuó L O?r éuó m ??=?" ?'…:"



??§ó

,?à????X:§`? e

,?à:U?

?X:§=,?à:??'…:" ?d?I O? ??§·?‰ ?????? >l?

? e üà???3 m! ?? >l

?§2u? e ??3,????????3??¤ " ^ Tarjan ?{?r?? ??E,?§I?k O(n + m) ?'…:§2 O(n + m) ^ Tarjan ?{?r?

???"

3.2.3

?????á8
:§÷vüü?mvk>??" M § ??? ??§ M ? >üüvkú ? –??

???á8?`§??? ·??? :§ n ? | M |" e50 ?? b ???^? ?? ??? z^>üà:–

k???3?á8?§?d???á8 ???á8 ?{" ? ?.§e ???

E?? ? n ? | M |

???? ??? ??

M§kr¤k?X:\\???á8" 4?á8? üà: u, v k m0 >e ?üw xe ?á8?§?”rù?/ ?>·??±

> e = (u, v)§?

…=k???\\ ??'X" r x1?| M| ?m ?? ? xe

‰??C? xe §?Lq? u, v

xe é???

??'X???5

§2q?z??X: t§du t ?? ¤k? :¤3 ? >e C

???á8? ?ò (?"

§@o? t k>?? )g?Q?

ù ??5

í ????

XJ )g?§@o???X?¤?

???

2015c&E?c

???II[è??è ??

7

f!?

? ?{9?A^

?g?? ? ?

ù?

L??

>§7? ? x

L? >?

??

???á8?

?X:§??

?u)g?§??L?m ?@?7:í ?5? > ù??Xé ?d§·??á ?X:?? ??(? ·? í xe xe gd

??'X5D4

§f7?L??Je

?§u??u)g?" ù?^???" x ?(? § ? ?? ?e >?

?^O2?§? M ???? x1?| M| ? ?" ?í

í ???3g?" ù ??±D? §lz?

> e m? DFS§rU(?

??:ê? O(| M |) = O(n) "

>??Lq?

?5 §¤±? O(m)

?d??? ?????á8 ?????á8??±? ??! m> ^

?mE,?? O(n + m)" ?6? ? ??§?> :3 S 8L

:3 T 8L??§@o?mk>?? g,?I??K "

ù?`?? ???§???á8 = n - ??? "

3.2.4

???

:CX
:§÷vz^>?– k??à: ?" ?8?

? :CX?`§?? ?:CX"

?????Juy???:CX @o3¤k:? K???á8§

?8???á8! ???á8 ??? :CX"

ù?`?? ???§? :CX = n - ???á8"

3.2.5
?

???

i;S

?
m> : ? ?§

i ; S ? ?? - matchi L ? ? ? > 1 i ? : ? i;S" ? é? ? " ???eZ? L§??ü? %

? z match1?nL ?cJ

O?" @o·?

k???????? §=?? ??i;S matchu" ·?l U?¤??

g ?§ U ? ? l

?q??>z?: u 5?? : v§ z g I ? u ???? > (u, v) du?>

?q?m>z?? u k>?? >" e???

>Kw,U??K§‰

2015c&E?c

???II[è??è

??

8

f!?

? ?{9?A^

?g?? ? ?

(u, v) ??3???p§=?? u, v ??áu??r????§XJ?K`?U! ?`??U" é u ? ? z ? : u§ é matchu = v ? é ?{ v ? U? v =?(?? ' X" ? ? §? “?2g ?U§·??”r u! v l ???í " §é O?^ DFS ? O(m) "

'X??C? O(n) g§?d?I? O(n) gr????" éu,? u§

?d?mE,?? O(nm)"

3.3

A^
·?? ~? 3 ???§??? ?? .k? =? :CX = n - ???á8" ?x/?§??Uy????? ?\K @o ?? . ???K?U)?" 1 ! <?

? " ù?aK8??~?§?&?????Lé?§3d??1o( ?" e?0 ? g? ?|? ??? K8"

3.3.1
K?

Problem 1. Chessboard
1

k?? n × n ?u,
1

?
5

? n ??§\?ò n ?????

??

z1z

?–

?k???" n ≤ 10 " ?§z?? ?I‰???3???/??S"

5

?POJ ]?m Round 2 - by sumix173

2015c&E?c

???II[è??è ??

9

f!?

? ?{9?A^

?g?? ? ?

?\??= ? {? K) ?kK? ? ?" ·??á

????(? "

x, y ?I??á §·??w?‘" P§êi x ?y ???3 [L x , R x ]§?= êi?y

?KC¤??ü

??§?>éAêi§m>éAü u??= /'…>0?K" ????k

?§?>z?:?m>

???m :?>" ·? ù??cJ L 5??

>??3??? ?" ? " ? ? ? ` /? ' … :0 §‰ ? ? ? ??? :¤3 > ? ?!

y k )§ ù ?

ù ? ? ? ± ? ?" @ o · ? ? I ? ” ? c ` ?? >?m¤ §, ?u 1§`?ù?: ¤“L êi ?z^>??3?p"

·?^ Tarjan ?r????§XJ??L?êi ??(?"

r?????

?>3?S§`?ù^?>??/'…>0 § =ù?: :?á???( 5

du??m?>§q?'%??5§?±^ém> `z?>§ù >ê? O(n log n) –u , K ? ? " § ù????;

%?K§=¤kêiU L üS êi§= ?|?Y"

l? mq?z? ?§zgW\ R ? ?mE,? O(n log n)"

2015c&E?c

???II[è??è ??

10

f!?

? ?{9?A^

?g?? ? ?

3.3.2
K?

Problem 2. Minimum Diameter
1

‰??? n(n ≤ 1000) ?:§í??? k(k < n, k ≤ 30) ?:§? ???? K) q??e5 :p??? ± |ab| ???§a, b ? ü?: a, b" %x " :é?C"

?e

:

@o?e

: x I?÷v | xb|, | xa| ≤ |ab|§?????3ü 8S :?é ¤ k ? l > |ab| 3 :§u

8S?" :é§ ? ? >§ ?eí? :o

e 5§ · ? 3 ü ê?? ≤ k =?" 5? z^>????

L??U???" ???á8=?S???U ü 8 ü?

?? ab§?????S?? > k ?§`????á8 ??ù??

3?l > |ab|

:é" ¤±ù?S????

?????á8?K" §?d?±?

du???á8 = n - ??? § " é?gO2?? O(m) = O(n2 ) ??cq? a, b ???|?"
1

uy???

< n ? k§`?I?<r?L k ?:§ù???1

§–?é k gO2??????{" 2? ?????‘??O ?? ?{§g

E,?§o?mE,? O(kn4 )"

?+ù?E,??U?LdK§

5

?CodeForces VK Cup 2012 Round 3 D

2015c&E?c

???II[è??è ??

11

f!?

? ?{9?A^

?g?? ? ?

‰{du??K'X??…?u??3d?

\??§k,

??

?±???P“ 2012 cg?K)K w?????z¤ "

3.3.3
K?

Problem 3. The Square Div One
1

? ? n × m(n, m ≤ 50) ê§? ?i;S? K)

?

§ \ I ? ‰ z ?? f W ? 1 ? max(n, m) Uk1 ^S¤

z1z ??3-Eêi" ?Y" ?i;S'

??i;S ??§??? ??ù?1z? ?? gê" X??Eù??KQ? ?? ?y? ?§ ù êi?m?>§?i;S? ‰?U max(n, m) g§ X J c A 1 W

?{??l? e?11(?êi" ??y êi§òz? ???±W ? " —? § A 1 ? )" ? ? ? ? ê i 7 L ? y A1?U1ê?v±4§W ¤I

?§??¤3

3W,?1§-? P = max(n, m)?êi?ê¤ ! r x L?êi x ?I? ?

g! h L???? 1?(?"

Kk) …= 1.
P i =1 r x

=h×m

2. éu?? x ÷v r x ≤ h 7?5?w, " ??5 r?W r x = h @ x§du ???`ù?1 y??
P i =1 r x

h = 1 ? w , ¤ á?

h > 1 ?§·?

= h × m§@o r x = h

x ????L m ?§

???v " Q,Xd§W x W?g=?"

e?1?§uy^??,¤

á§48y?=?" ¤±zg?? yr r x = h ??êiUW3,?
1

?? ?? ." m> P ?:L?êi§?> m ?:L? ?" ????^>"

5

?Topcoder - SRM 459

2015c&E?c

???II[è??è ??

12

f!?

? ?{9?A^

?g?? ? ?

e P > m K3?>?? :?>"

:L??J?W§m>÷v r x < h i;S ? "

x ?#?

^?c` ‰{?ù? ?? ?

2015c&E?c

???II[è??è

??

13

f!?

? ?{9?A^

?g?? ? ?

4
4.1

??????
‘s??{
???? ?? ???O3u?U?3??§ù —·??U=?¤k

?????K" U?U???'%r O> ??5Q?

é????1§X??¤?§?, s ò? , :3ü^? ·?uy?K?3??" XJ?? e?????? DFS éO2?" ·?ér? ? ?:? ^? ù? ??? O2??{"

t ??§ du??{ü??§ ? ??ó?§=??'%??5·??

>?§ù??{ "

??7????:§??7óê?? ???:?UCe??r > a." ?”k ‰ ??5‰§zgq????? : s§l s m?U O 5K :?óI?§????ó:" ?Juyó:

>/.?50 §zg·?q? ?ó: ?>" O2???Kl v ?? ??>§é ??? ?? óm? DFS" ???" ( ??§?{

c¤3:? u§q? e??:? v" XJ v ?–?L?e v ??X:Ké XJé XJé ?ó?§? XJ v ? –??K cq? ?>? 5?c??y?L " ???§·?r??¤k> nd" K§=r ¤?ùs?? ?:¤ " , 3#??-#éO2?" e?5??ù ‰

?" ???kó?

2015c&E?c

???II[è??è

??

14

f!?

? ?{9?A^

?g?? ? ?

?? G§

:

#?? G §·??I?y?±eü:?

1. e G ?3O2?§K3 G ???3" 2. e G ?3O2?§K3 G ???3" 3y??c§·?kx? ????^??>§=é @???"

??>? (u, v)§??s? h = LCA(u, v)" ????? O §k…=k h @o?\ h ?? >" * ??§÷? >?\ h ?± ??????:÷?? >? ?^? ! _? ok??r{?1¤ §???," ·?? ¤ :?#:§ ????" ?>???^? ü^ >a.??§???? >" >§??? h ??: ? >??

e G ?3O2?§K3 G ???3"
?c?? s ? h ù??ù???? S " - GS , GS ?OL? G, G ?r?? S ugC ?5`? ?{…? ?C" ? #?§w, GS , GS ?é

2015c&E?c

???II[è??è ??

15

f!?

? ?{9?A^

?g?? ? ?

Q, G ?3O2?§`? G ?

?

????

§ ??`?

GS ?

?

???? " ??O2??n§GS ??AT?3O2?" GS ? O2?? P§e P vk?L??§K GS ???3 P" ?K§4 P fr??????÷X?r r???^?{ q?? G S ? G 3O2?" #:§???{ O2?" ? ? ??§Q, GS ?3O2?§@o G ?AT? h§3 GS ? h ??X:§@où GS ?§ ? u? r O 2 ?§ r ù ^ O 2 ? é A

e G ?3O2?§K3 G ???3"
G ? O2?§XJvr#:§@o G ?w,?3?^? XJr ??rùü^>éA ·??c????L #: r{§ G ? §? >???? h ?? h ?± ?§? ? "

#:§???????§???O??^? >??? >" @?^" ?3 G ???? ??????:§???," @o G ?é

????§??±????>3??? G ? O2? "

???/?±uy?XJ ?3l s ?u 3é ?? O2?§ ??§? ?? §éO2? ?:?C"

c?l s ?uéO2?????3l s ?u

??§@oXJ O2?" ?d :§ :?

?y?B§·??/w?0/ s?" 3P?? U§zùs? ¤

?^? ?? ??¤

85P?z?:y33±=?:?? next ê|P???O2 V?óL5??sS? kó:§3BFS è "ù ??z?: 8

'X

??§^??

next ?S|¤ ??§è

r{" ?§S^?? BFS 5??

???§^?

:?ò??¤k?:IP?ó:\\

?±‰ ?géO2? ?m? O(n2 )"

? ?é O(n) gO2?§?doE,?? O(n3 )"

2015c&E?c

???II[è??è

??

16

f!?

? ?{9?A^

?g?? ? ?

4.2
4.2.1
K?

A^
Problem 1. ???iZ

Alice ? Bob 3 ? ? n(n ≤ 200) ? : ?§?? Alice k?"

{ü????

i Z§ ? ? ?6 ?

??§k?? <3,?: s ?" zg§ ?u? ????" ?? Alice ? Bob v h?§?k? K) (???e?3????? ?7‘" ?k§e?3????? v¤ § X: ??Ir v ? ,??X:§ ÷v s ??? : u =?" ù ,?: v ? " <rL :?

<3: u§ [?±4 <r ?K§l??[?í " ?U

? s ?k?7‘"

§÷v s ???

:§ Kk?7}??Kk r ? k?

:§@ok?zr??? ?o?k??r§??r ?^l?X: §, ^?g?"

5?XJù???u)§·??S?é

O?§=O2?§ù??c¤` ??? ? ü ?" ù

e??3§= s ??3??? ?^?????? r? ? ?^?k?à??X:

?§@o??é????? e k ? ? ? ? r§ ` ? ù^?? O ?§

, ? ? X :§

?§ s ò ? 23 ? ?" §ww?? ?à"

? ? ?C§`? s ????3??? ?§??c ^?g?" y3?KC¤ ?3???p§ ·???é????? 5?í ??: u ?= :??3??? ?" ó v ???O2? ?5? ê §q?z?? :§r§l??í

?3O2?§XJ?K`?T:???3??? §XJ?3O2?§u ?K§??í:?? ê ?1§O2 ? 2 +1§ ??'?c?? ??? ? O(n3 ) "? ?déuq? s??±3 O(n2 )

ê +1§d? u, v ?U? ?? ? §g?" q????

u§·??Il v m?éO2?=?" : O(n)§í O2?" ^‘ ?mp ????3l,?:?u

?k??g??? ?mE,? O(n3 )"

2015c&E?c

???II[è??è ??

17

f!?

? ?{9?A^

?g?? ? ?

4.2.2
K?

Problem 2. ???<:

k ? ? n(n ≤ 200) ? : :?\?3z??(? ? ?U<r¤k:" K)

? ? ?§ z ? \ ? ± ? ? < r – ? ü ? \ ? ? 0 ü?:?Uk??'X¤ § ?–

?-#(?§<r

? ? ? ? ? ?? ? ü ? k ? ? ' X ?§§?w,?U3??? du:ê??§?? ê R" ?? G ? ? ?? R" ??? § w,? R

: u, v§ = u, v ? ? ? ? ±

?,?

<r" @o·??á#? G §3¤kvk??' z< ? ?ê§ du??z??<ü? ?

X :é?m??>§L?ù^>üà:?±3?? ??<r"

?." XJù??.?±? §??? " :§2?? G ? ? 'X"

e?·?y?§ù??.????±? ?k§?? XJ,?: ??m ????¤k\?? 0 XJ,?:vk ó§? <K" ó\??? 0§??<K" : y3????e?¤k\?? 0 ??S§ù ó??k– ü?" ?K§ ó§ ? @????u?: :vU ?v

ó?

/?X0 " ??ù ?=? ?? ó ? X¤

ó

ó???u??S?: ? u§du u 3

???\??? 0§??? v gC 5

3??\?? 0 Q,–

? u§Q, v ?X u§@o v ????X ó §?dg?" \?? 0 ?5"

???? v ??U kü?§

¨?? x, y§?¨??

:? X, Y §

'X? x ? X, y ? Y §·?U¤ X ? Y, x ? y§?? X, Y ?\?? 0 ¤±?± ù zg?±N :
3

??< § x, y ?m??3??'X¤±?±? ??? ? ? ü?\?? 0

?C…?{§?…oUN ?{"

??^?

? >§@o??±‰ f? R ?<rü? "

??y?????J? ??é?{) ?mE,? O(n )"

2015c&E?c

???II[è??è ??

18

f!?

? ?{9?A^

?g?? ? ?

5

????
XJ·?3

?
??? ? " ?>?:§? ? ?mü>:ê? § ? §÷v ?K?±=z??? ??? ? ???mü>:ê ?? 0§ @o?? ?

?? ? §??> 2ò??3 ?K" e5·????? z?:?3? ?" >w‰

?K§=é??>

5.1

KM ?{
KM ?{q :?|?{§?±3 O(n3 ) ·?k0 ü?Vg" ?1?I??‰z?!: i ? ?? ? l(i)§éu¤k> (u, v) ÷v ?m???? ? "

w(u, v) ≤ l(u) + l(v) ? f???3?|?1?Ie >" ? )¤f?§??¤k:§? 3÷

v w(u, v) = l(u) + l(v) ?n 2.

éu,?|?1?I§XJ?? ?? y? 2. ?? ?????| val( M ) =
(u,v)∈ M

f??3

?

§@oT?

???

??

? "

?

M § ?> ?
n

w(u, v) ≤
(u,v)∈ M

l(u) + l(v) ≤
i =1

l(i)

???|?1?Ie ? f? val( M ) =
(u,v)∈ M

?

M
n

> ? l(i)

l(u) + l(v) =
i =1

=???| ? "

?

>

????' M

?§@o M ????

2015c&E?c

???II[è??è ??

19

f!?

? ?{9?A^

?g?? ? ?

k

???n§·?

8I???L??N

?I§?

?

f???3

? " ? ?B??§·??Xe??" du?mü>:ê? ?m> ?" § - n L??> :ê" - lxi L??>1 i ?: ?I§rxi L?m>1 i ?: ?I§w(u, v) L??>1 u ?:?m>1 v ?:

k??z?|?1?I§'X lxi = max{ w(i, j) | 1 ≤ j ≤ n }, rxi = 0 , zg????X:§”‰??? @ ?Xé?^O2?" XJé >3 O2??? O2" ???c¤` ??" - S ! T L? ???>! m ???>! m>?3 ??? :" ?K§ ·?ò

??? :§S ! T L?

3? f??? ? S T ??vk>" ??e?3?? >§ ??AT?UY)??S ?

¤k:?o??: s! ?o? T ?? §¤±? >w,vk" ? S T ?????? >§?K T ?éA:?l? >H{ 5 S" ? >! f

XJ·?‰ S ?¤k:?I ?a§T ?¤k:?I +a§@o S ?T ?" ??? >????3? f?§S ? T ??Uk#

>\\?

2015c&E?c

???II[è??è

??

20

f!?

? ?{9?A^

?g?? ? ?

?Jí?? a = min{ lxu + lyv ? w(u, v) | u ∈ S , v ∈ T } XJ a ??§?Iò?{?XJ a ? §? ?^# f?ò??Cz" > (u, v) \\? f? §kü????

1. v ??X:§Ké O2?" 2. v ? S ?,?:??? §Kò v ?§ zg?U?I § ?oé zg?U?I?§ O2?§?o ó?\\ ??" ???!: +2" ù`?–?? f?§?d·?????

U O(n) g?I?Ué O2?" ??? >???lm? 3*?ù? ??§??? ‘où??" ·?é T ?z?: v§‘o slack(v) = min{ lxu + lyv ? w(u, v) | u ∈ S } ±Bzg O(n) ???I?U? a = min{ slack(v) | v ∈ T } 3 ??#\\?? S !: ??§O(n) ?#?e slack(v)" a" O2?" éO2??*? O(n)
3

3?U?I ? g

??§O(n) ‰z? slack(v) ~

?? ??*? ,???X:§@o?é ?e§??q????X:? O(n)

§ zg?

??§zg*?I? O(n) ‘o§oE,? O(n )"

5.2

A^
?k?±)??? ? ! ?? ?Lr> K§??±)?? ? ?K" ? ?K"

KM ?{
?c

?I

.

?? .?§é?| lx, ly ÷v? lxi + ly j ≥ w(i, j)

2015c&E?c

???II[è??è ??

21

f!?

? ?{9?A^

?g?? ? ?

? z?

n

n

lxi +
i =1 i=1

lyi ?I????u

KM ?{?? u?? ?

?I=?‰Y§ ù??????{?I > ?§

KM ?? ?If??ù?e?"

2015c&E?c

???II[è??è

??

22

f!?

? ?{9?A^

?g?? ? ?

6
6.1

?????

aq

?

‘s?
? ? ? KM ? { ? I§ · ? ‰ z ? ! : i ? ?? ? ? K ? I zi!
B | u,v∈ B z B §we

‰z??ê:8 B ?????K?I zB" éu?^> e = (u, v)§- fe = zu + zv + XJéu,?? 1. fe ≥ we fore ∈ E 2. fe = we fore ∈ M 3. zi = 0 e i ??X:, zB = 0 e B ?? >?v @o M ????? ? " ??éu??? M §?> ?????L?
n | B|?1 2

L? e

> "

M §÷v?

LIMIT =
i =1

zi +
B

zB ×

| B| ? 1 2 z ?.§ ?

·?r> ?:8?I 5? ? "

we ??¤ fe ??§ ???c??!:?I ·? ? M > ?f? %§

z ?." u LIMIT§ ?d M ????? z B ?S??éz? ?5

?ùpw?5 B s‘o ?? ?" ?÷v^? 1, 2 ?¤k fe = we ??z ‘o@ 5? ·? ê?" c? zB > 0 y3w5·?

????

??w

?" ùp?In)? (5" ¤ 8I3u§??é ?|?I???? M § ÷v??^

?|?I??{ " > e |¤ ??? f?" M = ?§zi = max we /2" ?m?¤k zB = 0§·??P?? ^? 3" cJe§??~ ? ^? 3 :

:8"

?? G ??

?{L§ò3÷v^? 1! 2

2015c&E?c

???II[è??è ??

23

f!?

? ?{9?A^

?g?? ? ?

?{????? O2?§?????

?? ??

§?? n ?

?§z?

?·?3?

f??é

§?L·?l¤k??

:??m? BFS§r: sS¤k:I z" ós ?§ ?5

?ó/??¤k???ó:¤ §^??è P?ó:?r# ó:\\è §XJé ? y^? 3§·?3??

Q ?¤kó:§ s I? o@

O2?K? O2§?KN zB > 0 ?? ??§rsw‰:§? N z

?(?

s B§?????m" ?d·?3 BFS ??U?- ?s" XJ? =? ? zi ? = a§XJ i ?ó:" ? zi + = a§XJ i ??:" , f??vké

O 2 ?§ ”

? ? KM ? { ? @

??sS?¤k:a.??§sS

>üà? +a ?? ?a§?7?E ?c?? zB "

¤ù^>lm? f?§$–?I??{§ù???^ ? zB + = 2a§XJ B ?ós" ? zB ? = 2a§XJ B ??s" ùp` s??? f? " ?§?Juy?e?o?

s???s?Up?@Xs¤ §ù min?

??±

±s

S >?,33?

e?·?I??? a 1. zi §i ?ó:"

2. fe ? we §e = (u, v)! u ?ó:! v ??–?:" 3. ( fe ? we )/2§e = (u, v)! u, v ??3???sp 4. zB /2§ B ??s" N?uyù a ???s? >! min ??? >! ? >l? f?? ó:"

?”§?????I?{" ·?U a ???3=???? XJ??? 1§@oùgUC 5?a" ÷v" ^? 3 ò?±

2015c&E?c

???II[è??è

??

24

f!?

? ?{9?A^

?g?? ? ?

XJ??? 4§@o?keZ?s /¤ ?? 0 § ???cA?3e §?c 3 §·???±r§?m "

?C¤ 0" ?s’??? nd??

cù??

÷v^? 3§ y3§

?? a, b ?OL??mc! ?m " ?m ??? s" r¤k# ó:\\è Q" ?^# ?(? XJ??? 2 ?? 3§ ?òk– ù ·?o?é
2

ùù?s >\\? §2r

fs?¤

c

f??" XJ,ü ???¤k ?? 0

??3????? ó:?m\\ ?^>§Ké O 2 ?" ù ? ?" ?{?±‰ ós?m§?\e? ^aq

O2?"

?mE,? O(mn )" ??? ‘o slack C? O(n3 )"

6.2
6.2.1
K?

A^
????Ie4 ?K

‰??? n(n ≤ 200) ?: ?§?L¤k>– K) ·?? u?\?
3

{ü???§ >k> " é?^?á

?4?

?g"

>§?

??3?.???=z?:?ê??ó üü?á?§?K=z??ê??ê =z??? ? " :

ê¤ §??#\ > > ?m ?

?ü:m ?á?" ?^???ê~

^ Floyd ?{ O(n ) ??¤k: ? §r>

2015c&E?c

???II[è??è ??

25

f!?

? ?{9?A^

?g?? ? ?

7

o(
·??? o?a. ?{ ? ??? ? ?K§l??? ?‘??{" ? ?L?I .?? ?? ? §l ?

? ???§z?a?K?0 ·?uy§? ???§? é? ?U? ?K §??±=z???? ??{§ ?Kl SN

?%3uéO2?§?? ±)?" ??ù

§?ké???p §k,

?{±9?

??vk0

???±g1??§F"

<?? ?^"

8

a
a ?IO????J??S? a 6 ? " [?! ?U ??3 ?p?! ‘“`! H?R! ?…?! {1?! - "

?? ??é· ??" a ??? ?! M1?P“é· a a ?g?? ???é· · ?<é· '%?ì " ???|±"

???z
[1] Wikipedia§Berge’s lemma [2] Wikipedia§Hopcroft?Karp algorithm [3] Matthew Kusner§ 5Edmonds’s Blossom Algorithm6 [4] Zvi Galil§ 5E?cient Algorithms for Finding Maximal Matching in Graphs6 [5] 4[Z§ 5?{?m\?;6 §?u???? [6] ?á#§ 5CodeForces VK Cup 2012 Round 3 D. Minimum Diameter6 [7] ‘“`§ 5?? ? 6 ‘s??{6

[8] ‰?r§ 5????

2015c&E?c

???II[è??è ??

26


更多相关文档:

国家集训队1999论文集 邵铮

国家集训队1999论文国家集训队1999论文集隐藏>> 数学模型的建立,比较和应用苏州...-2- IOI'99 中国集训队优秀论文选 数学模型的建立,比较和应用 图一 在考虑...

国家集训队2000论文集 江鹏论文

35页 免费 国家集训队2000论文集 方奇... 11页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

国家集训队2003论文集 王知昆

国家集训队2003论文国家集训队2003论文集隐藏>> 王知昆 第 1 页 IOI2003 国家...中国集训队优秀论文集 信息学奥林匹克(季刊) 《金牌之路 竞赛辅导》 江文哉...

国家集训队2002论文集 李睿

国家集训队2002论文集 李睿_IT/计算机_专业资料。国家集训队2002论文集二分法...- 21 - 二分法与统计问题 江苏淮阴中学 李睿 参考书目 [1]IOI99 中国集训队...

国家集训队1999论文集 来煜坤

比如字符识别问题,考虑 n 行该最优化函数值时,注意到 最终一定是按照字符分割与识别的,因而最后一个字符或者是 19 行,或者是 20 IOI'99 中国集训队优秀论文选...

国家集训队1999论文集 石润婷

如果说该题有什么独特的算法的话,那就 IOI'99 中国集训队优秀论文选 - 53 - 隐蔽化,多维化,开放化——论当今信息学竞赛中数学建模的灵活性 是利用简单串并联...

国家集训队2005论文集 龙凡

国家集训队2006论文集 李天... 14页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

国家集训队2003论文集 许智磊

国家集训队2003论文集 王知... 10页 免费 国家集训队2003论文集 林希... 16页 免费 国家集训队2003论文集 高正... 25页 免费 国家集训队2003论文集 王知...

国家集训队2005论文集 朱晨光

许智磊 IOI2004 国家集训队论文 《后缀数组》 CEPC 2003 Problem D Dice Contest USACO 2004 February Contest Green Problems 附录一,文中例子的原题 1,例 2(...

国家集训队2002论文集 何林

国家集训队2002论文国家集训队2002论文集隐藏>> 猜想及其应用【摘要】 摘要】...湖南教育出版社 2000 年湖南集训试题 NOI2000 试题 中国基础教育网(www.cbe21....
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com