結果

問題 No.654 Air E869120
コンテスト
ユーザー 加藤優佑
提出日時 2021-01-09 01:03:12
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 4,629 bytes
コンパイル時間 490 ms
コンパイル使用メモリ 32,640 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 20:42:44
合計ジャッジ時間 2,111 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MMAX 1000
#define MIN(a,b) ((a) < (b) ? (a) : (b))

typedef long long flow_type;

struct flow_edge{
  int vertex;
  int next;
  flow_type capacity;
};

struct flow_graph{
  struct flow_edge *edge;
  int *start;
  int vertex_num;
  int pointer;
  int edge_length;
};
struct airline {
  int vertex;
  int ftime;
};

struct flow_graph *graph;
int *level;
int Cmp_air(const void*, const void*);
void Create_graph(int);
void Insert_edge(int, int, flow_type);
void Free_graph(void);
int Bfs(int, int, int);
flow_type Dfs(int, int, flow_type);
int main(void)
{
  int i, n, m, d, f[MMAX][5], alen = 1;
  flow_type maxflow = 0;
  struct airline a[2*MMAX+2];
  scanf("%d %d %d", &n, &m, &d);
  for (i = 0; i < m; i++) {
    scanf("%d %d %d %d %d", &f[i][0], &f[i][1], &f[i][2], &f[i][3], &f[i][4]);
    f[i][3] += d;
    a[i*2].vertex = f[i][0];
    a[i*2].ftime = f[i][2];
    a[i*2+1].vertex = f[i][1];
    a[i*2+1].ftime = f[i][3];
  }
  a[m*2].vertex = 1;
  a[m*2].ftime = 0;
  a[m*2+1].vertex = n;
  a[m*2+1].ftime = 2000000000;
  qsort(a, 2 * m + 2, sizeof(struct airline), Cmp_air);
  /*for (i = 1; i < 2 * m + 2; i++) {
    if (Cmp_air(&a[alen-1], &a[i])) {
      a[alen].vertex = a[i].vertex;
      a[alen++].ftime = a[i].ftime;
    }
  }*/
  alen = 2 * m + 2;
  level = (int*)malloc(sizeof(int) * alen);
  Create_graph(alen);
  for (i = 0; i < m; i++) {
    int lo, hi, mid, uv[2];
    struct airline ta;
    lo = 0;
    hi = alen - 1;
    ta.vertex = f[i][0];
    ta.ftime = f[i][2];
    while (lo <= hi) {
      mid = (lo + hi) / 2;
      if (Cmp_air(&a[mid], &ta) > 0) hi = mid - 1;
      else lo = mid + 1;
    }
    uv[0] = hi;
    lo = 0;
    hi = alen - 1;
    ta.vertex = f[i][1];
    ta.ftime = f[i][3];
    while (lo <= hi) {
      mid = (lo + hi) / 2;
      if (Cmp_air(&a[mid], &ta) > 0) hi = mid - 1;
      else lo = mid + 1;
    }
    uv[1] = hi;
    Insert_edge(uv[0], uv[1], f[i][4]);
  }
  for (i = 1; i < alen; i++) {
    if (a[i-1].vertex == a[i].vertex) Insert_edge(i - 1, i, __LONG_LONG_MAX__);
  }
  while (Bfs(0, alen - 1, alen)) maxflow += Dfs(0, alen - 1, __LONG_LONG_MAX__);
  printf("%lld\n", maxflow);
  Free_graph();
  free(level);
}
int Cmp_air(const void *a, const void *b)
{
  struct airline *ta = (struct airline*)a, *tb = (struct airline*)b;
  if (ta->vertex > tb->vertex) return 1;
  else if (ta->vertex < tb->vertex) return -1;
  else {
    if (ta->ftime > tb->ftime) return 1;
    else if (ta->ftime < tb->ftime) return -1;
    else return 0;
  }
}
void Create_graph(int vertex_num){
  int i, initial_length = 2;
  graph = (struct flow_graph*)calloc(1, sizeof(struct flow_graph));
  graph->vertex_num = vertex_num;
  graph->edge = (struct flow_edge*)calloc(initial_length, sizeof(struct flow_edge));
  graph->start = (int*)calloc(vertex_num, sizeof(int));
  graph->pointer = 0;
  graph->edge_length = initial_length;
  for(i = 0; i < vertex_num; i++) graph->start[i] = -1;
}

void Insert_edge(int from, int to, flow_type capa){
  int p = graph->pointer;
  if(graph->pointer == graph->edge_length){
    graph->edge_length *= 2;
    graph->edge = (struct flow_edge*)realloc(graph->edge, sizeof(struct flow_edge) * graph->edge_length);
  }
  graph->edge[p].vertex = to;
  graph->edge[p].next = graph->start[from];
  graph->edge[p].capacity = capa;
  graph->start[from] = p;
  graph->edge[p+1].vertex = from;
  graph->edge[p+1].next = graph->start[to];
  graph->edge[p+1].capacity = 0;
  graph->start[to] = p + 1;
  graph->pointer += 2;
}

void Free_graph(void)
{
  free(graph->edge);
  free(graph->start);
  free(graph);
}

int Bfs(int s, int t, int size)
{
  int i, p, head = 0, tail = 0, queue[size];
  for (i = 0; i < size; i++) level[i] = -1;
  level[s] = 0;
  queue[tail++] = s;
  do {
    i = queue[head++];
    for (p = graph->start[i]; p != -1; p = graph->edge[p].next) {
      int v = graph->edge[p].vertex;
      if (level[v] < 0 && graph->edge[p].capacity > 0) {
        queue[tail++] = v;
        level[v] = level[i] + 1;
      }
    }
  } while (head != tail);
  return level[t] >= 0;
}

flow_type Dfs(int u, int t, flow_type f)
{
  int p;
  flow_type fsum = 0;
  if (u == t) return f;
  for (p = graph->start[u]; p != -1; p = graph->edge[p].next) {
    int v = graph->edge[p].vertex;
    if (level[u] < level[v] && graph->edge[p].capacity > 0) {
      flow_type ftemp = Dfs(v, t, MIN(f - fsum, graph->edge[p].capacity));
      if (ftemp > 0) {
        graph->edge[p].capacity -= ftemp;
        graph->edge[p^1].capacity += ftemp;
        fsum += ftemp;
        if (fsum == f) break;
      }
    }
  }
  return fsum;
}
0