Güç Şəbəkəsi#5756
Bir enerji şəbəkəsi enerji stansiyaları, istehlakçılar və dispetçerlərdən ibarət qovşaqlardan və bu qovşaqları birləşdirən enerji nəqli xətlərindən ibarətdir. Hər bir u qovşağı s(u) ≥ 0 qədər enerji ala bilər, 0 ≤ p(u) ≤ p_max(u) qədər enerji istehsal edə bilər, 0 ≤ c(u) ≤ min(s(u),c_max(u)) qədər enerji istehlak edə bilər və d(u)=s(u)+p(u)-c(u) qədər enerji çatdıra bilər. Aşağıdakı məhdudiyyətlər mövcuddur: enerji stansiyaları üçün c(u)=0, istehlakçılar üçün p(u)=0 və dispetçerlər üçün p(u)=c(u)=0. Şəbəkədə hər bir qovşaqdan u digər qovşağa v yalnız bir enerji nəqli xətti (u,v) ilə bağlana bilər; bu xətt u tərəfindən v-yə 0 ≤ l(u,v) ≤ l_max(u,v) qədər enerji nəql edir. Con = _u(cu) şəbəkədə istehlak edilən enerjini göstərir. Məqsəd Con maksimum dəyərini tapmaqdır.
Şəkildə bir nümunə göstərilmişdir. Enerji stansiyası u-nun x/y etiketi p(u)=x və p_max(u)=y olduğunu göstərir. İstehlakçı u-nun x/y etiketi c(u)=x və c_max(u)=y olduğunu göstərir. Enerji nəqli xətti (u,v)-nin x/y etiketi l(u,v)=x və l_max(u,v)=y olduğunu göstərir. İstehlak edilən enerji Con=6-dır. Şəbəkənin digər mümkün vəziyyətləri də mövcuddur, lakin Con dəyəri 6-dan çox ola bilməz.
Giriş faylında bir neçə məlumat dəsti mövcuddur. Hər bir məlumat dəsti bir enerji şəbəkəsini təsvir edir. Dörd tam ədədlə başlayır: 0 ≤ n ≤ 100 (qovşaqların sayı), 0 ≤ n_p ≤ n (enerji stansiyalarının sayı), 0 ≤ n_c ≤ n (istehlakçıların sayı) və 0 ≤ m ≤ n^2 (enerji nəqli xətlərinin sayı). m məlumat üçlükləri (u,v)z ilə davam edir, burada u və v qovşaq identifikatorlarıdır (0-dan başlayaraq) və 0 ≤ z ≤ 1000 l_max(u,v) dəyəridir. n_p cütlükləri (u)z ilə davam edir, burada u enerji stansiyasının identifikatorudur və 0 ≤ z ≤ 10000 p_max(u) dəyəridir. Məlumat dəsti n_c cütlükləri (u)z ilə bitir, burada u istehlakçının identifikatorudur və 0 ≤ z ≤ 10000 c_max(u) dəyəridir. Bütün giriş rəqəmləri tam ədədlərdir. (u,v)z üçlükləri və (u)z cütlükləri istisna olmaqla, girişdə boşluqlar sərbəst şəkildə ola bilər. Giriş məlumatları faylın sonu ilə bitir və düzgündür.
Girişdən hər bir məlumat dəsti üçün proqram müvafiq şəbəkədə istehlak edilə bilən maksimum enerji miqdarını standart çıxışda çap etməlidir. Hər bir nəticə tam ədədi dəyərə malikdir və ayrı bir sətirin başlanğıcından çap edilməlidir.
Nümunə 1