Diferente pentru problema/lianyu intre reviziile #18 si #31

Diferente intre titluri:

lianyu
Lianyu

Diferente intre continut:

== include(page="template/taskheader" task_id="lianyu") ==
Pe insula Lian Yu sunt $N$ asezari conectate prin $M$ drumuri bidirectionale. Pe aceasta insula renumitul Slade Wilson creste cel mai periculos drog si de asemena cea mai periculoasa arma, Mirakuru. A.R.G.U.S a aflat de aceasta operatiune si vrea sa trimita $K$ echipaje de soldati sa investigheze si sa obtina informatii esentiale. Totusi acest lucru nu este chiar atat de simplu si prin urmare A.R.G.U.S v-a angajat pe voi trei sa le spuneti costul minim pentru a trimite $K$ echpaje de soldati pe insula tinand cont de urmatoarele conditii:
Pe insula Lian Yu sunt $N$ asezari, numerotate de la $1$ la $N$, conectate prin $M$ drumuri bidirectionale. Pe aceasta insula renumitul Slade Wilson creste cel mai periculos drog si de asemena cea mai periculoasa arma, Mirakuru. A.R.G.U.S a aflat de aceasta operatiune si vrea sa trimita $K$ echipaje de soldati sa investigheze si sa obtina informatii esentiale. Totusi acest lucru nu este chiar atat de simplu si prin urmare A.R.G.U.S v-a angajat pe voi trei sa le spuneti costul minim pentru a trimite $K$ echpaje de soldati pe insula tinand cont de urmatoarele conditii:
* datorita structurii insulei, in fiecare asezare $i$ poate fi lasat, de catre avioane, maxim un echipaj de soldati cu costul $cost[~i~]$.
* dupa aterizarea echipajelor acestea vor trebui sa se intalneasca intr-o asezare ca sa continue planul. Datorita interventiei bruste a echipajului si a suportului aerian, soldatii vor putea elimina toti mercenarii lui Slade Wilson care se vor afla in asezarile unde vor ateriza acestia. De indata ce soldatii vor ateriza, se va da alarma in toata insula si toti mercenarii vor lua cat mai mult Mirakuru si se vor aduna intr-una din asezari ca sa-l protejeze (si cel mai probabil daca soldatii vor trece prin aceasta asezare vor fi omorati, cea ce este totatl exclus).
* dupa aterizarea echipajelor acestea vor trebui sa se intalneasca intr-o asezare ca sa continue planul. Datorita interventiei bruste a echipajului si a suportului aerian, soldatii vor putea elimina toti mercenarii lui Slade Wilson care se vor afla in asezarile unde vor ateriza acestia. De indata ce soldatii vor ateriza, se va da alarma in toata insula si toti mercenarii vor lua cat mai mult Mirakuru si se vor aduna intr-una din asezari ca sa-l protejeze (si cel mai probabil daca soldatii vor trece prin aceasta asezare vor fi omorati, cea ce este total exclus).
Asadar echipajele trebuie lasate in asezari astfel incat in oricare din cele ramase s-ar strange mercenarii lui Slade Wilson, soldatii sa poata sa se intalneasca intr-o asezare fara sa treaca prin cea aleasa de de Slade Wilson si echipa sa.
h2. Restricţii
* $1 ≤ K ≤ N ≤ 3000$
* $1 ≤ M ≤ 5000&
* se poate ajunge de la oricare asezare la oricare alta mergand pe cel $M$ drumuri
* intre oricare doua asezari exista maxim un drum si nu exista drum de la o asezare la ea insasi
* $1 ≤ M ≤ 5000$
* $1 ≤ cost[~i~] ≤ 10^5^$
* $Se poate ajunge de la oricare asezare la oricare alta mergand pe cele $M$ drumuri$
* $Intre oricare doua asezari exista maxim un drum si nu exista drum de la o asezare la ea insasi$
h2. Exemplu
table(example). |_. lianyu.in |_. lianyu.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 5 5 2
  2 4 1 4 1
  1 2
  2 3
  3 4
  1 4
  4 5
| 3
|
h3. Explicaţie
...
Se trimit echipaje in asezarile 1 si 3.
Un cost mai bun se poate obtine daca am trimite echipaje in asezarile 3 si 5, dar daca mercenarii se vor strange in asezarea 4 atunci echipajul din asezarea 5 nu se va mai putea intalni cu cel din asezarea 3.
== include(page="template/taskfooter" task_id="lianyu") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.