Ca orice ţară civilizată, România importă diferite produse din alte ţări. În acest scop se efectuează
M transporturi, fiecare transport plecând dintr-un oraş din afara ţării şi având ca destinaţie finală un oraş din România. Orice transport este efectuat de un camion ce aparţine fie firmei Alfatrans, fie firmei Betatrans.
Putem presupune că oraşele sunt numerotate de la 1 la
N, oraşele
1..K fiind din Romania, iar oraşele
K+1..N din alte ţări. Între aceste oraşe există
N-1 şosele bidirecţionale astfel încât între oricare doua oraşe există exact un drum (format din una sau mai multe şosele) şi orice drum de la un anumit oraş din România către un oraş din altă ţară trece prin oraşul 1, în acest oraş aflându-se vama.
Pe parcursul drumului oricărui transport, la trecerea printr-un oraş şoferul camionului trebuie să plătească anumite taxe şi trebuie să comercializeze o parte din produsul transportat, astfel încât să obţină un profit fixat de primăria oraşului respectiv.
Guvernul României a stabilit pentru fiecare transport profitul total minim ce trebuie obţinut. Profitul total se obţine însumând profiturile obţinute în fiecare oraş prin care trece camionul pe drumul de la oraşul de plecare la oraşul destinaţie (inclusiv oraşul de plecare şi oraşul destinaţie).
Patronul Alfatrans are numeroase relaţii internaţionale şi poate manipula primăria fiecărui oraş. Astfel, el poate să stabilească pentru fiecare oraş
i profitul
Pi care trebuie să fie obţinut la trecerea unui camion prin oraşul respectiv.
Pentru a discredita firma Betatrans, patronul firmei Alfatrans doreşte să stabilească
Pi pentru fiecare oraş
i astfel încât orice transport executat de camioane Alfatrans să aducă un profit mai mare sau egal cu profitul minim stabilit pentru acel transport şi orice transport executat de camioane Betatrans să aducă un profit strict mai mic decât profitul stabilit.
Cerinţă
Pentru un număr considerabil de acţiuni la Alfatrans şi pentru a obţine 100 de puncte, trebuie să-l ajutaţi pe patronul firmei Alfatrans să stabilească pentru fiecare oraş profitul impus de primărie astfel încât firma Betatrans să fie discreditată.
Date de intrare
Pe prima linie a fişierului de intrare
import.in sunt scrise numerele naturale
N M K separate prin câte un spaţiu, având semnificaţia din enunţ. Următoarele
N-1 linii conţin câte două numere naturale
a b separate printr-un spaţiu, cu semnificaţia că există o şosea bidirecţională de la oraşul
a la orasul
b. Următoarele
M linii descriu transporturile după cum urmează. Fiecare linie conţine 4 numere
a b c d separate prin câte un spaţiu cu semnificaţia ″se face transport de la oraşul
a la oraşul
b executat de firma
x, iar profitul minim ce trebuie asigurat pentru acest transport este
c ″. Firma
x este Alfatrans dacă
d=0 şi respectiv Betatrans dacă
d=1. Se garantează că pentru orice transport
a este un oraş din afara ţării, iar
b este un oraş din România.
Date de ieşire
Fişierul
import.out va conţine o singură linie pe care se vor scrie
n numere separate prin exact câte un spaţiu. Cel de al
i-lea număr de pe linie reprezintă
Pi, profitul stabilit de patronul Alfatrans pentru oraşul
i. Dacă aceste valori vor face ca firma Betatrans să nu respecte cerinţele guvernului, iar firma Alfatrans să respecte în totalitate aceste cerinţe veţi obţine punctajul maxim pe test.
Restricţii
2 < N < 222
1 < K < N
0 < M < K*(N-K)
Profitul minim ce trebuie asigurat pentru fiecare transport este un număr întreg cuprins între
-109 şi
109.
Profiturile
Pi trebuie să fie numere întregi cuprinse între
-100000 şi
100000.
Se garantează existenţa unei soluţii.
Exemple
import.in | import.out | Explicaţii |
7 4 4
1 3
3 2
3 4
1 5
1 6
6 7
6 2 10 0
6 3 5 1
7 4 7 0
5 4 -2 1
| 0 6 -6 3 0 10 0
| Primul transport trece prin oraşele 6 1 3 şi 2 obţinând un profit
de 10+0-6+6=10 deci respectă condiţiile din enunţ.
Al doilea trece prin 6 1 3 obţine un profit de 10+0-6=4<5 şi de asemenea respectă condiţiile din enunţ
Al treilea drum trece prin oraşele 7 6 1 3 4, obţine 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 < -2
|