結果

問題 No.654 Air E869120
コンテスト
ユーザー 加藤優佑
提出日時 2021-01-07 10:27:23
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,865 bytes
コンパイル時間 636 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 32,512 KB
最終ジャッジ日時 2024-11-08 00:04:50
合計ジャッジ時間 2,875 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MMAX 1000
#define MIN(a,b) ((a) < (b) ? (a) : (b))
struct node {
  int id;
  long long cap;
  struct node *next;
};
struct airline {
  int vertex;
  int ftime;
};
struct node **list;
int *level, *queue;
long long **flow;
int cmp_air(const void*, const void*);
void Insert(int, int, long long);
int Bfs(int, int, int);
long long Dfs(int, int, long long);
int main(void)
{
  int i, n, m, d, f[MMAX][5], alen = 1;
  long long 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;
    }
  }
  list = (struct node**)malloc(sizeof(struct node*) * alen);
  flow = (long long**)malloc(sizeof(long long*) * alen);
  level = (int*)malloc(sizeof(int) * alen);
  queue = (int*)malloc(sizeof(int) * alen);
  for (i = 0; i < alen; i++) {
    list[i] = NULL;
    flow[i] = (long long*)calloc(alen, sizeof(long));
  }
  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(uv[0], uv[1], f[i][4]);
  }
  for (i = 1; i < alen; i++) {
    if (a[i-1].vertex == a[i].vertex) Insert(i - 1, i, __LONG_LONG_MAX__);
  }
  while (Bfs(0, alen - 1, alen)) maxflow += Dfs(0, alen - 1, __LONG_LONG_MAX__);
  printf("%lld\n", maxflow);
  for (i = 0; i < alen; i++) {
    free(list[i]);
    free(flow[i]);
  }
  free(list);
  free(flow);
  free(level);
  free(queue);
}
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 Insert(int a, int b, long long c)
{
  struct node *p = (struct node*)malloc(sizeof(struct node));
  p->id = b;
  p->cap = c;
  p->next = list[a];
  list[a] = p;
  p = (struct node*)malloc(sizeof(struct node));
  p->id = a;
  p->cap = 0;
  p->next = list[b];
  list[b] = p;
}

int Bfs(int s, int t, int size)
{
  struct node *n;
  int i, head = 0, tail = 0;
  for (i = 0; i < size; i++) level[i] = -1;
  level[s] = 0;
  queue[tail++] = s;
  do {
    i = queue[head++];
    for (n = list[i]; n != NULL; n = n->next) {
      int v = n->id;
      if (level[v] < 0 && flow[i][v] < n->cap) {
        queue[tail++] = v;
        level[v] = level[i] + 1;
      }
    }
  } while (head != tail);
  return level[t] >= 0;
}

long long Dfs(int u, int t, long long f)
{
  long long fsum = 0;
  struct node *n;
  if (u == t) return f;
  for (n = list[u]; n != NULL; n = n->next) {
    int v = n->id;
    if (level[u] < level[v] && flow[u][v] < n->cap) {
      long long ftemp = Dfs(v, t, MIN(f - fsum, n->cap - flow[u][v]));
      if (ftemp > 0) {
        flow[u][v] += ftemp;
        flow[v][u] -= ftemp;
        fsum += ftemp;
        if (fsum == f) break;
      }
    }
  }
  return fsum;
}
0