1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| int in[45][45]; int point[45][45], cnt;
int main() { m = read(); n = read(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m + i - 1; ++j) { in[i][j] = read(); point[i][j] = ++cnt; } }
s = 0; t = cnt * 2 + 1; for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0); for (int i = 1; i <= n + m - 1; ++i) add(point[n][i] + cnt, t, 1, 0); for (int i = 1; i <= n; ++i) { if (i < n) for (int j = 1; j <= m + i - 1; ++j) { add(point[i][j] + cnt, point[i + 1][j], 1, 0); add(point[i][j] + cnt, point[i + 1][j + 1], 1, 0); } for (int j = 1; j <= m + i - 1; ++j) add(point[i][j], point[i][j] + cnt, 1, in[i][j]); } ansflow = MaxCostMaxFlow(anscost); printf("%lld\n", anscost);
edges.clear(); for (int i = 0; i < maxn; ++i) G[i].clear(); s = 0; t = cnt + 1; for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0); for (int i = 1; i <= n + m - 1; ++i) add(point[n][i], t, inf, in[n][i]); for (int i = 1; i < n; ++i) for (int j = 1; j <= m + i - 1; ++j) { add(point[i][j], point[i + 1][j], 1, in[i][j]); add(point[i][j], point[i + 1][j + 1], 1, in[i][j]); } ansflow = MaxCostMaxFlow(anscost); printf("%lld\n", anscost);
edges.clear(); for (int i = 0; i < maxn; ++i) G[i].clear(); s = 0; t = cnt + 1; for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0); for (int i = 1; i <= n + m - 1; ++i) add(point[n][i], t, inf, in[n][i]); for (int i = 1; i < n; ++i) for (int j = 1; j <= m + i - 1; ++j) { add(point[i][j], point[i + 1][j], inf, in[i][j]); add(point[i][j], point[i + 1][j + 1], inf, in[i][j]); } ansflow = MaxCostMaxFlow(anscost); printf("%lld\n", anscost);
return 0; }
|