網頁

2014年4月16日 星期三

POJ 2584 T-Shirt Gumbo

題意:
  以sample input舉例
START 4     -> 4表示有4個人
SM ML LX XT    -> 第一人能穿的衣服Size從S~M,第二人從M~L,...
0 1 1 1 0    -> 衣服S號有0件,M號有1件,L號有1件,X號有1件,T號有0件
END
    求出是否能將衣服分配給所有人。
想法:
    最大流題目,S表示super source,T表示super sink,S到每個人的容量為1,因為每個人只需要一件衣服;每種size的衣服到T的容量為該種size衣服的數量;然後做最大流,並判斷最後的數量是否與人數一樣。