結果
| 問題 |
No.2604 Initial Motion
|
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2024-02-10 20:54:44 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 727 ms / 3,000 ms |
| コード長 | 8,327 bytes |
| コンパイル時間 | 7,072 ms |
| コンパイル使用メモリ | 169,184 KB |
| 実行使用メモリ | 215,092 KB |
| 最終ジャッジ日時 | 2024-09-28 17:18:48 |
| 合計ジャッジ時間 | 19,992 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 39 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (84 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
static int NN => int.Parse(ReadLine());
static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
static long[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (k, n, m) = ((int)c[0], (int)c[1], c[2]);
var a = NList;
var b = NList;
var map = NArr(m);
var hnum = new int[n];
foreach (var ai in a) ++hnum[ai - 1];
var g = new MinCostFlowGraph(n + 2);
for (var i = 0; i < n; ++i)
{
g.AddEdge(n, i, hnum[i], 0);
g.AddEdge(i, n + 1, (int)b[i], 0);
}
foreach (var edge in map)
{
g.AddEdge((int)edge[0] - 1, (int)edge[1] - 1, k, edge[2]);
g.AddEdge((int)edge[1] - 1, (int)edge[0] - 1, k, edge[2]);
}
var ans = g.Flow(n, n + 1);
WriteLine(ans.cost);
}
class MinCostFlowGraph
{
public class Edge
{
public int To;
public int Rev;
public long Cap;
public long Flow;
public long Cost;
public Edge(int to, int rev, long cap, long cost)
{
To = to;
Rev = rev;
Cap = cap;
Cost = cost;
}
public Edge(int to, int rev, long cap, long flow, long cost)
{
To = to;
Rev = rev;
Cap = cap;
Flow = flow;
Cost = cost;
}
}
int size;
List<(int from, int to)> pos;
List<Edge>[] g;
public MinCostFlowGraph(int size)
{
this.size = size;
pos = new List<(int from, int cnt)>();
g = new List<Edge>[size];
for (var i = 0; i < g.Length; ++i) g[i] = new List<Edge>();
}
public int AddEdge(int from, int to, int cap, long cost)
{
var m = pos.Count;
pos.Add((from, g[from].Count));
g[from].Add(new Edge(to, g[to].Count, cap, cost));
g[to].Add(new Edge(from, g[from].Count - 1, 0, -cost));
return m;
}
public Edge GetEdge(int i)
{
var _e = g[pos[i].from][pos[i].to];
var _re = g[_e.To][_e.Rev];
return new Edge(pos[i].from, _e.To, _e.Cap + _re.Cap, _re.Cap, _e.Cost);
}
public List<Edge> GetEdges()
{
var res = new List<Edge>(pos.Count);
for (var i = 0; i < pos.Count; ++i)
{
res.Add(GetEdge(i));
}
return res;
}
public (long cap, long cost) Flow(int s, int t)
{
return Flow(s, t, long.MaxValue);
}
public (long cap, long cost) Flow(int s, int t, long limit)
{
return Slope(s, t, limit).Last();
}
public List<(long cap, long cost)> Slope(int s, int t)
{
return Slope(s, t, int.MaxValue);
}
public List<(long cap, long cost)> Slope(int s, int t, long limit)
{
var dual = new long[size];
var dist = new long[size];
var pv = new int[size];
var pe = new int[size];
var vis = new bool[size];
bool DualRef()
{
for (var i = 0; i < size; ++i)
{
dist[i] = long.MaxValue;
pv[i] = -1;
pe[i] = -1;
vis[i] = false;
}
var q = new PriorityQueue<Q>(size, false);
q.Enqueue(new Q(0, s));
dist[s] = 0;
while (q.Count > 0)
{
var cur = q.Dequeue();
var v = cur.To;
if (vis[v]) continue;
vis[v] = true;
if (v == t) break;
for (var i = 0; i < g[v].Count; ++i)
{
var e = g[v][i];
if (vis[e.To] || e.Cap == 0) continue;
var 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;
q.Enqueue(new Q(dist[e.To], e.To));
}
}
}
if (!vis[t]) return false;
for (var v = 0; v < size; ++v)
{
if (!vis[v]) continue;
dual[v] -= dist[t] - dist[v];
}
return true;
}
var flow = 0L;
var cost = 0L;
var prevCost = -1L;
var res = new List<(long cap, long cost)>();
res.Add((flow, cost));
while (flow < limit)
{
if (!DualRef()) break;
var c = limit - flow;
for (var v = t; v != s; v = pv[v])
{
c = Math.Min(c, g[pv[v]][pe[v]].Cap);
}
for (var v = t; v != s; v = pv[v])
{
var e = g[pv[v]][pe[v]];
e.Cap -= c;
g[v][e.Rev].Cap += c;
}
var d = -dual[s];
flow += c;
cost += c * d;
if (prevCost == d) res.RemoveAt(res.Count - 1);
res.Add((flow, cost));
prevCost = cost;
}
return res;
}
class Q : IComparable<Q>
{
public long Cost;
public int To;
public Q (long cost, int to)
{
Cost = cost;
To = to;
}
public int CompareTo(Q b)
{
return Cost.CompareTo(b.Cost);
}
}
}
class PriorityQueue<T> where T : IComparable<T>
{
public T[] List;
public int Count;
bool IsTopMax;
public PriorityQueue(int count, bool isTopMax)
{
IsTopMax = isTopMax;
List = new T[Math.Max(128, count)];
}
public void Enqueue(T value)
{
if (Count == List.Length)
{
var newlist = new T[List.Length * 2];
for (var i = 0; i < List.Length; ++i) newlist[i] = List[i];
List = newlist;
}
var pos = Count;
List[pos] = value;
++Count;
while (pos > 0)
{
var parent = (pos - 1) / 2;
if (Calc(List[parent], List[pos], true)) break;
Swap(parent, pos);
pos = parent;
}
}
public T Dequeue()
{
--Count;
Swap(0, Count);
var pos = 0;
while (true)
{
var child = pos * 2 + 1;
if (child >= Count) break;
if (child + 1 < Count && Calc(List[child + 1], List[child], false)) ++child;
if (Calc(List[pos], List[child], true)) break;
Swap(pos, child);
pos = child;
}
return List[Count];
}
bool Calc(T a, T b, bool equalVal)
{
var ret = a.CompareTo(b);
if (ret == 0 && equalVal) return true;
return IsTopMax ? ret > 0 : ret < 0;
}
void Swap(int a, int b)
{
var tmp = List[a];
List[a] = List[b];
List[b] = tmp;
}
}
}