Графын онол II (Friend IOI14 Part II)

Хэд хэдэн онолын нэрүүдийг монголоор сайн мэдэхгүй юм. Мэдэх нэг нь комментоор үлдээгээрэй.

::Maximum Independent Set

Аль ч хоёр орой нь хөрш байх ёсгүй оройн олонлог гэхээр үүнийг independent set гэдэг. Энэ олонлогийн оройн тоог байж болох хамгийн ихээр нь байлгаж чадвал үүнийг maximum independent set гэдэг. Энэ бодлого бол шийдэгдээгүй бодлого NP буюу одоогоор мэдэгдэж байгаа хамгийн сайн алгоритмын үнэлгээ нь non-polynomal ба олон гишүүнт хэлбэрээр тавигдахгүй гэсэн үг. Үүнийг a(v) гэе.



::Minimum Vertex Cover

Графаас хэд хэдэн оройн сонгон оройн олонлог авах ба үүссэн олонлог дахь орой болгон нь анхны том графын ядаж нэг ирмэгт харьяалагдаж байвал үүнийг vertex cover гэдэг. Бүрхэлт гэх юмуудаа. Мөн уг олонлогийн оройн тоог байж болох хамгийн багад хүргэж чадвал үүнийг minimum vertex cover гэж байгаа юм. Үүнийг b(v) гэе.



Ерөнхий тохиолдолд дээрх хоёр бодлого хоюулаа NP бодлого.



::Konig's theorem

Графын нийт оройн тоо V = a(v) + b(v)



::Bipartite граф

Графыг аль ч хоёр хөрш орой нь ялгаатай өнгөөр будагдсан байхаар будахад яг 2 будаг хэрэг болдог графыг bipartite граф гэдэг. Ийм графын хэрэглээ маш өндөр. Ийм граф дээр b(v) тоог олох нь компьютерийн шинжлэх ухаанд маш их хэрэг болж байгаа, учир нь O(EVf*) хугацаанд b(v)-г олох алгоритм байгаа. a(v) = V-b(v) гээд хялбархан олчиж байгаа биз.



::Maximum Matching

Оюутнууд болон оюутны байр байг. Оюутнууд аль аль өрөөнд орох хүсэлтэй байгаа хүсэлт нь өгөгдсөн, нэг өрөөнд нэг л оюутан байх ёстой бол хамгийн ихдээ хичнээн оюутан өрөөнд орж чадах вэ? гэсэн бодлого байг. Үүнийг зүүн талд нь бүх оюутнуудыг графын оройнууд болгоод цувуулаад тавья. Баруун талд нь бүх өрөөнүүдийг тавье.

Дээр үүссэн граф бол bipartite graph. Дээр тавигдсан бодлогын хариу буюу хамгийн их хоёр хосыг байгуулах бодлого нь maximum matching юм. Хамгийн их хос оройн тоо гэх юмуудаа. Үүнийг network flow ашиглаад олчихдог. Flow-н талаар ЭНД дарж уншина уу. Товчхондоо бол графыхаа хоёр талд нь нэмээд хоёр орой тавиад (зүүн талд нь эхлэл s, баруун талд нь төгсгөлын орой t) ирмэг бүрт урсгалын 1 гэсэн утга өгөөд алгоритмаа гүйлгэчинэ.

Миний бичсэн Ford-Fulkersonий энгийн цэвэрхэн код ЭНД дарж харна уу. Өөрөө гол нь сураарай.



Дэд бодлого 5 дээр анализ хийе



Зөвхөн дүрэм 0 болон 1 гэхээр графаа зураад үздээ. Яаж ч байсан сондгой урттай цикл үүсэхгүйг хараад батлах гээд үзээрэй. Үүсэж болох графын оройн зэрэг дээр тулгуурлаад гарчина. Сондгой цикл байхгүй гэхээр үүсэх граф маань bipartite граф болно. Maximum Matching-г олоод нийт оройн тооноос хасахад манай бодлогын хариу гарж ирнэ. Графаа яаж байгуулж байгаа, бас бус зүйлүүдийг яаж шийдсэнийг кодноос харна уу.

source

Мэдээлэл зүйн олон улсын олимпиадын тухай (Friend part I)

Олон улсын мэдээлэл зүйн олимпиад гэж ямархуу бодлоготой тэмцээн болдогийг сонирхуулах бас ирээдүйд явах хүүхдүүдэд бага ч гэсэн мэдрүүлж тайлбарлах үүднээс уг постыг бичлээ.



Ямар бодлого сонгож авах вэ гэж бодож байгаад 14 оны Friend гэж бодлогыг сонголоо. Бодлогын өгүүлбэрийг нь илүү дутуу зүйлүүдийг хасаж орчууллаа. Граф юмшиг харагдаж байгаа ч дэд бодлого гэж яагаад оруулаад байгаан мөн чанар, яагаад сүүлийн жилүүдэд уг тэмцээн маань илүү шударга олимпиад болоод байгааг харуулахыг хичээлээ. Товчхондоо бол бодлогын өгүүлбэрийг уншаад аан энэ граф байна гээд дүгнэж болно. Бүтэн бодолт маань мэдээж бүх тохиолдлыг давах ёстой. Бүх тохиолдол гэж ярьж байгаа маань тохиолдлуудыг дотор нь дахиад ангилчиж болохыг харж байгаа байх. Хүүхэд хичээж хичээж маш их цаг хугацаа, бэлтгэл зарцуулж энэ тэмцээнд орж байгаа, тодорхой түвшинд уг бодлогыг бодож чадах хэмжээнд байгаа, бүх тохиолдлыг биш ч хэд хэдэн тохиолдолд нь бодолт хийх хэмжээний хүүхдүүд байгаа. Энэ хүүхдүүдийг үнэлэх ёстой гэдэг нь хамгийн чухал зүйл юм. Жишээ нь энэ Friend гээд бодлого графын бодлого мөн нь мөн. Гэхдээ эхний 3-н дэд бодлого нь энгийн цикл, 4 дэх бодолт нь динамик програмчлал, 5 дахь бодлого онол жаахан шаардсан, 6 буюу бүтэн бодолт шаардах дэд бодлого бол сэтгэх, сэтгэлгээ туршлага шаардсан.



Энэ бодлого бол 2014 оны хоёр дахь хамгийн хүнд бодлого. Гэхдээ эхний 4н дэд бодлого нь ямар амархан болохыг хараарай.

Дэд бодлого бүрийг спож дээрх өөрийн хуудсанд тухайн таарсан тесттэй нь хамт оруулж бэлдлээ. Өөрсдийн бодолтоо шалгаарай. Бүгд албан ёсны бэлтгэгдсэн тестүүд байгаа шүү, минийх биш.

Дэд бодлого 1

Дэд бодлого 2

Дэд бодлого 3

Дэд бодлого 4

Дэд бодлого 5 Үүсэх граф нь bipartite буюу дурын хоёр орой нь ялгаатай өнгөөр будахад хоёрхон өнгө хангалттай байх граф байгаа.

N оройтой (оройг 0..N-1 дугаарласан) чиглэлгүй мөн орой болгон нь эерэг тоон жинтэй граф өгөгдсөн. Графаа байгуулахдаа N алхамаар байгуулна, алхамуудаа мөн 0-ээс эхлэж дугаарлана. Хамгийн эхлээд буюу алхам 0-т граф зөвхөн 0 (оройн дугаар шүү!) гэсэн оройг нэмнэ. Дараачын алхам i (1 < i < N) бүрт доорх 3-н дүрмүүдийн нэг нь байна:

Дүрэм 0* HOST 0 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройтой холбоно. 

Дүрэм 1* HOST 1 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройн бүх хөрш оройнуудтай холбно. Гэхдээ HOST-той холбохгүй.

Дүрэм 2* HOST 2 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройн бүх хөрш оройнуудтай холбно. Мөн HOST-г ч холбоно.

Дээр бичигдсэн HOST нь дандаа тухайн i тооноос бага тоо байна. Аль нэг аль хэдийн нэмэгдсэн оройнуудын нэг нь байна гэсэн үг.

Энд нэг зүйлийг тодруулахад хөрш орой гэдэг нь зөвхөн нэг ирмэгээр холбогдсон хоёр оройг хөрш орой гэнэ шүү. Илүү дэлгэрэнгүй тайлбар хэрэгтэй бол миний блогийн граф гэсэн постыг уншна уу.

Даалгавар: Үүссэн графаас аль ч хоёр орой нь хоорондоо хөрш биш байхаар оройн олонлог сонгож авая. Уг олононлогийнхаа нийт оройн жингүүдийн нийлбэрийг S гэе. S-н хамгийн их утгыг ол.

Дэд бодлогуудын оролтын өгөгдлийн хязгаарлалтууд:

Дэд бодлого 1: Нийт онооны 11%. 2<=N<=10. 1<=Оройн жингүүдийн утга<=10^6. Бүх 3-н дүрэм ашиглагдна.

Дэд бодлого 2: Нийт онооны 8%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 1 ашиглагдна.

Дэд бодлого 3: Нийт онооны 8%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 2 ашиглагдна.

Дэд бодлого 4: Нийт онооны 19%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 0 ашиглагдна.

Дэд бодлого 5: Нийт онооны 23%. 2<=N<=1,000. Оройн жингүүдийн утга=1. Дүрэм 0 болон 1 ашиглагдна.

Дэд бодлого 6: Нийт онооны 31%. 2<=N<=100,000. 1<=Оройн жингүүдийн утга<=10,000. Бүх дүрэм ашиглагдна.



Оролтын файлын формат:

Эхний мөрөнд N гэсэн ганц тоо

2 дахь мөрөнд N ширхэг тоо байх ба тухайн i дахь тоо нь i (0 <= i < N)дугаартай оройн жин байна.

3 дахь мөрөнд N-1 шихрэг хоёр хос тоо байх ба энэ нь графаа байгуулах алхам бүр юм. i дахь хос тоо нь "HOST A" гэсэн форматтай байна. Энд HOST нь дээр дурьдагдсан HOST, A гэсэн тоо нь дүрмийн дугаар байна.

Гаралтын файлын формат:

Бодлогын хариу болох ганц тоо л байна.



Жишээ оролт:

6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0

Жишээ оролтын гаралт:

35





Анализ:



Дэд бодлого 1:

Бүх дүрэм орох тул үүсэж болох граф юу ч байж болно.

N=10 учраас оройн бүх боломжит дэд олонлогуудыг гаргаж байгаад тухайн дэд олонлог бүрт орж байгаа оройнуудын жингийн нийлбэрүүдээс хамгийн ихийг нь авна гэсэн үг. Битмаск ашиглаад бүх дэд олонлогуудыг гаргана. Битмаскын талаар энд дарж уншина уу. Бүх дэд олонлогыг үүсгэхэд O(2^N) хугацаа мөн тухайн дэд олонлогийн дурын хоёр орой нь хөрш биш гэж шалгахад O(N*N) бодолт хийнэ. Нийтдээ бодолтын үнэлгээ O(N^2 * 2^N). Даалгавар, уг бодолтыг сайжруулж O(N*2^N) болгоно уу.

Аль болох ойлгомжтой бичих үүднээс соорс кодыг с дээр бичлээ.

source



Дэд бодлого 2:

Зөвхөн дүрэм 1 тул үүсэх графд ямар ч ирмэг байхгүй, дан тус тусдаа орой гэсэн үг. Бодолт хамгийн амархан, бүх оройн жингийн нийлбэр гэсэн үг. O(N).

source



Дэд бодого 3:

Зөвхөн дүрэм 2 гэхээр үүсэх граф бүтэн граф гэсэн үг. Өөрөөр хэлбэл дурын 2 орой хөрш гэсэн үг. Тэгэхээр зүгээр л бүх орон жингийн хамгийн их утга хариу болно. O(N).

source



Дэд бодлого 4:

Зөвхөн дүрэм 0 гэхээр үүсэж граф мод байна гэсэн үг. Модны dp болж хувирлаа.

Модоо 0 дугаартай оройноос нь барьж байгаад өлгөчихсөн гэж үзье. Үүнийг rooted tree гэдэг. Ерөнхий санаа бол i оройгоос өлгөгдсөн дэд модны хувьд бодлогын хариуг олоод явна гэсэн үг. Нэг тооцох ёстой зүйл бол тухайн i оройн жинг тооцоондоо оруулах эсэх. dp(i, 0), dp(i, 1) гэсэн 2 функц байг.

1 үед тухайн i оройн жинг оруулсан.

0 үед тухайн i оройн жинг оруулаагүй.

dp(i, 0) = sum(max(dp(k, 0), dp(k, 1))), k = i оройн бүх хөрш хүү оройнууд

dp(i, 1) = sum(dp(k, 0))+jin(i). k = мөн i оройн бүх хөрш хүү оройнууд

Бодлогын хариу тэгвэл max(dp(i, 0), dp(i, 1)) байна.

source





За энэ хүрээт түр өндөрлөхгүй бол миний шалгалтандаа бэлдэх өнгөрлөө. Тун ойрын хугацаанд, хагас сайнаас өмнө ч юмуу Part II-г оруулна аа. Амжилт