Luogu P2050. [NOI2012] Food Festival

Original link: https://www.shuizilong.com/house/archives/luogu-p2050-noi2012-%E7%BE%8E%E9%A3%9F%E8%8A%82/

• https://www.luogu.com.cn/problem/P2050

You can get 60 points by using the method of the previous question , and consider optimization. We found that for each chef, the edge it uses must be a set of prefixes, so it can be greedy to add new edges dynamically after each augmentation.

  
   
#include <lastweapon/io>  
   
#include <lastweapon/mincostflow>  
   
using namespace lastweapon;  
   
  
   
int main() {  
   
  
   
#ifndef ONLINE_JUDGE  
   
    freopen("in.txt", "r", stdin);  
   
    //freopen("out.txt", "w", stdout);  
   
#endif  
   
  
   
    int n, m, p; RD(n, m); p = 800; int s = n+m*p, t = s+1, nn = 0;  
   
    mcf_graph<int, int> G(t+1);  
   
  
   
    REP(i, n) G.add_edge(s, i, RD(), 0);  
   
    REP(i, p) REP(j, m) G. add_edge(n+p*j+i, t, 1, 0);  
   
  
   
    REP(i, n) REP(j, m) {  
   
        int c; RD(c); REP(k, p) G.add_edge(i, n+p*j+k, 1, (k+1)*c);  
   
    }  
   
  
   
    printf("%d\n", G.flow(s, t).se);  
   
}  
   
  
   

This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p2050-noi2012-%E7%BE%8E%E9%A3%9F%E8%8A%82/
This site is only for collection, and the copyright belongs to the original author.