結果

問題 No.957 植林
ユーザー akakimidoriakakimidori
提出日時 2019-12-21 11:25:00
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 626 ms / 2,000 ms
コード長 5,098 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 31,556 KB
実行使用メモリ 5,216 KB
最終ジャッジ日時 2023-09-26 09:48:02
合計ジャッジ時間 15,976 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,380 KB
testcase_01 AC 0 ms
4,384 KB
testcase_02 AC 0 ms
4,376 KB
testcase_03 AC 28 ms
4,596 KB
testcase_04 AC 27 ms
4,376 KB
testcase_05 AC 24 ms
4,488 KB
testcase_06 AC 34 ms
4,768 KB
testcase_07 AC 34 ms
4,504 KB
testcase_08 AC 15 ms
4,504 KB
testcase_09 AC 15 ms
4,584 KB
testcase_10 AC 16 ms
4,696 KB
testcase_11 AC 16 ms
4,672 KB
testcase_12 AC 16 ms
4,516 KB
testcase_13 AC 13 ms
4,384 KB
testcase_14 AC 17 ms
4,744 KB
testcase_15 AC 15 ms
4,536 KB
testcase_16 AC 15 ms
4,384 KB
testcase_17 AC 14 ms
4,416 KB
testcase_18 AC 442 ms
4,652 KB
testcase_19 AC 463 ms
4,656 KB
testcase_20 AC 503 ms
4,732 KB
testcase_21 AC 522 ms
4,888 KB
testcase_22 AC 528 ms
4,896 KB
testcase_23 AC 556 ms
4,852 KB
testcase_24 AC 591 ms
4,984 KB
testcase_25 AC 613 ms
5,016 KB
testcase_26 AC 617 ms
5,056 KB
testcase_27 AC 626 ms
5,144 KB
testcase_28 AC 602 ms
5,188 KB
testcase_29 AC 606 ms
5,180 KB
testcase_30 AC 604 ms
5,180 KB
testcase_31 AC 428 ms
4,488 KB
testcase_32 AC 460 ms
4,652 KB
testcase_33 AC 488 ms
4,804 KB
testcase_34 AC 512 ms
4,748 KB
testcase_35 AC 539 ms
4,832 KB
testcase_36 AC 555 ms
4,960 KB
testcase_37 AC 588 ms
4,992 KB
testcase_38 AC 610 ms
5,144 KB
testcase_39 AC 601 ms
5,108 KB
testcase_40 AC 620 ms
5,216 KB
testcase_41 AC 11 ms
5,104 KB
testcase_42 AC 10 ms
5,056 KB
testcase_43 AC 18 ms
5,112 KB
testcase_44 AC 19 ms
5,076 KB
testcase_45 AC 0 ms
4,376 KB
testcase_46 AC 0 ms
4,380 KB
testcase_47 AC 1 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;
typedef int64_t i64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

typedef i64 flow_type;

const flow_type flow_inf = 90000000000000;

typedef struct flow_edge {
  int32_t vertex;
  int32_t next;
  flow_type capacity;
} flow_edge;

typedef struct maxFlowGraph {
  flow_edge *edge;
  int32_t *start;
  int32_t vertex_num;
  int32_t pointer;
  int32_t edge_length;
} graph;

graph* new_graph (const int32_t vertex_num) {
  graph * const g = (graph *) calloc (1, sizeof (graph));
  g->vertex_num = vertex_num;
  const int32_t initial_length = 4;
  g->edge = (flow_edge *) calloc (initial_length, sizeof (flow_edge));
  g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  g->pointer = 0;
  g->edge_length = initial_length;
  for (int32_t i = 0; i < vertex_num; ++i) {
    g->start[i] = -1;
  }
  return g;
}

void free_graph (graph * const g) {
  free (g->edge);
  free (g->start);
  free (g);
}

void clear_graph (graph * const g) {
  g->pointer = 0;
  memset (g->start, -1, sizeof (int32_t) * g->vertex_num);
}

void add_edge (graph * const g, const int32_t from, const int32_t to, const flow_type capa) {
  if (g->pointer == g->edge_length) {
    g->edge_length *= 2;
    g->edge = (flow_edge *) realloc (g->edge, sizeof (flow_edge) * g->edge_length);
  }
  const int32_t p = g->pointer;
  g->edge[p] = (flow_edge) {to, g->start[from], capa};
  g->start[from] = p;
  g->edge[p + 1] = (flow_edge) {from, g->start[to], 0};
  g->start[to] = p + 1;
  g->pointer += 2;
}

void add_edge_undirected (graph * const g, const int32_t u, const int32_t v, const flow_type capa) {
  if (g->pointer == g->edge_length) {
    g->edge_length *= 2;
    g->edge = (flow_edge *) realloc (g->edge, sizeof (flow_edge) * g->edge_length);
  }
  const int32_t p = g->pointer;
  g->edge[p] = (flow_edge) {v, g->start[u], capa};
  g->start[u] = p;
  g->edge[p + 1] = (flow_edge) {u, g->start[v], capa};
  g->start[v] = p + 1;
  g->pointer += 2;
}

flow_type dinic_dfs (const int32_t v, const graph * const g, const int32_t dst, const int32_t * const level, int32_t * const iter, flow_type e) {
  if (v == dst) return e;
  flow_type sum = 0;
  for (int32_t p = iter[v]; p != -1; p = g->edge[p].next, iter[v] = p) {
    const int32_t u = g->edge[p].vertex;
    const flow_type capa = g->edge[p].capacity;
    if (level[u] <= level[v] || capa <= 0) continue;
    const flow_type f = dinic_dfs (u, g, dst, level, iter, capa < e ? capa : e);
    if (f > 0) {
      g->edge[p].capacity -= f;
      g->edge[p ^ 1].capacity += f;
      sum += f;
      e -= f;
      if (e <= 0) return sum;
    }
  }
  return sum;
}

flow_type dinic (const graph * const g, const int32_t src, const int32_t dst) {
  const int32_t vertex_num = g->vertex_num;
  int32_t * const level = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  int32_t * const queue = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  int32_t * const iter  = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  flow_type flow = 0;
  while (1) {
    memset (level, 0, sizeof (int32_t) * vertex_num);
    int32_t front = 0;
    int32_t last = 0;
    level[dst] = vertex_num;
    queue[last++] = dst;
    while (front < last && level[src] == 0) {
      const int32_t v = queue[front++];
      for (int32_t p = g->start[v]; p!=-1; p = g->edge[p].next) {
        const int32_t u = g->edge[p].vertex;
        if (g->edge[p ^ 1].capacity > 0 && level[u] == 0) {
          level[u] = level[v] - 1;
          queue[last++] = u;
        }
      }
    }
    if (level[src] == 0) break;
    memcpy (iter, g->start, sizeof (int32_t) * vertex_num);
    while (1) {
      const flow_type f = dinic_dfs (src, g, dst, level, iter, flow_inf);
      if (f <= 0) break;
      flow += f;
    }
  }
  free (level);
  free (queue);
  free (iter);
  return flow;
}

void run(void) {
    i32 h, w;
    scanf ("%" SCNi32 "%" SCNi32, &h, &w);
    i32 *a = ALLOC (h * w, i32);
    i32 *r = ALLOC (h, i32);
    i32 *c = ALLOC (w, i32);
    for (i32 i = 0; i < h; ++i) {
        for (i32 j = 0; j < w; ++j) {
            scanf ("%" SCNi32, a + i * w + j);
        }
    }
    for (i32 i = 0; i < h; ++i) {
        scanf ("%" SCNi32, r + i);
    }
    for (i32 j = 0; j < w; ++j) {
        scanf ("%" SCNi32, c + j);
    }
    graph *g = new_graph(h + w + 2);
    const i32 src = h + w;
    const i32 dst = src + 1;
    for (i32 i = 0; i < h; ++i) {
        i64 local = 0;
        for (i32 j = 0; j < w; ++j) {
            add_edge(g, h + j, i, a[i * w + j]);
            local += a[i * w + j];
        }
        add_edge(g, i, dst, local);
    }
    i64 sum = 0;
    for (i32 i = 0; i < h; ++i) {   
        sum += r[i];
        add_edge(g, src, i, r[i]);
    }
    for (i32 j = 0; j < w; ++j) {
        sum += c[j];
        add_edge(g, src, h + j, c[j]);
    }
    i64 ans = sum - dinic(g, src, dst);
    printf("%" PRIi64 "\n", ans);
}

int main(void) {
    run();
    return 0;
}
0