結果
問題 | No.2604 Initial Motion |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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;}}/*** n頂点0辺のグラフを作る。<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<>());}}/*** fromからtoへ最大容量cap、コストcostの辺を追加する。<br>* ならしO(1)** @param from 有向辺の始点(0≦from<n)* @param to 有向辺の終点(0≦to<n)* @param cap 最大容量(0≦cap)* @param cost 流量1当たりのコスト(0≦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;}/*** 最小費用流。頂点sからtへ流せるだけ流す。<br>* Fを流量、mを辺数として、O(F(n + m) log n)** @param s 始点(0≦s<n)* @param t 終点(0≦t<n)* @return [0]:流せた量、[1]:その時のコスト*/long[] flow(int s, int t) {return flow(s, t, Long.MAX_VALUE);}/*** 最小費用流。頂点sからtへflowLimitに達するまで流せるだけ流す。<br>* Fを流量、mを辺数として、O(F(n + m) log n)** @param s 始点(0≦s<n)* @param t 終点(0≦t<n)* @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** ■制約* sからtへ流したフローの流量がlongに収まる。* 流したフローのコストの総和がlongに収まる。* 0≦nx≦8×10^18+1000* </pre>** @param s 始点(0≦s<n、s≠t)* @param t 終点(0≦t<n、s≠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)** ■制約* sからtへ流したフローの流量がlongに収まる。* 流したフローのコストの総和がlongに収まる。* 0≦nx≦8×10^18+1000* </pre>** @param s 始点(0≦s<n、s≠t)* @param t 終点(0≦t<n、s≠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;}}