SRM642D1Med TaroCutting
こういうのは好き
問題概要(原文)
$N$ 本の木があって，高さは $H_i$ で毎日 $A_i$ 伸びる．また $M$ 個の機械があって整数 $B_j$ を持つ．その日の終わりに $i$ 番の木の高さが $B_j$ より大きいなら木の高さを $B_j$ にするという操作ができる．ただし， $1$ つの機械あたり $1$ 本の木しか割り当てられない． $T$ 日後の木の高さの総和を最小化せよ．
考察
- 木の高さを減らすならなるべく後の方で減らしたい．
- 木の高さを何度も減らす意味はない
以上を考えると $i$ 番目の木を $j$ 日目に $k$ 番の機械にかけるかどうかという割当問題を解けばよい．
単純にグラフを作ると $N + M \times T$ 個の頂点と $N \times M \times T$ 本ぐらいの辺ができてやばいが，木-切る日，切る日-機械の $2$ つの二部グラフに分けてマッチングをすることにすれば大丈夫．
- $i$ 番目の木を $j$ 日目に切ると， $A_i \times (T-j)$ だけコストがかかる (容量 1)
- 木を切らないときに $H_i + A_i \times T$のコストがかかる (容量 $1$)
- $j$ 日目に $k$ 番の機械で切ったことにすると， $B_k$ のコストがかかる (容量 $1$)
という辺を適切に貼ればよい．
計算量は $O(N(N \times T + T \times M)log(N+T+M))$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class TaroCutting
{
public int getNumber(int[] height, int[] add, int[] device, int time)
{
var n = height.Length;
var m = time;
var p = device.Length;
var G = Enumerate(n + m + p + +2, x => new List<Edge<int, int>>());
var s = n + m + p;
var t = n + m + p + 1;
for (int i = 0; i < n; i++)
{
G.AddDirectedEdge(s, i, 1, 0);
G.AddDirectedEdge(i, t, 1, height[i] + add[i] * time);
for (int rem = 0; rem < m; rem++)
{
G.AddDirectedEdge(i, n + rem, 1, add[i] * rem);
}
}
for (int rem = 0; rem < m; rem++)
{
for (int k = 0; k < p; k++)
{
G.AddDirectedEdge(n + rem, n + m + k, 1, device[k]);
}
}
for (int k = 0; k < p; k++)
{
G.AddDirectedEdge(n + m + k, t, 200, 0);
}
var min = Flow.PrimalDual(G, s, t, n);
Debug.WriteLine(min);
return min.x;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
static public class EnumerableEX
{
static public string AsString(this IEnumerable<char> e) { return new string(e.ToArray()); }
static public string AsJoinedString<T>(this IEnumerable<T> e, string s = " ") { return string.Join(s, e); }
}
#region CostEdge
static public class Edge
{
static public Edge<C, V> Create<C, V>(int t, int r, C _cap, V _cost) { return new Edge<C, V>(t, r, _cap, _cost); }
}
public class Edge<C, V>
{
public int to, rev;
public C cap;
public V cost;
public Edge(int t, int r, C _cap, V _cost) { to = t; rev = r; cap = _cap; cost = _cost; }
public override string ToString() { return string.Format("{0}: Capacity {1}, Cost{2}", to, cap, cost); }
}
#endregion
#region AddCostEdge
static public partial class Flow
{
static public void AddDirectedEdge(this List<Edge<int, int>>[] G, int from, int to, int cap, int cost)
{
G[from].Add(Edge.Create(to, G[to].Count, cap, cost));
G[to].Add(Edge.Create(from, G[from].Count - 1, 0, -cost));
}
static public void AddDirectedEdge(this List<Edge<int, double>>[] G, int from, int to, int cap, double cost)
{
G[from].Add(Edge.Create(to, G[to].Count, cap, cost));
G[to].Add(Edge.Create(from, G[from].Count - 1, 0, -cost));
}
}
#endregion
#region Integer MinCostFlow
static public partial class Flow
{
/// <summary>
/// 最小費用流をprimal-dual法でやる
/// </summary>
/// <param name="G">グラフ</param>
/// <param name="s">始点</param>
/// <param name="t">終点</param>
/// <param name="f">流す最大流量</param>
/// <param name="INF">適当な最大値</param>
/// <returns></returns>
static public Pair<int, int> PrimalDual(List<Edge<int, int>>[] G, int s, int t, int f, int INF = 1 << 20)
{
var n = G.Length;
var dist = new int[n];
var prev = new int[n];
var prevEdge = new int[n];
var total = new Pair<int, int>(0, 0);
var potential = new int[n];
while (f > 0)
{
for (int i = 0; i < n; i++)
dist[i] = INF;
//shortest path
if (total.y == 0)
{
var q = new Queue<int>();
q.Enqueue(s); dist[s] = 0;
var inQ = new bool[n];
while (q.Any())
{
var p = q.Dequeue();
inQ[p] = false;
for (int i = 0; i < G[p].Count; i++)
{
var e = G[p][i];
var j = e.to;
var d = dist[p] + e.cost;
if (e.cap > 0 && d < dist[j])
{
if (!inQ[j])
{
inQ[j] = true;
q.Enqueue(j);
}
dist[j] = d; prev[j] = p; prevEdge[j] = i;
}
}
}
}
else
{
var vis = new bool[n];
var pq = new PriorityQueue<Pair<int, int>>();
pq.Enqueue(new Pair<int, int>(0, s));
dist[s] = 0;
while (pq.Any())
{
var p = pq.Dequeue().y;
if (vis[p]) continue;
vis[p] = true;
for (int i = 0; i < G[p].Count; i++)
{
var e = G[p][i];
if (e.cap <= 0) continue;
var j = e.to;
var d = dist[p] + e.cost + potential[p] - potential[j];
if (dist[j] > d)
{
dist[j] = d; prev[j] = p; prevEdge[j] = i;
pq.Enqueue(new Pair<int, int>(d, j));
}
}
}
}
//update
{
if (dist[t] == INF) break;
for (int i = 0; i < n; i++)
potential[i] += dist[i];
var d = f; var distt = 0;
for (var v = t; v != s;)
{
var u = prev[v]; var e = G[u][prevEdge[v]];
d = Math.Min(d, e.cap); distt += e.cost; v = u;
}
f -= d; total.x += d * distt; total.y += d;
for (var v = t; v != s; v = prev[v])
{
var e = G[prev[v]][prevEdge[v]];
e.cap -= d; G[e.to][e.rev].cap += d;
}
}
}
return total;
}
}
#endregion
#region Compair
static public class Pair
{
static public Pair<FT, ST> Create<FT, ST>(FT f, ST s)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return new Pair<FT, ST>(f, s); }
static public Pair<FT, ST> Min<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return (p.CompareTo(q) <= 0) ? p : q; }
static public Pair<FT, ST> Max<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return (p.CompareTo(q) >= 0) ? p : q; }
}
public struct Pair<FT, ST>: IComparable<Pair<FT, ST>>
where FT : IComparable<FT>
where ST : IComparable<ST>
{
public FT x;
public ST y;
public Pair(FT f, ST s) : this() { x = f; y = s; }
public int CompareTo(Pair<FT, ST> other)
{
var cmp = x.CompareTo(other.x);
return cmp != 0 ? cmp : y.CompareTo(other.y);
}
public override string ToString() { return string.Format("{0} {1}", x, y); }
}
#endregion
#region PriorityQueue and PairingHeap
public class PriorityQueue<T>
{
PairingHeap<T> top;
Comparison<T> compare;
int size;
public int Count { get { return size; } }
public PriorityQueue() : this(Comparer<T>.Default) { }
public PriorityQueue(Comparison<T> comparison) { compare = comparison; }
public PriorityQueue(IComparer<T> comparer) { compare = comparer.Compare; }
public void Enqueue(T item)
{
var heap = new PairingHeap<T>(item);
top = PairingHeap<T>.Merge(top, heap, compare);
size++;
}
public T Dequeue()
{
var ret = top.Key;
size--;
top = PairingHeap<T>.Pop(top, compare);
return ret;
}
public bool Any() { return size > 0; }
public T Peek() { return top.Key; }
}
#region PairingHeap
public class PairingHeap<T>
{
public PairingHeap(T k) { key = k; }
private readonly T key;
public T Key { get { return key; } }
private PairingHeap<T> head;
private PairingHeap<T> next;
static public PairingHeap<T> Pop(PairingHeap<T> s, Comparison<T> compare)
{
return MergeLst(s.head, compare);
}
static public PairingHeap<T> Merge(PairingHeap<T> l, PairingHeap<T> r, Comparison<T> compare)
{
if (l == null || r == null) return l == null ? r : l;
if (compare(l.key, r.key) > 0) Swap(ref l, ref r);
r.next = l.head;
l.head = r;
return l;
}
static public PairingHeap<T> MergeLst(PairingHeap<T> s, Comparison<T> compare)
{
var n = new PairingHeap<T>(default(T));
while (s != null)
{
PairingHeap<T> a = s, b = null;
s = s.next; a.next = null;
if (s != null) { b = s; s = s.next; b.next = null; }
a = Merge(a, b, compare); a.next = n.next;
n.next = a;
}
while (n.next != null)
{
var j = n.next;
n.next = n.next.next;
s = Merge(j, s, compare);
}
return s;
}
static void Swap(ref PairingHeap<T> l, ref PairingHeap<T> r) { var t = l; l = r; r = t; }
}
#endregion
#endregion
コメント
- DPっぽいけど状態が複雑なときはだいたいフロー
