Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 136. feladat (2019. szeptember)

S. 136. Adott egy \(\displaystyle N\) csúcsú, \(\displaystyle M\) élű egyszerű gráf (nincs többszörös él vagy hurokél, de nem feltétlenül összefüggő). A csúcsokat 0-tól \(\displaystyle (N-1)\)-ig indexeljük. A gráf összes csúcsa fekete vagy fehér. Jelölje \(\displaystyle f(x)\) az \(\displaystyle X\) csúcs színét. Cseresznyének hívunk egy \(\displaystyle (A,B,C)\) rendezett csúcshármast, ha páronként különbözőek és létezik az \(\displaystyle A-B\), valamint a \(\displaystyle B-C\) csúcspárok közt él. Egy \(\displaystyle (A,B,C)\) cseresznye finom, ha \(\displaystyle f(A)=f(C)\) és \(\displaystyle f(A)\ne f(B)\). Adjuk meg, hogy egy él behúzásával legföljebb mennyire növelhető a finom cseresznyék száma. (\(\displaystyle A\) és \(\displaystyle B\) csúcs összeköthető egy éllel, ha \(\displaystyle A\ne B\), és eddig nem létezett köztük él.)

Standard bemenet: az első sor tartalmazza \(\displaystyle N\)-et és \(\displaystyle M\)-et. A következő sor \(\displaystyle N\) darab számot tartalmaz: az \(\displaystyle i\)-edik szám az \(\displaystyle i-1\) indexű csúcs színét határozza meg, 0 ha fekete, 1 ha fehér. A következő \(\displaystyle M\) sor mindegyike két számot tartalmaz. Az \(\displaystyle i\)-edik sor az \(\displaystyle i\)-edik él két végpontjának csúcsindexét adja meg.

Standard kimenet: a maximálisan elérhető finom cseresznyék száma.

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 0\le M\le \min (10^{5},N^{2}-N-1)\). Időkorlát: 0,3 mp.

Értékelés: A pontok 50%-a kapható, ha a gráf fa.

Példa:

Bemenet (a / jel sortörést helyettesít)Kimenet
5 4
0 1 1 1 0
0 1 / 1 4 / 3 0 / 0 2
12
Beküldendő egy s136.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2019. október 10-én LEJÁRT.


Statisztika:

Az S. 136. feladat értékelése még nem fejeződött be.


A KöMaL 2019. szeptemberi informatika feladatai