EvbCFfp1XB

problem and my answer.



Approach 貪欲法 + 焼きなまし法 を使いました。

  • 貪欲法
    • オーダーを並べ替える。
      • 納期が早い、数量が多い、最早開始日時が早い、(納期 - 最早開始日時) が短いオーダーを優先する。
    • 最早開始日時 から使える枠(リソースと時間のペア)を探す。
      • 同じパンの枠がある場合はその枠を優先する。
      • 同じパンの枠に追加するとき、追加した後のキャパシティの小さい枠を優先する。
      • 枠が空のとき、キャパシティの大きい枠を優先する。
  • 焼きなまし法
    • 近傍1 : オーダーを納期に間に合うように移動する。
      • 別のパンがあって、無効な移動なことがあります。
    • 近傍2 : オーダーを同じパンの別の枠に移動する。
      • 納期に間に合わなくても気にしない。
    • 近傍3 : オーダーを同じパンの別の枠のオーダーと交換する。
    • 近傍4 : ある枠の全てのオーダーを、別の枠の全てのオーダーと交換する。
      • 別の枠は、リソースはランダムで、時間は前後 ± 1。
      • 枠のオーダーの最早開始日時の最大値と数量の和を持つと、有効な交換かどうかO(1)で判定できる。
      • 時間は前後 ± 1なので、スコアの差を、事前に計算できます。
    • 近傍5 : ある枠の全てのオーダーを、同じパンの別の枠に移動する。
  • 高速化
    • 構造体のメンバーを vector にコピーして、vector を使いました。



problem https://github.com/kosakkun/Typical-MM/tree/master/GraphColoring

Approach
  • 貪欲法で有効な彩色を見つける。
  • その状態から色を1つ減らして、焼きなまし法やタブーサーチで有効な彩色を見つける。これを繰り返す。

  • 診断人さんが使ってたタブーサーチが強かった。

  • 貪欲法
    • 次数の大きい頂点から彩色する。
  • タブーサーチ
    • 有効な彩色が見つかったら、ある色を無色にして、色を1つ減らす。
    • 無色の頂点から1つランダムに選ぶ。
    • その頂点に隣接する頂点の色ごとに次数の和を求める。
    • タブーリストにない色で、最も次数の和が小さい色で彩色する。
      • 全ての色がタブーリストに載ってたら、タブーリストを無視して、最も次数の和が小さい色で彩色する。
    • 隣接する頂点が同じ色なら、その頂点を無色にする。
    • 彩色した色と頂点のペアをタブーリストに加える。





source code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

public class GraphColoring {
private static final int NUM_TABU_LIST = 75;
private static final int NG = ((1 << 16) - 1);

private int numVertexes;
private int numEdges;
private IntSet[] nextVertexSet;
private int usedColors;
private int[] vertexToColor;

private int bestUsedColors;
private int[] bestVertexToColor;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private IntSet uncoloredVertexSet;

private int[] tabuList = new int[NUM_TABU_LIST];
private int indexOfTabuList = 0;
private boolean[][] isTabu;

private int[] colorToSumDegree = new int[256];

private int[] run(int N, int M, int[] a, int[] b) {
init(N, M, a, b);
solve();
return vertexToColor;
}

private void init(int N, int M, int[] a, int[] b) {
this.numVertexes = N;
this.numEdges = M;

Utils.debug("numVertexes", numVertexes, "numEdges", numEdges);

nextVertexSet = new IntSet[numVertexes];
for (int i = 0; i < numVertexes; i++) {
nextVertexSet[i] = new IntSet(numVertexes);
}
for (int i = 0; i < numEdges; i++) {
nextVertexSet[a[i]].add(b[i]);
nextVertexSet[b[i]].add(a[i]);
}

vertexToColor = new int[numVertexes];
bestVertexToColor = new int[numVertexes];
for (int i = 0; i < numVertexes; i++) {
vertexToColor[i] = -1;
bestVertexToColor[i] = -1;
}

bestUsedColors = (int) 1e9;

uncoloredVertexSet = new IntSet(numVertexes);

isTabu = new boolean[numVertexes][256];
}

private void solve() {
greedy();
tabuSearch();
}

private void tabuSearch() {
for (int numIterations = 0;; numIterations++) {
if ((numIterations & ((1 << 10) - 1)) == 0) {
if (watch.getSecond() >= 9.5) {
loadBest();
Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
break;
}
}
while (uncoloredVertexSet.size() == 0) {
saveBest();
Utils.debug("numIterations", numIterations, "usedColors", usedColors, "time", watch.getSecondString());
usedColors--;
for (int v = 0; v < numVertexes; v++) {
if (vertexToColor[v] == usedColors) {
uncoloredVertexSet.add(v);
}
}
initTabuList();
}

int vertex = uncoloredVertexSet.get((int) (uncoloredVertexSet.size() * rng.nextDouble()));

for (int color = 0; color < usedColors; color++) {
colorToSumDegree[color] = 0;
}
for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
colorToSumDegree[vertexToColor[nextVertex]] += nextVertexSet[nextVertex].size();
}

int bestSumDegree = (int) 1e9;
int bestColor = -1;
for (int color = 0; color < usedColors; color++) {
if (isTabu[vertex][color]) {
continue;
}

if (colorToSumDegree[color] < bestSumDegree) {
bestSumDegree = colorToSumDegree[color];
bestColor = color;
}
}

if (bestColor == -1) {
for (int color = 0; color < usedColors; color++) {
if (colorToSumDegree[color] < bestSumDegree) {
bestSumDegree = colorToSumDegree[color];
bestColor = color;
}
}
}

vertexToColor[vertex] = bestColor;
uncoloredVertexSet.removeValue(vertex);

for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
if (vertexToColor[nextVertex] == bestColor) {
vertexToColor[nextVertex] = usedColors;
uncoloredVertexSet.add(nextVertex);
}
}

addTabu(vertex, bestColor);

}
}

private void addTabu(int vertex, int color) {
int tabu = tabuList[indexOfTabuList];
if (vertex(tabu) != NG) {
isTabu[vertex(tabu)][color(tabu)] = false;
}

tabuList[indexOfTabuList] = encode(vertex, color);
isTabu[vertex][color] = true;

indexOfTabuList++;
if (indexOfTabuList >= NUM_TABU_LIST) {
indexOfTabuList = 0;
}
}

private void initTabuList() {
for (int i = 0; i < NUM_TABU_LIST; ++i) {
int tabu = tabuList[i];
if (vertex(tabu) != NG) {
isTabu[vertex(tabu)][color(tabu)] = false;
}
tabuList[i] = encode(NG, NG);
}
}

private void greedy() {
ArrayList<Pair<Integer, Integer>> degreeAndVertexPairs = new ArrayList<>();
for (int vertex = 0; vertex < numVertexes; vertex++) {
degreeAndVertexPairs.add(new Pair<Integer, Integer>(-nextVertexSet[vertex].size(), vertex));
}
Collections.sort(degreeAndVertexPairs);
for (int i = 0; i < degreeAndVertexPairs.size(); i++) {
int vertex = degreeAndVertexPairs.get(i).second.intValue();
for (int color = 0; color < 256; color++) {
if (canUse(vertex, color)) {
vertexToColor[vertex] = color;
break;
}
}
}
usedColors = calculateUsedColors();
saveBest();
Utils.debug("greedy", "usedColors", usedColors, "time", watch.getSecondString());
}

private int calculateUsedColors() {
HashSet<Integer> set = new HashSet<>();
for (int vertex = 0; vertex < numVertexes; vertex++) {
set.add(vertexToColor[vertex]);
}
return set.size();
}

private boolean canUse(int vertex, int color) {
for (int i = 0; i < nextVertexSet[vertex].size(); i++) {
int nextVertex = nextVertexSet[vertex].get(i);
if (vertexToColor[nextVertex] == color) {
return false;
}
}
return true;
}

private void saveBest() {
if (usedColors < bestUsedColors) {
bestUsedColors = usedColors;
for (int i = 0; i < numVertexes; i++) {
bestVertexToColor[i] = vertexToColor[i];
}
}
}

private void loadBest() {
usedColors = bestUsedColors;
for (int i = 0; i < numVertexes; i++) {
vertexToColor[i] = bestVertexToColor[i];
}
}

private static final int encode(int vertex, int color) {
return (vertex << 16) | color;
}

private static final int vertex(int v) {
return v >>> 16;
}

private static final int color(int v) {
return v & ((1 << 16) - 1);
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

String line = br.readLine();
String[] split = line.split(" ");
int N = Integer.parseInt(split[0]);
int M = Integer.parseInt(split[1]);
int[] a = new int[M];
int[] b = new int[M];
for (int i = 0; i < M; i++) {
line = br.readLine();
split = line.split(" ");
a[i] = Integer.parseInt(split[0]);
b[i] = Integer.parseInt(split[1]);
}

GraphColoring gc = new GraphColoring();
int[] ret = gc.run(N, M, a, b);
for (int i = 0; i < N; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (IOException e) {
e.printStackTrace();
}
}

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() <= 0;
}

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}




Approach 複数のアプローチを試して一番スコアの良いものを返した。

  • トラックを使わずに割当問題を解く。
    • 最小費用流を使った。
    • 450000点くらい。
  • 倉庫のアイテムをトラックで顧客の近くに移動して、割当問題を解く。
    • 600000点くらい。
    • 次のアプローチを使うと、このアプローチはほとんど出番がないので最終的に使わなかった。
  • 全てのアイテムを一箇所に集めて、配る。
    • 集めるのも配るのもどちらも最小シュタイナー木問題。
    • 集めるとき、最小全域木にフェルマー点を加えて、もう一度最小全域木を作った。
      • フェルマー点を求めるとき、トラックのコストはマンハッタン距離なのに、ユークリッド距離を使って良かったんだろうか?
    • 配るとき、トラックの行き先の位置と個数を焼き鈍した。
      • 近傍は、点の追加、削除、移動。
      • 時間を10倍にしても2%しか改善しない。
    • 850000点くらい。
      • 追記 : 9%TLEしてたので、832897.36 / 0.91 = 915271.82点。

残り10%5%ほどを改善するアプローチ
  • 全てのアイテムを一箇所に集める必要はない。
    • 集めるとき、配るとき両方のコストが減る。
    • 追記 : このアプローチは、問題を集める問題と配る問題に分けたのをさらに分ける感じだが、方向が逆で、集めながら配る問題にして1つの問題にするほうが改善するらしい。

感想

  • やることが色々あって楽しかった。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class TrucksAndCouriers {
private int truckFixed;
private int truckVariable;
private int[] warehouseX;
private int[] warehouseY;
private int[] warehouseItem;
private int[] warehouseQuantity;
private int[] customerX;
private int[] customerY;
private int[] customerItem;
private int numWarehouses;
private int numCustomers;
private ArrayList<String> solution;
private int score;
private int bestScore;
private ArrayList<Truck> bestTrucks;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();
private ArrayList<Customer> customers2;
private ArrayList<Truck> trucks;
private HashMap<Integer, HashMap<Integer, Integer>> warePointToItemToQuantity;
private ArrayList<Integer> warePoints;
private int sumTruckCost;
private HashMap<Integer, ArrayList<Customer>> warePointToCustomers;
private HashMap<Integer, ArrayList<Customer>> warePointToCustomers0;
private int numOriginalWares;

public String[] planShipping(int truckFixed, int truckVariable, int[] warehouseX, int[] warehouseY, int[] warehouseItem, int[] warehouseQuantity, int[] customerX, int[] customerY, int[] customerItem) {
init(truckFixed, truckVariable, warehouseX, warehouseY, warehouseItem, warehouseQuantity, customerX, customerY, customerItem);
solve();
Utils.debug("score", score, "time", watch.getSecondString());
String[] solution = makeSolution();
Utils.debug("score", score, "time", watch.getSecondString());
return solution;
}

private String[] makeSolution() {
score = 0;
for (Truck truck : trucks) {
addTruck2(truck);
}

ArrayList<Pair<Integer, Integer>> warePointAndItemPairs = new ArrayList<>();
for (Integer warePoint : warePoints) {
for (Integer item : warePointToItemToQuantity.get(warePoint).keySet()) {
warePointAndItemPairs.add(new Pair<Integer, Integer>(warePoint, item));
}
}

int[][] costs = new int[customers2.size()][warePointAndItemPairs.size()];

for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int item = customer.item;
for (int wi = 0; wi < warePointAndItemPairs.size(); wi++) {
Integer warePoint = warePointAndItemPairs.get(wi).first;
Integer item2 = warePointAndItemPairs.get(wi).second;
if (item2 != item) {
costs[ci][wi] = -1;
continue;
}
if (warePointToItemToQuantity.get(warePoint).get(item2) <= 0) {
costs[ci][wi] = -1;
continue;
}
costs[ci][wi] = distance(customer, warePoint);
}
}

int R = costs.length;
int C = costs[0].length;

MinCostFlow mcf = new MinCostFlow(R + C + 2);

int s = R + C;
int t = s + 1;

for (int r = 0; r < R; r++) {
mcf.addEdge(s, r, 1, 0);
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (costs[r][c] < 0) {
continue;
}
mcf.addEdge(r, R + c, 1, costs[r][c]);
}
}
for (int c = 0; c < C; c++) {
Pair<Integer, Integer> pair = warePointAndItemPairs.get(c);
Integer warePoint = pair.first;
Integer item = pair.second;
mcf.addEdge(R + c, t, quantity(y(warePoint), x(warePoint), item), 0);
}

int minCost = mcf.run(s, t, R);

int[] rToC = new int[R];
Arrays.fill(rToC, -1);
for (int r = 0; r < R; r++) {
ArrayList<Edge> edges = mcf.G.get(r);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int c = e.to - R;
rToC[r] = c;
break;
}
}
for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int item = customer.item;
int ware = rToC[ci];
Pair<Integer, Integer> pair = warePointAndItemPairs.get(ware);
addCourier(x(pair.first), y(pair.first), customer.x, customer.y, item);
}
return (String[]) solution.toArray(new String[solution.size()]);
}

private void addTruck2(Truck truck) {
if (truck.items.size() == 0) {
return;
}
String s = "T," + truck.startX + "," + truck.startY + "," + truck.destX + "," + truck.destY;
for (Integer item : truck.items) {
s += "," + item;
}
solution.add(s);
score += truckFixed + truckVariable * (Math.abs(truck.startX - truck.destX) + Math.abs(truck.startY - truck.destY));
}

private void init(int truckFixed, int truckVariable, int[] warehouseX, int[] warehouseY, int[] warehouseItem, int[] warehouseQuantity, int[] customerX, int[] customerY, int[] customerItem) {
this.truckFixed = truckFixed;
this.truckVariable = truckVariable;
this.numWarehouses = warehouseX.length;
this.warehouseX = warehouseX;
this.warehouseY = warehouseY;
this.warehouseItem = warehouseItem;
this.warehouseQuantity = warehouseQuantity;
this.numCustomers = customerX.length;
this.customerX = customerX;
this.customerY = customerY;
this.customerItem = customerItem;
warePoints = new ArrayList<>();
warePointToItemToQuantity = new HashMap<>();
for (int i = 0; i < numWarehouses; i++) {
int z = z(this.warehouseX[i], this.warehouseY[i]);
if (warePointToItemToQuantity.get(z) == null) {
warePointToItemToQuantity.put(z, new HashMap<>());
warePoints.add(z);
}
Integer quantity = warePointToItemToQuantity.get(z).get(this.warehouseItem[i]);
warePointToItemToQuantity.get(z).put(this.warehouseItem[i], (quantity == null ? 0 : quantity.intValue()) + this.warehouseQuantity[i]);
}
solution = new ArrayList<>();

score = 0;
bestScore = (int) 1e9;
customers2 = new ArrayList<>();
for (int i = 0; i < numCustomers; i++) {
Customer customer = new Customer();
customer.x = this.customerX[i];
customer.y = this.customerY[i];
customer.item = this.customerItem[i];
customers2.add(customer);
}

trucks = new ArrayList<>();
Utils.debug("truckFixed", truckFixed, "truckVariable", truckVariable, "numWarehouses", numWarehouses, "numCustomers", numCustomers);
ArrayList<Pair<Integer, Integer>> warePointAndItemPairs = new ArrayList<>();
for (Integer warePoint : warePoints) {
for (Integer item : warePointToItemToQuantity.get(warePoint).keySet()) {
warePointAndItemPairs.add(new Pair<Integer, Integer>(warePoint, item));
}
}

int[][] costs = new int[customers2.size()][warePointAndItemPairs.size()];

for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int item = customer.item;
for (int wi = 0; wi < warePointAndItemPairs.size(); wi++) {
Integer warePoint = warePointAndItemPairs.get(wi).first;
Integer item2 = warePointAndItemPairs.get(wi).second;
if (item2 != item) {
costs[ci][wi] = -1;
continue;
}
if (warePointToItemToQuantity.get(warePoint).get(item2) <= 0) {
costs[ci][wi] = -1;
continue;
}
costs[ci][wi] = distance(customer, warePoint);
}
}

int R = costs.length;
int C = costs[0].length;

MinCostFlow mcf = new MinCostFlow(R + C + 2);

int s = R + C;
int t = s + 1;

for (int r = 0; r < R; r++) {
mcf.addEdge(s, r, 1, 0);
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (costs[r][c] < 0) {
continue;
}
mcf.addEdge(r, R + c, 1, costs[r][c]);
}
}
for (int c = 0; c < C; c++) {
Pair<Integer, Integer> pair = warePointAndItemPairs.get(c);
Integer warePoint = pair.first;
Integer item = pair.second;
mcf.addEdge(R + c, t, quantity(y(warePoint), x(warePoint), item), 0);
}

int minCost = mcf.run(s, t, R);
score = minCost;
bestScore = score;
bestTrucks = new ArrayList<>();

int[] rToC = new int[R];
Arrays.fill(rToC, -1);
for (int r = 0; r < R; r++) {
ArrayList<Edge> edges = mcf.G.get(r);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int c = e.to - R;
rToC[r] = c;
break;
}
}

warePointToCustomers = new HashMap<>();
for (int r = 0; r < rToC.length; r++) {
int c = rToC[r];
Integer warePoint = warePointAndItemPairs.get(c).first;
if (warePointToCustomers.get(warePoint) == null) {
warePointToCustomers.put(warePoint, new ArrayList<>());
}
warePointToCustomers.get(warePoint).add(customers2.get(r));
}
warePointToCustomers0 = new HashMap<>();
for (int r = 0; r < rToC.length; r++) {
int c = rToC[r];
Integer warePoint = warePointAndItemPairs.get(c).first;
if (warePointToCustomers0.get(warePoint) == null) {
warePointToCustomers0.put(warePoint, new ArrayList<>());
}
warePointToCustomers0.get(warePoint).add(customers2.get(r));
}

numOriginalWares = warePoints.size();
Utils.debug("score", score, "time", watch.getSecondString());
}

private int distance(Customer customer, Integer warePoint) {
return distance(x(warePoint), y(warePoint), customer.x, customer.y);
}

private static final int distance(int x, int y, int x2, int y2) {
return Math.abs(x - x2) + Math.abs(y - y2);
}

private static final int z(int x, int y) {
return (y << 16) | (x);
}

private static final int x(int z) {
return z & ((1 << 16) - 1);
}

private static final int y(int z) {
return z >>> 16;
}

private void solve() {
moveToCenterMST();
SA2();
Utils.debug("points.size()", points.size());
score += score2;
makeTrucks();

saveBest();
loadBest();
}

private void makeTrucks() {
MinimumSpanningTree mst = new MinimumSpanningTree(points.size());
for (int i = 0; i < points.size(); i++) {
Point pi = points.get(i);
for (int j = i + 1; j < points.size(); j++) {
Point pj = points.get(j);
mst.addEdge(i, j, truckFixed + truckVariable * distance(pi.x, pi.y, pj.x, pj.y));
}
}

Utils.debug("mst.kruskal()", mst.kruskal());

ArrayList<Integer>[] pointToCustomers = new ArrayList[points.size()];
for (int i = 0; i < pointToCustomers.length; i++) {
pointToCustomers[i] = new ArrayList<>();
}
int[] customerToPoint = new int[customers2.size()];
for (int ci = 0; ci < customers2.size(); ci++) {
Customer customer = customers2.get(ci);
int min = (int) 1e9;
int mini = -1;
for (int pi = 0; pi < points.size(); pi++) {
int distance = distance(customer.x, customer.y, points.get(pi).x, points.get(pi).y);
if (distance < min) {
min = distance;
mini = pi;
}
}
customerToPoint[ci] = mini;
pointToCustomers[mini].add(ci);
}

indexToCustomerIndexes = new ArrayList[points.size()];
for (int i = 0; i < indexToCustomerIndexes.length; i++) {
indexToCustomerIndexes[i] = new ArrayList<>();
}
dfs(0, mst, new boolean[points.size()], customerToPoint, pointToCustomers);
Utils.debug("0 size", indexToCustomerIndexes[0].size(), customers2.size());

bfs(0, mst);
}

private void bfs(int index0, MinimumSpanningTree mst) {
LinkedList<Integer> queue = new LinkedList<>();
boolean[] used = new boolean[points.size()];
{
queue.add(index0);
used[index0] = true;
}
for (; !queue.isEmpty();) {
int index = queue.pollFirst().intValue();
for (int i = 0; i < mst.G.get(index).size(); i++) {
Edge3 edge3 = mst.G.get(index).get(i);

if (used[edge3.to]) {
continue;
}
used[edge3.to] = true;
queue.add(edge3.to);

Point point = points.get(index);
Point point2 = points.get(edge3.to);
ArrayList<Integer> items = new ArrayList<>();
for (Integer ci : indexToCustomerIndexes[edge3.to]) {
items.add(customers2.get(ci.intValue()).item);
}
Truck truck = new Truck(point.x, point.y, point2.x, point2.y, items);
addTruck(truck);

}
}
}

private ArrayList<Integer>[] indexToCustomerIndexes;

private void dfs(int index, MinimumSpanningTree mst, boolean[] used, int[] customerToPoint, ArrayList<Integer>[] pointToCustomers) {
used[index] = true;

for (int i = 0; i < mst.G.get(index).size(); i++) {
Edge3 edge3 = mst.G.get(index).get(i);
if (used[edge3.to]) {
continue;
}
dfs(edge3.to, mst, used, customerToPoint, pointToCustomers);
indexToCustomerIndexes[index].addAll(indexToCustomerIndexes[edge3.to]);
}
indexToCustomerIndexes[index].addAll(pointToCustomers[index]);
}

private Point FermatPoint(Point a, Point b, Point c) {
double da = dist(b, c);
double db = dist(a, c);
double dc = dist(a, b);

if (da * da >= db * db + dc * dc + db * dc)
return null;
if (db * db >= dc * dc + da * da + dc * da)
return null;
if (dc * dc >= da * da + db * db + da * db)
return null;

double A = Math.acos((db * db + dc * dc - da * da) / (2 * db * dc));
double B = Math.acos((dc * dc + da * da - db * db) / (2 * dc * da));
double C = Math.acos((da * da + db * db - dc * dc) / (2 * da * db));

double ra = csc(A + Math.PI / 3);
double rb = csc(B + Math.PI / 3);
double rc = csc(C + Math.PI / 3);

double wa = da * ra;
double wb = db * rb;
double wc = dc * rc;

double wall = wa + wb + wc;

double x = a.x * wa + b.x * wb + c.x * wc;
double y = a.y * wa + b.y * wb + c.y * wc;
return new Point((int) (0.5 + x / wall), (int) (0.5 + y / wall));
}

private double csc(double x) {
return 1.0 / Math.sin(x);
}

private double dist(Point a, Point b) {
int dx = a.x - b.x;
int dy = a.y - b.y;
return Math.sqrt(dx * dx + dy * dy);
}

private void moveToCenterMST() {
score = 0;

MinimumSpanningTree mst = new MinimumSpanningTree(warePoints.size());
for (int from = 0; from < warePoints.size(); from++) {
for (int to = from + 1; to < warePoints.size(); to++) {
mst.addEdge(from, to, truckFixed + truckVariable * distance(x(warePoints.get(from)), y(warePoints.get(from)), x(warePoints.get(to)), y(warePoints.get(to))));
}
}
int cost = mst.kruskal();
Utils.debug("MST cost", cost);

for (int from = 0, size = warePoints.size(); from < size; from++) {
Integer za = warePoints.get(from);
Point a = new Point(x(za), y(za));
ArrayList<Edge3> edges = mst.G.get(from);
for (int i = 0; i < edges.size(); i++) {
Edge3 edge = edges.get(i);
Integer zb = warePoints.get(edge.to);
Point b = new Point(x(zb), y(zb));
for (int j = i + 1; j < edges.size(); j++) {
Edge3 edge2 = edges.get(j);
Integer zc = warePoints.get(edge2.to);
Point c = new Point(x(zc), y(zc));
Point fermat = FermatPoint(a, b, c);
if (fermat == null) {
continue;
}

if (truckCost(fermat, a) + truckCost(fermat, b) + truckCost(fermat, c) < truckCost(a, b) + truckCost(a, c)) {
warePoints.add(z(fermat.x, fermat.y));
}
}
}
}

mst = new MinimumSpanningTree(warePoints.size());
for (int from = 0; from < warePoints.size(); from++) {
for (int to = from + 1; to < warePoints.size(); to++) {
mst.addEdge(from, to, truckFixed + truckVariable * distance(x(warePoints.get(from)), y(warePoints.get(from)), x(warePoints.get(to)), y(warePoints.get(to))));
}
}
cost = mst.kruskal();
Utils.debug("MST cost", cost);

LinkedList<Integer> queue = new LinkedList<>();
boolean[] used = new boolean[warePoints.size()];
{
int min = (int) 1e9;
int mini = -1;
for (int i = 0; i < warePoints.size(); i++) {
Integer warePoint = warePoints.get(i);
int x = x(warePoint);
int y = y(warePoint);
int distance = distance(x, y, 500, 500);
if (distance < min) {
min = distance;
mini = i;
}
}
queue.add(mini);
used[mini] = true;
}
ArrayList<Pair<Integer, Integer>> edgesAndWarePairs = new ArrayList<>();
for (; !queue.isEmpty();) {
Integer v = queue.pollFirst();
int size = (v.intValue() >>> 16);
int index = v.intValue() & ((1 << 16) - 1);

edgesAndWarePairs.add(new Pair<Integer, Integer>(-size, index));

for (Edge3 edge3 : mst.G.get(index)) {
if (used[edge3.to]) {
continue;
}
used[edge3.to] = true;
queue.add(((size + 1) << 16) | edge3.to);
}
}
Collections.sort(edgesAndWarePairs);

used = new boolean[warePoints.size()];
for (int i = 0; i < edgesAndWarePairs.size() - 1; i++) {
Integer index = edgesAndWarePairs.get(i).second;
Integer warePoint = warePoints.get(index);
used[index] = true;
int fromX = x(warePoint);
int fromY = y(warePoint);
ArrayList<Customer> customers = warePointToCustomers.get(warePoint);
if (customers == null || customers.size() == 0) {
continue;
}

int toX = 500;
int toY = 500;

ArrayList<Edge3> edge3s = mst.G.get(index);
for (int j = 0; j < edge3s.size(); j++) {
if (used[edge3s.get(j).to]) {
continue;
}
Integer warePointTo = warePoints.get(edge3s.get(j).to);
toX = x(warePointTo);
toY = y(warePointTo);
break;
}
int truckCost = truckFixed + truckVariable * distance(toX, toY, fromX, fromY);
ArrayList<Integer> items = new ArrayList<>();
for (Customer customer : customers) {
items.add(customer.item);
}

Truck truck = new Truck(fromX, fromY, toX, toY, items);

if (!canAddTruck(truck.startX, truck.startY, truck.destX, truck.destY, truck.items)) {
return;
}
addTruck(truck);

if (warePointToCustomers.get(z(toX, toY)) == null) {
warePointToCustomers.put(z(toX, toY), new ArrayList<>());
}
warePointToCustomers.get(z(toX, toY)).addAll(customers);
warePointToCustomers.get(warePoint).clear();
score += truckCost;
Utils.debug(i, "score", score);
}

Pair<Integer, Integer> pair = edgesAndWarePairs.get(edgesAndWarePairs.size() - 1);
Integer warePoint = warePoints.get(pair.second.intValue());
points.add(new Point(x(warePoint), y(warePoint)));

Utils.debug("score", score);
}

private int truckCost(Point a, Point b) {
return truckFixed + truckVariable * distance(a.x, a.y, b.x, b.y);
}

private ArrayList<Point> points = new ArrayList<>();

private void SA2() {
score2 = calculateScore(points);
double second = Math.ceil(watch.getSecond());
sa.endTime = 8.0;
sa.init();
for (;; sa.numIterations++) {
{
sa.update();
if (sa.isTLE()) {
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%6.0f", score2), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}
if (sa.time > second) {
second++;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%6.0f", score2), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

mutate2();

}
}

private void mutate2() {
double random = 3 * rng.nextDouble();
if (random < 1) {
addPoint();
} else if (random < 2) {
removePoint();
} else if (random < 3) {
movePoint();
}
}

private double score2;

private void addPoint() {
int x = (int) (1001 * rng.nextDouble());
int y = (int) (1001 * rng.nextDouble());
points.add(new Point(x, y));

double score = calculateScore(points);

if (sa.accept(score - score2)) {
score2 = score;
} else {
points.remove(points.size() - 1);
}
}

private MinimumSpanningTree mst10 = new MinimumSpanningTree(1000);

private double calculateScore(ArrayList<Point> points2) {
mst10.clear(points2.size());
for (int i = 0; i < points2.size(); i++) {
Point pi = points2.get(i);
for (int j = i + 1; j < points2.size(); j++) {
Point pj = points2.get(j);
mst10.addEdge(i, j, truckFixed + truckVariable * distance(pi.x, pi.y, pj.x, pj.y));
}
}
int score = mst10.kruskal();
for (Customer customer : customers2) {
int min = (int) 1e9;
for (int i = 0; i < points2.size(); i++) {
int distance = distance(customer.x, customer.y, points2.get(i).x, points2.get(i).y);
if (distance < min) {
min = distance;
}
}
score += min;
}
return score;
}

private void removePoint() {
if (points.size() <= 1) {
return;
}
int index = 1 + (int) ((points.size() - 1) * rng.nextDouble());
Point p = points.remove(index);

double score = calculateScore(points);

if (sa.accept(score - score2)) {
score2 = score;
} else {
points.add(p);
}
}

private void movePoint() {
if (points.size() <= 1) {
return;
}

int index = 1 + (int) ((points.size() - 1) * rng.nextDouble());
int x = points.get(index).x;
int y = points.get(index).y;

points.get(index).x += (int) (-0.5 * sa.range + sa.range * rng.nextDouble());
points.get(index).x = Math.min(1000, Math.max(0, points.get(index).x));
points.get(index).y += (int) (-0.5 * sa.range + sa.range * rng.nextDouble());
points.get(index).y = Math.min(1000, Math.max(0, points.get(index).y));

double score = calculateScore(points);

if (sa.accept(score - score2)) {
score2 = score;
} else {
points.get(index).x = x;
points.get(index).y = y;
}
}

private void addTruck(Truck truck) {
trucks.add(truck);
addTruck(truck.startX, truck.startY, truck.destX, truck.destY, truck.items);
}

private void removeTruck(Truck truck) {
trucks.remove(truck);
removeTruck(truck.startX, truck.startY, truck.destX, truck.destY, truck.items);
}

private void addTruck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
for (Integer item : items) {
if (quantity(startY, startX, item) <= 0) {
Utils.debug("warehouses[startY][startX][item] <= 0");
return;
}
}
for (Integer item : items) {
add(startY, startX, item, -1);
add(destY, destX, item, 1);
}
}

private void removeTruck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
for (Integer item : items) {
add(startY, startX, item, 1);
add(destY, destX, item, -1);
}
}

private boolean canAddTruck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
for (Integer item : items) {
if (quantity(startY, startX, item) <= 0) {
return false;
}
}
return true;
}

private int quantity(int y, int x, Integer item) {
if (warePointToItemToQuantity.get(z(x, y)) == null) {
return 0;
}
if (warePointToItemToQuantity.get(z(x, y)).get(item) == null) {
return 0;
}
return warePointToItemToQuantity.get(z(x, y)).get(item);
}

private void add(int y, int x, Integer item, int value) {
assert item != null;
int z = z(x, y);
if (warePointToItemToQuantity.get(z) == null) {
warePointToItemToQuantity.put(z, new HashMap<>());
warePoints.add(z);
}
assert warePointToItemToQuantity.get(z) != null;
Integer quantity = warePointToItemToQuantity.get(z).get(item);
int value2 = (quantity == null ? 0 : quantity.intValue()) + value;
warePointToItemToQuantity.get(z).put(item, value2);
}

private void addCourier(int startX, int startY, int destX, int destY, int item) {
solution.add("C," + startX + "," + startY + "," + destX + "," + destY + "," + item);
score += Math.abs(startX - destX) + Math.abs(startY - destY);
}

private void saveBest() {
if (score < bestScore) {
bestScore = score;
bestTrucks.clear();
for (Truck truck : trucks) {
ArrayList<Integer> items = new ArrayList<>();
for (Integer item : truck.items) {
items.add(item);
}
bestTrucks.add(new Truck(truck.startX, truck.startY, truck.destX, truck.destY, items));
}
}
}

private void loadBest() {
score = bestScore;
for (int i = trucks.size() - 1; i >= 0; i--) {
Truck truck = trucks.get(i);
removeTruck(truck);
}
trucks.clear();
for (Truck truck : bestTrucks) {
ArrayList<Integer> items = new ArrayList<>();
for (Integer item : truck.items) {
items.add(item);
}
Truck e = new Truck(truck.startX, truck.startY, truck.destX, truck.destY, items);
addTruck(e);
}
}

private static int[] readArray(BufferedReader br) throws Exception {
int[] ret = new int[Integer.parseInt(br.readLine())];
for (int i = 0; i < ret.length; i++)
ret[i] = Integer.parseInt(br.readLine());
return ret;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
TrucksAndCouriers sol = new TrucksAndCouriers();
int truckFixed = Integer.parseInt(br.readLine());
int truckVariable = Integer.parseInt(br.readLine());
int[] warehouseX = readArray(br);
int[] warehouseY = readArray(br);
int[] warehouseItem = readArray(br);
int[] warehouseQuantity = readArray(br);
int[] customerX = readArray(br);
int[] customerY = readArray(br);
int[] customerItem = readArray(br);
String[] ret = sol.planShipping(truckFixed, truckVariable, warehouseX, warehouseY, warehouseItem, warehouseQuantity, customerX, customerY, customerItem);
System.out.println(ret.length);
for (int i = 0; i < ret.length; i++)
System.out.println(ret[i]);
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Edge {
int to;
int cap;
int cost;
int rev;

public Edge(int to, int cap, int cost, int rev) {
this.to = to;
this.cap = cap;
this.cost = cost;
this.rev = rev;
}
}

class MinCostFlow {

private static final int INF = (int) 1e9;
public ArrayList<ArrayList<Edge>> G;
private int[] dist;
private int[] prevv;
private int[] preve;

public MinCostFlow(int v) {
clear(v);
}

public void clear(int v) {
G = new ArrayList<ArrayList<Edge>>();
for (int i = 0; i < v; i++) {
G.add(new ArrayList<Edge>());
}
dist = new int[v];
prevv = new int[v];
preve = new int[v];
}

public void addEdge(int from, int to, int cap, int cost) {
assert cost >= 0;
assert cost <= INF;

int edgeIndex = G.get(from).size();
int reverseEdgeIndex = G.get(to).size();
G.get(from).add(new Edge(to, cap, cost, reverseEdgeIndex));
G.get(to).add(new Edge(from, 0, -cost, edgeIndex));
}

public int run(int s, int t, int f) {
int res = 0;
while (f > 0) {
Arrays.fill(dist, INF);
dist[s] = 0;

for (;;) {
boolean update = false;

for (int v = 0; v < dist.length; v++) {
if (dist[v] >= INF) {
continue;
}
for (int i = 0; i < G.get(v).size(); i++) {
Edge e = G.get(v).get(i);
if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}

if (!update) {
break;
}
}

if (dist[t] >= INF) {
return -1;
}

int d = f;
for (int v = t; v != s; v = prevv[v]) {
d = Math.min(d, G.get(prevv[v]).get(preve[v]).cap);
}

f -= d;
res += d * dist[t];

for (int v = t; v != s; v = prevv[v]) {
Edge e = G.get(prevv[v]).get(preve[v]);
e.cap -= d;
G.get(v).get(e.rev).cap += d;
}

}

return res;
}

public static int[] bestMatching(int[][] costs) {
assert check(costs);

int R = costs.length;
int C = costs[0].length;

MinCostFlow mcf = new MinCostFlow(R + C + 2);

int s = R + C;
int t = s + 1;

for (int r = 0; r < R; r++) {
mcf.addEdge(s, r, 1, 0);
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (costs[r][c] < 0) {
continue;
}
mcf.addEdge(r, R + c, 1, costs[r][c]);
}
}
for (int c = 0; c < C; c++) {
mcf.addEdge(R + c, t, 1, 0);
}

int minCost = mcf.run(s, t, R);

int[] rToC = new int[R];
Arrays.fill(rToC, -1);
for (int r = 0; r < R; r++) {
ArrayList<Edge> edges = mcf.G.get(r);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int c = e.to - R;
rToC[r] = c;
break;
}
}
return rToC;
}

private static boolean check(int[][] costs) {
assert costs.length > 0;
assert costs[0].length > 0;
for (int i = 1; i < costs.length; i++) {
assert costs[i].length == costs[i - 1].length;
}
return true;
}
}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 9.0;
public double time = startTime;

public double startTemperature = 10;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 100;
public double endRange = 5;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? TrucksAndCouriers.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateTime() {
time = useTime ? TrucksAndCouriers.watch.getSecond() : numIterations;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
return acceptS(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (TrucksAndCouriers.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}

assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (TrucksAndCouriers.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class Customer {
int x;
int y;
int item;
}

class Ware {
int x;
int y;
int[] quantity = new int[100];
}

class Truck {
int startX;
int startY;
int destX;
int destY;
ArrayList<Integer> items;

public Truck(int startX, int startY, int destX, int destY, ArrayList<Integer> items) {
super();
this.startX = startX;
this.startY = startY;
this.destX = destX;
this.destY = destY;
this.items = items;
}
}

class Edge3 {
int to;
int cost;

public Edge3(int to, int cost) {
this.to = to;
this.cost = cost;
}
}

class Edge2 {
int from;
int to;
int cost;

public Edge2(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}

class MinimumSpanningTree {

private static final int INF = (int) 1e9;
public ArrayList<ArrayList<Edge3>> G;
private ArrayList<Edge2> edges;
private int numVertexes;

public MinimumSpanningTree(int v) {
clear(v);
}

public void clear(int v) {
this.numVertexes = v;

if (G == null) {
G = new ArrayList<ArrayList<Edge3>>();
}
for (int i = 0; i < v; i++) {
if (i < G.size()) {
G.get(i).clear();
} else {
G.add(new ArrayList<Edge3>());
}
}
if (edges == null) {
edges = new ArrayList<Edge2>();
} else {
edges.clear();
}
}

public void addEdge(int from, int to, int cost) {
assert cost >= 0;
assert cost <= INF;
edges.add(new Edge2(from, to, cost));
}

private UnionFind unionFind = new UnionFind();

public int kruskal() {
unionFind.init(numVertexes);

Collections.sort(edges, new Comparator<Edge2>() {
@Override
public int compare(Edge2 o1, Edge2 o2) {
if (o1.cost < o2.cost) {
return -1;
}
if (o1.cost > o2.cost) {
return 1;
}
return 0;
}
});

int cost = 0;
int numEdges = 0;
for (Edge2 edge2 : edges) {
if (unionFind.isSame(edge2.from, edge2.to)) {
continue;
}
unionFind.unite(edge2.from, edge2.to);

G.get(edge2.from).add(new Edge3(edge2.to, edge2.cost));
G.get(edge2.to).add(new Edge3(edge2.from, edge2.cost));

cost += edge2.cost;
numEdges++;
if (numEdges >= numVertexes - 1) {
break;
}
}
return cost;
}

public int prim() {

ArrayList<ArrayList<Edge2>> G = new ArrayList<>();
for (int i = 0; i < numVertexes; i++) {
G.add(new ArrayList<>());
}
for (Edge2 edge2 : edges) {
G.get(edge2.from).add(new Edge2(edge2.from, edge2.to, edge2.cost));
G.get(edge2.to).add(new Edge2(edge2.to, edge2.from, edge2.cost));
}

int cost = 0;
int numEdges = 0;

boolean[] used = new boolean[numVertexes];
PriorityQueue<Edge2> pq = new PriorityQueue<>(new Comparator<Edge2>() {
@Override
public int compare(Edge2 o1, Edge2 o2) {
if (o1.cost < o2.cost) {
return -1;
}
if (o1.cost > o2.cost) {
return 1;
}
return 0;
}
});
{
int vertex = (int) (numVertexes * Math.random());
pq.add(new Edge2(vertex, vertex, 0));
}
for (; !pq.isEmpty();) {
Edge2 current = pq.poll();

if (used[current.to]) {
continue;
}

used[current.to] = true;
cost += current.cost;

if (current.from != current.to) {
numEdges++;
if (numEdges == numVertexes - 1) {
break;
}

this.G.get(current.from).add(new Edge3(current.to, current.cost));
this.G.get(current.to).add(new Edge3(current.from, current.cost));
}

for (Edge2 edge : G.get(current.to)) {
if (used[edge.to]) {
continue;
}
pq.add(edge);
}

}

return cost;
}

}

class Point {

public int x;
public int y;

public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}

}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class UnionFind {
private int[] par;
private int[] rank;

public void init(int n) {
if (par == null || par.length < n) {
par = new int[n];
}
if (rank == null || rank.length < n) {
rank = new int[n];
}
for (int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
}
}

public int getRoot(int x) {
if (par[x] == x) {
return x;
} else {
par[x] = getRoot(par[x]);
return par[x];
}
}

public void unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y) {
return;
}
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}

public boolean isSame(int x, int y) {
return getRoot(x) == getRoot(y);
}
}



このページのトップヘ