網頁

2014年4月18日 星期五

UVa 10779 Collectors Problem

題意:
    有N個人(含Bob)以及M種貼紙(編號1~M),每個人手上有不同種類的貼紙數張,Bob要透過和別人交換貼紙使得他擁有最多種類的貼紙。交換規則為,除了Bob以外的其他人只與Bob交換,且只有當手中該種類貼紙大於1張時才會交換沒有的種類,也就是Bob要用某甲手中沒有的貼紙種類與某甲交換,且某甲只當該種類他有大於1張時他才願意換出那張貼紙。
    輸入第一行N M,接下來N行,每行第一個數字K表示那個人有K張貼紙,後面K個數字分別為每張貼紙的種類編號。N行中第一行為Bob。
    輸出Bob最多能擁有幾種貼紙。

想法:
    建圖做最大流,建圖方法為:
  1. 每個人i擁有j種類貼紙d張,則cap[i][j]=d,表示人與該種貼紙之間的容量為那個人擁有該種貼紙的張數。
  2. "除了Bob以外",每個人i如果擁有j種類貼紙(也就是cap[i][j]>=1),則將cap[i][j]--,因為他要保留一張絕對不交換出去,如果cap[i][j]==0,表示那個人沒有j種類貼紙,所以他願意換入該種類貼紙1張,因此把cap[j][i]=1。
  3. 因為最後只要輸出Bob有幾種貼紙,建立每種貼紙到super sink(T)的容量為1。