申論題

15. (5%) You are the program chair of a conference! Part of your job is to assign papers to 6 papers P1,P2,P3, P4,P5, P6 and 3 reviewers R1, R2, R3. Initially, each reviewer constructs a list of papers he is willing to review as followings: R1 ={P1,P3, P5, P6},R2 ={P1, P2,P4},R3={P1,P2,P3,P4, P5, P6}. An assignment of papers to reviewers is valid if each paper is assigned to at least 2distinct reviewers that are willing to review that paper. The maximum number of papers assigned to anyer should not be greater than 4. You would like to maximize the total number of pap are validly assigned. Please model this problem using a s-t flow network G = (V, E) (Draw a flow network with capacity labeling)._____ What is the maximum number of papers that can be validly assigned?_____