e-olymp
Məsələlər

Yaxşı qraf

Yaxşı qraf

Aleks yaxşı qrafı belə təyin edir:

  • Bir təpə yaxşı qrafdır.
  • Əgər iki yaxşı qrafın ümumi təpələri yoxdursa, onda onların birləşməsi də yaxşı qrafdır.
  • Əgər Gyaxşı qrafdırsa, onda (G -nin tamamlanması) da yaxşı qrafdır.

Yaxşı qrafda maksimal çəkili dəstlərin axtarılması məsələsini həll etməyə çalışın.

Giriş verilənləri

Giriş faylının birinci sətri verilmiş Gyaxşı qrafındakı təpələrin sayını ifadə edən yeganə N (1N500) ədədini ehtiva edir.

Növbəti n sətir G -nin əlaqəlilik matrisini ehtiva edir.

Hər bir növbəti N sətir i-ci təpənin çəkisini ifadə edən wi (1wi1000) tam ədədini ehtiva edir.

Çıxış verilənləri

Çıxış faylının yeganə sətrində G qrafının maksimal təstinin çəkisini verməli.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
4
0000
0011
0101
0110
100
1
2
3
Çıxış verilənləri
100