import

Import

== include(page="template/taskheader" task_id="import") ==

Ca orice tara civilizata, Romania importa diferite produse din alte tari. In acest scop se efectueaza $M$ transporturi, fiecare transport plecand dintr-un oras din afara tarii si avand ca destinatie finala un oras din Romania. Orice transport este efectuat de un camion ce apartine fie firmei Alfatrans, fie firmei Betatrans. Putem presupune ca orasele sunt numerotate de la $1$ la $N$, orasele $1 ... K$ fiind din Romania, iar orasele $K+1 ... N$ din alte tari. Intre aceste orase exista $N-1$ sosele bidirectionale astfel incat intre oricare $2$ orase exista exact un drum (format din una sau mai multe sosele) si orice drum de la un anumit oras din Romania catre un oraa din alta tara trece prin orasul $1$, in acest oras aflandu-se vama. Pe parcursul drumului oricarui transport, la trecerea printr-un oras soferul camionului trebuie sa plateasca anumite taxe si trebuie sa comercializeze o parte din produsul transportat, astfel incat sa obtina un profit fixat de primaria orasului respectiv. Guvernul Romaniei a stabilit pentru fiecare transport profitul total minim ce trebuie obtinut. Profitul total se obtine insumand profiturile obtinute in fiecare oras prin care trece camionul pe drumul de la orasul de plecare la orasul destinatie (inclusiv orasul de plecare si orasul destinatie). Patronul Alfatrans are numeroase relatii internationale si poate manipula primaria fiecarui oras. Astfel, el poate sa stabileasca pentru fiecare oras $i$ profitul $P{~i~}$ care trebuie sa fie obtinut la trecerea unui camion prin orasul respectiv. Pentru a discredita firma Betatrans, patronul firmei Alfatrans doreste sa stabileasca $P{~i~}$ pentru fiecare oras $i$ astfel incat orice transport executat de camioane Alfatrans sa aduca un profit mai mare sau egal cu profitul minim stabilit pentru acel transport si orice transport executat de camioane Betatrans sa aduca un profit strict mai mic decat profitul stabilit.

Ca orice tara civilizata, Romania importa diferite produse din alte tari. In acest scop se efectueaza $M$ transporturi, fiecare transport plecand dintr-un oras din afara tarii si avand ca destinatie finala un oras din Romania. Orice transport este efectuat de un camion ce apartine fie firmei Alfatrans, fie firmei Betatrans. Putem presupune ca orasele sunt numerotate de la $1$ la $N$, orasele $1 ... K$ fiind din Romania, iar orasele $K+1 ... N$ din alte tari. Intre aceste orase exista $N-1$ sosele bidirectionale astfel incat intre oricare $2$ orase exista exact un drum (format din una sau mai multe sosele) si orice drum de la un anumit oras din Romania catre un oras din alta tara trece prin orasul $1$, in acest oras aflandu-se vama. Pe parcursul drumului oricarui transport, la trecerea printr-un oras soferul camionului trebuie sa plateasca anumite taxe si trebuie sa comercializeze o parte din produsul transportat, astfel incat sa obtina un profit fixat de primaria orasului respectiv. Guvernul Romaniei a stabilit pentru fiecare transport profitul total minim ce trebuie obtinut. Profitul total se obtine insumand profiturile obtinute in fiecare oras prin care trece camionul pe drumul de la orasul de plecare la orasul destinatie (inclusiv orasul de plecare si orasul destinatie). Patronul Alfatrans are numeroase relatii internationale si poate manipula primaria fiecarui oras. Astfel, el poate sa stabileasca pentru fiecare oras $i$ profitul $P{~i~}$ care trebuie sa fie obtinut la trecerea unui camion prin orasul respectiv. Pentru a discredita firma Betatrans, patronul firmei Alfatrans doreste sa stabileasca $P{~i~}$ pentru fiecare oras $i$ astfel incat orice transport executat de camioane Alfatrans sa aduca un profit mai mare sau egal cu profitul minim stabilit pentru acel transport si orice transport executat de camioane Betatrans sa aduca un profit strict mai mic decat profitul stabilit.

h2. Cerinta

h3. Explicatie

Primul transport trece prin orasele $6 1 3$ si $2$ obtinand un profit
de $10+0-6+6=10$ deci respecta conditiile din enunt.

Primul transport trece prin orasele $6 1 3$ si $2$ obtinand un profit de $10+0-6+6=10$ deci respecta conditiile din enunt.

Al doilea trece prin $6 1 3$ si obtine un profit de $10+0-6=4$ mai mic decat $5$ si de asemenea respecta conditiile din enunt
Al treilea drum trece prin orasele $7 6 1 3 4$, obtine un profit de $0+10+0-6+3=7$, iar ultimul drum trece prin $5 1 3 4$ cu un profit de $0+0-6+3=-3$ mai mic decat $-2$
== include(page="template/taskfooter" task_id="import") ==

1713