#include #include #include #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; }