網頁

2014年4月16日 星期三

1459 Power Network

題意:
    有發電站(只發電不耗電),中繼站(不發電不耗電),和用電站(只耗電不發電)三種node,題目求所有用電站耗電量總和的最大値。
    輸入第一行有4個數字,n np nc m,n表示共有n站,np為發電站數量,nc為用電站數量,m為有m條電線。
    接下來有m組(u,v)z,表示u到v該電線的容量為z。然後有np個(u)z表示編號u發電站發電量為z;再接下來有nc個u(z)表示編號u為用電站最大用電量為z。
想法:
    最大流模板題,用super source串起所有發電站,super sink串起所有用電站。



沒有留言:

張貼留言