結果

問題 No.2604 Initial Motion
ユーザー ks2m
提出日時 2024-01-12 23:24:18
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,058 ms / 3,000 ms
コード長 7,915 bytes
コンパイル時間 3,911 ms
コンパイル使用メモリ 84,552 KB
実行使用メモリ 52,280 KB
最終ジャッジ日時 2024-09-28 00:11:22
合計ジャッジ時間 28,589 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int k = Integer.parseInt(sa[0]);
int n = Integer.parseInt(sa[1]);
int m = Integer.parseInt(sa[2]);
sa = br.readLine().split(" ");
int[] a = new int[n];
for (int i = 0; i < k; i++) {
a[Integer.parseInt(sa[i]) - 1]++;
}
int s = n;
int t = s + 1;
MinCostFlow mcf = new MinCostFlow(t + 1);
sa = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
int b = Integer.parseInt(sa[i]);
mcf.addEdge(i, t, b, 0);
mcf.addEdge(s, i, a[i], 0);
}
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
int u = Integer.parseInt(sa[0]) - 1;
int v = Integer.parseInt(sa[1]) - 1;
long d = Long.parseLong(sa[2]);
mcf.addEdge(u, v, n, d);
mcf.addEdge(v, u, n, d);
}
br.close();
long[] res = mcf.flow(s, t);
System.out.println(res[1]);
}
}
class MinCostFlow {
private final int n;
private List<int[]> pos;
private List<List<Edge2>> g;
class Edge {
/** */
final int from;
/** */
final int to;
/** */
long cap;
/** */
long flow;
/** 1 */
long cost;
public Edge(int from, int to, long cap, long flow, long cost) {
this.from = from;
this.to = to;
this.cap = cap;
this.flow = flow;
this.cost = cost;
}
}
private class Edge2 {
final int to, rev;
long cap, cost;
public Edge2(int to, int rev, long cap, long cost) {
this.to = to;
this.rev = rev;
this.cap = cap;
this.cost = cost;
}
}
private class Q {
final long key;
final int to;
public Q(long key, int to) {
this.key = key;
this.to = to;
}
}
/**
* n0<br>
* O(n)
*
* @param n
*/
public MinCostFlow(int n) {
this.n = n;
pos = new ArrayList<>();
g = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
g.add(new ArrayList<>());
}
}
/**
* fromtocapcost<br>
* O(1)
*
* @param from 0≦fromn
* @param to 0≦ton
* @param cap 0≦cap
* @param cost 10≦cost
* @return
*/
int addEdge(int from, int to, long cap, long cost) {
assert 0 <= from && from < n : "from=" + from;
assert 0 <= to && to < n : "to=" + to;
assert 0 <= cap : "cap=" + cap;
assert 0 <= cost : "cost=" + cost;
// System.out.println(from + "->" + to + " " + cap + " " + cost);
int m = pos.size();
pos.add(new int[] { from, g.get(from).size() });
g.get(from).add(new Edge2(to, g.get(to).size(), cap, cost));
g.get(to).add(new Edge2(from, g.get(from).size() - 1, 0, -cost));
return m;
}
/**
* i<br>
* O(1)
*
* @param i 0≦i
* @return
*/
Edge getEdge(int i) {
assert 0 <= i && i < pos.size() : "i=" + i + ", size=" + pos.size();
Edge2 e = g.get(pos.get(i)[0]).get(pos.get(i)[1]);
Edge2 re = g.get(e.to).get(e.rev);
return new Edge(pos.get(i)[0], e.to, e.cap + re.cap, re.cap, e.cost);
}
/**
* <br>
* O()
*
* @return
*/
List<Edge> edges() {
int m = pos.size();
List<Edge> result = new ArrayList<>(m);
for (int i = 0; i < m; i++) {
result.add(getEdge(i));
}
return result;
}
/**
* st<br>
* FmO(F(n + m) log n)
*
* @param s 0≦sn
* @param t 0≦tn
* @return [0][1]
*/
long[] flow(int s, int t) {
return flow(s, t, Long.MAX_VALUE);
}
/**
* stflowLimit<br>
* FmO(F(n + m) log n)
*
* @param s 0≦sn
* @param t 0≦tn
* @param flowLimit
* @return [0][1]
*/
long[] flow(int s, int t, long flowLimit) {
List<long[]> result = slope(s, t, flowLimit);
return result.get(result.size() - 1);
}
/**
* <pre>
*
* (0, 0)
* [0][1]調
* x[0]x
*
* ■
* stlong
* long
* 0≦nx≦8×10^181000
* </pre>
*
* @param s 0≦sns≠t
* @param t 0≦tns≠t
* @return [0][1]
*/
List<long[]> slope(int s, int t) {
return slope(s, t, Long.MAX_VALUE);
}
/**
* <pre>
*
* (0, 0)
* [0][1]調
* x[0]min(x, flowLimit)
*
* ■
* stlong
* long
* 0≦nx≦8×10^181000
* </pre>
*
* @param s 0≦sns≠t
* @param t 0≦tns≠t
* @param flowLimit
* @return [0][1]
*/
List<long[]> slope(int s, int t, long flowLimit) {
assert 0 <= s && s < n : "s=" + s;
assert 0 <= t && t < n : "t=" + t;
assert s != t : "s=t=" + s;
long[] dual = new long[n];
long[] dist = new long[n];
int[] pv = new int[n];
int[] pe = new int[n];
boolean[] vis = new boolean[n];
long flow = 0;
long cost = 0;
long prevCost = -1;
List<long[]> result = new ArrayList<>();
result.add(new long[] { flow, cost });
while (flow < flowLimit) {
if (!dualRef(s, t, dual, dist, pv, pe, vis)) {
break;
}
long c = flowLimit - flow;
for (int v = t; v != s; v = pv[v]) {
c = Math.min(c, g.get(pv[v]).get(pe[v]).cap);
}
for (int v = t; v != s; v = pv[v]) {
Edge2 e = g.get(pv[v]).get(pe[v]);
e.cap -= c;
g.get(v).get(e.rev).cap += c;
}
long d = -dual[s];
flow += c;
cost += c * d;
if (prevCost == d) {
result.remove(result.size() - 1);
}
result.add(new long[] { flow, cost });
prevCost = cost;
}
return result;
}
private boolean dualRef(int s, int t, long[] dual, long[] dist, int[] pv, int[] pe, boolean[] vis) {
Arrays.fill(dist, Long.MAX_VALUE);
Arrays.fill(pv, -1);
Arrays.fill(pe, -1);
Arrays.fill(vis, false);
PriorityQueue<Q> que = new PriorityQueue<>((o1, o2) -> Long.compare(o1.key, o2.key));
dist[s] = 0;
que.add(new Q(0, s));
while (!que.isEmpty()) {
int v = que.poll().to;
if (vis[v]) {
continue;
}
vis[v] = true;
if (v == t) {
break;
}
for (int i = 0; i < g.get(v).size(); i++) {
Edge2 e = g.get(v).get(i);
if (vis[e.to] || e.cap == 0) {
continue;
}
long cost = e.cost - dual[e.to] + dual[v];
if (dist[e.to] - dist[v] > cost) {
dist[e.to] = dist[v] + cost;
pv[e.to] = v;
pe[e.to] = i;
que.add(new Q(dist[e.to], e.to));
}
}
}
if (!vis[t]) {
return false;
}
for (int v = 0; v < n; v++) {
if (vis[v]) {
dual[v] -= dist[t] - dist[v];
}
}
return true;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0