結果

問題 No.654 Air E869120
コンテスト
ユーザー akakimidori
提出日時 2019-03-24 01:16:56
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 5,088 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 33,024 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-25 04:54:58
合計ジャッジ時間 1,759 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef int64_t flow_type;

const flow_type flow_inf = (int64_t) 1000000000 * 1000;

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 *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;
}

flow_type dinic_dfs (const int32_t v, 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 (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) {
      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;
}

typedef int32_t i32;
typedef int64_t i64;

typedef struct node {
  i32 v;
  i32 t;
} node;

int cmpNode (const void *a, const void *b) {
  node *p = (node *) a;
  node *q = (node *) b;
  if (p->v != q->v) return p->v < q->v ? -1 : 1;
  i32 d = p->t - q->t;
  return d == 0 ? 0 : d < 0 ? -1 : 1;
}

i32 toIndex (node *z, i32 len, node v) {
  i32 l = 0;
  i32 r = len;
  while (r - l > 1) {
    i32 m = (l + r) / 2;
    int c = cmpNode (&v, z + m);
    if (c == 0) return m;
    if (c < 0) {
      r = m;
    } else {
      l = m;
    }
  }
  return l;
}

void run(void){
  i32 n, m, d;
  scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &n, &m, &d);
  i32 *u = (i32 *) calloc (5 * m, sizeof (i32));
  i32 *v = u + m;
  i32 *p = v + m;
  i32 *q = p + m;
  i32 *w = q + m;
  node *z = (node *) calloc (2 * m + 2, sizeof (node));
  for (i32 i = 0; i < m; ++i) {
    for (i32 j = i; j < 5 * m; j += m) {
      scanf("%" SCNi32, u + j);
    }
    q[i] += d;
    z[i] = (node) {u[i], p[i]};
    z[i + m] = (node) {v[i], q[i]};
  }
  z[2 * m] = (node) {1, 0};
  z[2 * m + 1] = (node) {n, 2000000000};
  qsort (z, 2 * m + 2, sizeof (node), cmpNode);
  i32 len = 1;
  for (i32 i = 1; i < 2 * m + 1; ++i) {
    if (cmpNode (z + len - 1, z + i) == 0) continue;
    z[len++] = z[i];
  }
  graph *g = new_graph (len);
  const i32 src = 0;
  const i32 dst = len - 1;
  for (i32 i = 0; i < m; ++i) {
    i32 a = toIndex (z, len, (node) {u[i], p[i]});
    i32 b = toIndex (z, len, (node) {v[i], q[i]});
    add_edge (g, a, b, w[i]);
  }
  for (i32 i = 0; i < len - 1; ++i) {
    if (z[i].v == z[i + 1].v) {
      add_edge (g, i, i + 1, flow_inf);
    }
  }
  i64 ans = dinic (g, src, dst);
  printf("%" PRIi64 "\n", ans);
}

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