某岛

… : "…アッカリ～ン . .. . " .. .

June 14, 2023

Luogu P2053. [SCOI2007] 修车

https://www.luogu.com.cn/problem/P2053
看起来可以 dp，不过每个人修每个车地代价并不相同。
于是可以二分图建模。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#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);
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

#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;
    G.s = s; G.t = t; G.n = 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);
}

Posted by xiaodao
Category: 日常