結果
| 問題 |
No.654 Air E869120
|
| コンテスト | |
| ユーザー |
 denderaKawazu
|
| 提出日時 | 2019-01-24 18:00:07 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,116 bytes |
| コンパイル時間 | 3,465 ms |
| コンパイル使用メモリ | 85,320 KB |
| 実行使用メモリ | 56,220 KB |
| 最終ジャッジ日時 | 2024-09-16 04:39:46 |
| 合計ジャッジ時間 | 8,577 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 31 WA * 4 |
ソースコード
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Comparator;
import java.util.ArrayDeque;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
FastScanner in = new FastScanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(1, in, out);
out.close();
}
static class Task {
public void solve(int testNumber, FastScanner in, PrintWriter out) {
int n = in.nextInt();
int m = in.nextInt();
int d = in.nextInt();
Task.Schedule[] schedules = new Task.Schedule[m];
for (int i = 0; i < m; i++)
schedules[i] = new Task.Schedule(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt(), in.nextLong());
Arrays.sort(schedules, Comparator.comparing(Task.Schedule::getP));
Dinic dinic = new Dinic(m + 2);
for (int i = 0; i < m; i++) {
Task.Schedule cs = schedules[i];
int t = cs.getQ() + d;
if (cs.getU() == 1)
dinic.setEdge(m, i, cs.getW());
if (cs.getV() == n) {
dinic.setEdge(i, m + 1, cs.getW());
continue;
}
for (int j = m - 1; schedules[j].getP() >= t; j--) {
if (schedules[j].getU() == cs.getV()) {
dinic.setEdge(i, j, cs.getW());
}
}
}
out.println(dinic.getMaxFlow(m, m + 1));
}
static class Schedule {
int u;
int v;
int p;
int q;
long w;
Schedule(int u, int v, int p, int q, long w) {
this.u = u;
this.v = v;
this.p = p;
this.q = q;
this.w = w;
}
public int getU() {
return u;
}
public int getV() {
return v;
}
public int getP() {
return p;
}
public int getQ() {
return q;
}
public long getW() {
return w;
}
}
}
static class FastScanner {
private InputStream in;
private byte[] buffer = new byte[1024];
private int bufPointer;
private int bufLength;
public FastScanner(InputStream in) {
this.in = in;
}
private int readByte() {
if (bufPointer >= bufLength) {
if (bufLength == -1)
throw new InputMismatchException();
bufPointer = 0;
try {
bufLength = in.read(buffer);
} catch (IOException e) {
throw new InputMismatchException();
}
if (bufLength <= 0)
return -1;
}
return buffer[bufPointer++];
}
private static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public long nextLong() {
long n = 0;
int b = readByte();
while (isSpaceChar(b))
b = readByte();
boolean minus = (b == '-');
if (minus)
b = readByte();
while (b >= '0' && b <= '9') {
n *= 10;
n += b - '0';
b = readByte();
}
if (!isSpaceChar(b))
throw new NumberFormatException();
return minus ? -n : n;
}
public int nextInt() {
long n = nextLong();
if (n < Integer.MIN_VALUE || n > Integer.MAX_VALUE)
throw new NumberFormatException();
return (int) n;
}
}
static class Dinic {
private ArrayList<Dinic.Edge>[] graph;
private int[] dist;
private int[] start;
public Dinic(int vertexNum) {
dist = new int[vertexNum];
start = new int[vertexNum];
graph = new ArrayList[vertexNum];
for (int i = 0; i < vertexNum; i++)
graph[i] = new ArrayList<>();
}
public void setEdge(int from, int to, long cap) {
Dinic.Edge e = new Dinic.Edge(to, cap);
e.rev = new Dinic.Edge(from, 0, e);
graph[from].add(e);
graph[to].add(e.rev);
}
public long getMaxFlow(int source, int sink) {
long flow = 0;
while (true) {
setDistBFS(source);
if (dist[sink] == -1)
return flow;
Arrays.fill(start, 0);
long df = sendFlowDFS(source, sink, Long.MAX_VALUE);
while (df > 0) {
flow += df;
df = sendFlowDFS(source, sink, Long.MAX_VALUE);
}
}
}
private void setDistBFS(int zero) {
Arrays.fill(dist, -1);
dist[zero] = 0;
Queue<Integer> vq = new ArrayDeque<>();
vq.add(zero);
while (!vq.isEmpty()) {
int cv = vq.poll();
for (Dinic.Edge e : graph[cv]) {
if (e.cap > 0 && dist[e.to] == -1) {
dist[e.to] = dist[cv] + 1;
vq.add(e.to);
}
}
}
}
private long sendFlowDFS(int cv, int source, long flow) {
if (cv == source)
return flow;
while (start[cv] < graph[cv].size()) {
Dinic.Edge e = graph[cv].get(start[cv]);
if (e.cap > 0 && dist[cv] < dist[e.to]) {
long d = sendFlowDFS(e.to, source, Math.min(e.cap, flow));
if (d > 0) {
e.cap -= d;
e.rev.cap += d;
return d;
}
}
start[cv]++;
}
return 0;
}
private static class Edge {
int to;
Dinic.Edge rev;
long cap;
Edge(int to, long cap) {
this.to = to;
this.cap = cap;
}
Edge(int to, long cap, Dinic.Edge rev) {
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
}
}