שאלה: נתונה רשת זרימה, ידוע כי כל קיבולי הקשתות הן שורש 2 מלבד קשת אחת עם קיבול 2. תאר אלג' יעיל למציאת זרימה מקסימאלית.
הרעיון שלי היה לגרום לכל קשת להיות בקיבול 1, ואז להשתמש בדיניץ על רשת 0-1 ובסוף להכפיל בשורש 2 את הזרימה המקסימאלית - וככה גם נעשה ברפרנס.
אבל ברפרנס כתבו שצריך לעשות עוד בדיקה לראות מה עם הקשת שבקיבול 2.
האם צריך להתייחס אליה בכלל?
עד כמה שאני מבין, אלא אם הקשת הזאת היא ישירה בין המקור לבור (ואת זה קל לוודא), היא תהיה על מסלול ביניהם שכל שאר הקשתות בו יהיו בקיבול שורש 2 - ולכן הזרימה דרכה לא תהיה יותר משורש 2