1149:PIGS

keyword

最大流　C++

概要

豚小屋がM(<1000)個あり、最初はx_i(<1000)匹豚が入っている。N(<100)日間客が来る。客は豚小屋の鍵をいくつか持っていて、豚小屋の鍵を全て開ける。小屋からでられる豚は客にy_j匹まで売りつけることができる。その後豚を空いている小屋に再配置する。そして全ての小屋に鍵をかける。このとき、ひとつの豚小屋に何匹詰めても良い。最大で何匹の豚を売り払うことができるか求める問題。
最大流を流して解く。まず、ソースからM個のノードに流量x_iの辺を張る。またnext[i] = iと初期化する。次に、1日目に来る客から順次辺とノードを追加していく。持っている鍵に対して、S = {next[key]}を求め、next[key]を全て新しいノードの番号に更新する。そして全てのSの元から、新しいノードへの流量無限大の辺を張る。そして新しいノードからシンクへ流量y_jの辺を張る。あとは流すだけ。計算量は、辺の数がよく分からないので正確には把握していない。多分|E| = O(|V|^2)にはならないはず。
それにしても、自分の頭で考えて最大流の問題を解いたのはこれが初めてかも知れない。でもこの問題正当率高いし、見る人が見たらきっと「流すだけ」とか言われるような気がする。

int main(){
    int M, N;
    scanf("%d%d",&M,&N);
    for(int i=1; i<=M; i++)
        next[i] = i;
    for(int i=0; i<M; i++){
        int x;
        scanf("%d",&x);
        add_edge(0,i+1,x);
    }
    for(int i=0; i<N; i++){
        int k, x;
        scanf("%d",&k);
        vector<int> froms;
        for(int j=0; j<k; j++){
            scanf("%d",&x);
            froms.push_back(next[x]);
            next[x] = M+i+1;
        }
        sort(froms.begin(), froms.end());
        froms.erase(unique(froms.begin(), froms.end()), froms.end());
        for(int j=0; j<froms.size(); j++)
            add_edge(froms[j], M+i+1, 1<<29);
        scanf("%d",&x);
        add_edge(M+i+1, M+N+1, x);
    }
    printf("%d\n",max_flow(0,M+N+1));
    return 0;
}