מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/תרגילים/מערך הייצור באישימוטו/שאלה

קונצרן המכוניות היפני אישימוטו מעוניין להעביר את מערך הייצור שלו לישראל. הגרף הבא מתאר את המצב בישראל. הצמתים $\displaystyle s_{1},\ldots ,s_{m}$ מתארים את מיקומם של המפעלים שהקונצרן רוצה לבנות. הצמתים $\displaystyle t_{1},\ldots ,t_{n}$ מתארים נמלים (דרכם שולחים את המכוניות לחו"ל). שאר הצמתים הם צמתי ביניים. הקשתות מתארות כבישים, וקיבוליהם מתארים את מספר המכוניות ליחידת זמן שאפשר לשלוח דרכם.

נתונים המספרים $\displaystyle x_{1},\ldots ,x_{m}$, המתארים את מספר המכוניות לשעה שהקונצרן מתכנן לייצור ב$\displaystyle s_{1},\ldots ,s_{m}$. אנא מצא אלגוריתם יעיל המוצא האם המפעלים יוכלו לייצר מכוניות כך שלא ייווצר צואר בקבוק. (הנח שכל נמל מסוגל לטפל בכל כמות מכוניות ליחידת זמן).

.