Luogu P2053. [SCOI2007] Car Repair

Original link: https://www.shuizilong.com/house/archives/luogu-p2053-scoi2007-%E4%BF%AE%E8%BD%A6/

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

  It seems that dp is possible, but the cost of repairing each car is not the same for each person.

  So it can be modeled as a bipartite graph.

  
   
#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 m, n; RD(m, n); int s = n*(m+1), t = s+1;  
   
    mcf_graph<int, int> G(t+1);  
   
  
   
    REP(i, n) {  
   
        G. add_edge(s, i, 1, 0);  
   
        REP(j, m) {  
   
            G.add_edge(n*(j+1)+i, t, 1, 0);  
   
            int c; RD(c); REP(k, n) G.add_edge(i, n*(j+1)+k, 1, (k+1)*c);  
   
        }  
   
    }  
   
    printf("%.2f\n", (DB)G.flow(s, t).se / n);  
   
}  
   

  
   
#include <lastweapon/mincostflow2>  
   
using namespace lastweapon;  
   
  
   
int main() {  
   
  
   
#ifndef ONLINE_JUDGE  
   
    freopen("in.txt", "r", stdin);  
   
    //freopen("out.txt", "w", stdout);  
   
#endif  
   
  
   
    int m, n; RD(m, n); int s = n*(m+1), t = s+1;  
   
    mcf_graph<int, int, 2047, 105536, 2047> G;  
   
    Gs = s; Gt = t; Gn = t+1;  
   
  
   
    REP(i, n) {  
   
        G. add_edge(s, i, 1, 0);  
   
        REP(j, m) {  
   
            G.add_edge(n*(j+1)+i, t, 1, 0);  
   
            int c; RD(c); REP(k, n) G.add_edge(i, n*(j+1)+k, 1, (k+1)*c);  
   
        }  
   
    }  
   
  
   
    printf("%.2f\n", (DB)G.Run().se / n);  
   
}  
   
  
   

This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p2053-scoi2007-%E4%BF%AE%E8%BD%A6/
This site is only for collection, and the copyright belongs to the original author.