루미 알고리즘

#1431플래티넘Snökaos

PO 2017 온라인 예선코딩출제 Lisa Vällfors, Fredrik Hernqvist스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Ett snöoväder har dragit in och det är kaos i trafiken. Inte nog med det, utan vissa delar av järnvägsspåret har snöat igen vilket gjort att all tågtrafik stoppats. Detta är naturligtvis inte så bra, eftersom mängder av resenärer nu står vid sina stationer och inte kommer någonstans. Fredrika har därför fått i uppgift att röja bort snön mellan stationerna innan rusningstiden börjar och katastrofen är ett faktum.

Järnvägsspåret är helt utan förgreningar och har n stationer, numrerade från 1 till n i den ordning de förekommer på spåret (så att station i kommer precis före station i+1). Det finns därmed n - 1 sträckor mellan stationerna. Av dessa är s täckta med snö.

Fredrika är lite orolig eftersom hon räknat ut att hon endast hinner röja bort snön från p sträckor. För att göra det bästa av situationen bestämmer sig Fredrika för att välja de sträckor som gör att så många som möjligt av de väntande resenärerna kan åka dit de vill. Till sin hjälp har hon svaren från en enkät som hon skickat ut till alla som väntar, där de fått svara på vilka stationer de vill åka mellan.

Förutsatt att Fredrika väljer sträckorna optimalt, beräkna hur många väntande resenärer som kommer kunna åka då hon är klar.

Notera att tåg kan endast köra på snöfria sträckor. Alla stationer har tåg parkerade, så samtliga snöfria sträckor kommer att kunna trafikeras, även om stationerna inte kan nås från spårets slutstationer. Tågtrafiken är helt stoppad fram tills Fredrika är klar, så även resenärer som från början har en snöfri resväg räknas in i svaret.

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Sample 1

Indata

Första raden innehåller fyra heltal, 2 ≤ n ≤ 200, 1 ≤ m ≤ 100000, 0 ≤ s, p ≤ n - 1: antalet stationer, antalet resenärer, antalet igensnöade sträckor och antalet sträckor Fredrika hinner ploga.

Därefter följer m rader där rad i innehåller två heltal 1 ≤ a_i ≠ b_i ≤ n, stationerna där resenär i vill starta respektive sluta.

Därefter följer s rader där rad j innehåller ett heltal 1 ≤ c_j ≤ n - 1, stationen som ligger precis innan den igensnöade sträckan j. En sträcka förekommer högst en gång i denna lista.

Utdata

Ditt program ska skriva ut ett enda heltal: det största antalet resenärer som kan genomföra sina resor genom att ploga högst p sträckor.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränserÖvrigt
112n ≤ 200, m ≤ 100, p = 1
211n ≤ 200, m ≤ 100, s ≤ 12
310n ≤ 200, m ≤ 100a_i = 1 för alla a_i
467n ≤ 200

예제

예제 1

입력
5 4 3 2
1 5
1 4
2 3
3 4
1
3
4
출력
3

출처 표기

출처: Programmeringsolympiaden 2017년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.