היי, יש לי שאלה בנוגע לשאלה 3 מהמבחן (מצורף קישור)
http://tau-algorithms.wdfiles.com/local--files/exams/exam_2018a_moed-b.pdf
בפתרון שראיתי שקיבל את כל הניקוד, הקשתות שנמתחו מהאיברים
1,…n^2
לעבר t היו כולן בקיבול 1.
לא הבנתי מדוע. להבנתי הקיבול צריך להיות k/n.
כאשר לקבוצות Ai אני מותחת קשתות בקיבול k מ-s
ובין Ai לכל האיברים שנמצאים בה קשתות בקיבול 1.
אם k<n אז ברור שאין לבעיה פיתרון.
כמו כן, לא ייתכן ש k>n^2.
לא ביקשו קבוצות זרות, אלא רק שכל איבר יבחר. לכן הרעיון שלי היה להגדיר קיבול k/n על הקשתות בין האיברים לt
ואחפש זרימה בגודל n*k
כלומר להבנתי קיבולים 1 בין האיברים ל-t
לא יבטיח לי את המבוקש גם אם אמצא זרימה מקסימלית בגודל n*k.
בנוסף בנוגע לניתוח -
בגלל שK חסום כפי שציינתי, ל
לפני שיפורים קיבלתי O(n^7) בדיניץ
לאחר שיפורים קיבלתי O(k*n^4)
גם מFF
וגם מדיניץ ברשת 0-1
אשמח לעזרה כי בבדיקה נטען שהפתרון הוא n^5
תודה רבה!