Created
October 12, 2019 22:14
-
-
Save weihao/c2aa6aa1bc93f415ae64c72ec6efc15d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.awt.*; | |
import java.util.*; | |
import java.util.List; | |
public class CopsAndRobbers { | |
static long one = 1; | |
public static void main(String[] args) { | |
Scanner in = new Scanner(System.in); | |
int n = in.nextInt(); | |
int m = in.nextInt(); | |
int c = in.nextInt(); | |
int[] colors = new int[c]; | |
for (int i = 0; i < colors.length; i++) { | |
} | |
char[][] graph = new char[n][m]; | |
in.nextLine(); | |
for (int i = 0; i < n; i++) { | |
char[] line = in.nextLine().toCharArray(); | |
for (int j = 0; j < m; j++) | |
graph[i][j] = line[j]; | |
} | |
for (char[] row : graph) { | |
System.out.println(Arrays.toString(row)); | |
} | |
in.nextInt(); | |
MaxFlowSolver dinic = new Dinic(((n * m) - 4) * 4); | |
Map<Point, List<Node>> map = new HashMap<>(); | |
List<Node> list = new ArrayList<Node>(); | |
Node sink = dinic.addNode(); | |
Point[][] points = new Point[n][m]; | |
list.add(sink); | |
map.put(new Point(-1, -1), list); | |
Node src = new Node(); | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < m; j++) { | |
char curr = graph[i][j]; | |
if ((i == 0 && j == 0) || (i == 0 && j == m - 1) || (i == n - 1 && j == 0) || (i == n - 1 && j == m - 1)) { | |
if (curr == 'B') { | |
System.out.println("-1"); | |
return; | |
} | |
continue; | |
} | |
if (curr == 'B') { | |
src = dinic.addNode(); | |
if (i > 0) { | |
Point p = points[i-1][j]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
dinic.link(src, in2, one, 0); | |
} | |
if (i < n - 1) { | |
Point p = points[i+1][j]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
dinic.link(src, in2, one, 0); | |
} | |
if (j > 0) { | |
Point p = points[i][j-1]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
dinic.link(src, in2, one, 0); | |
} | |
if (j < m - 1) { | |
Point p = points[i][j+1]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
dinic.link(src, in2, one, 0); | |
dinic.link(src, in2, one, 0); | |
} | |
} else { | |
long cost = (curr == '.') ? Long.MAX_VALUE : colors['a' - curr]; | |
Node in1 = dinic.addNode(); | |
Node out = dinic.addNode(); | |
dinic.link(in1, out, 1, cost); | |
List<Node> nodeList = new ArrayList<Node>(); | |
nodeList.add(in1); | |
nodeList.add(out); | |
Point newPoint = new Point(i,j); | |
points[i][j] = newPoint; | |
map.put(newPoint, nodeList); | |
if (i > 0) { | |
if(graph[i-1][j] == 'B') continue; | |
Point p = points[i-1][j]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
Node out2 = other.get(1); | |
dinic.link(in1, out2, one, 0); | |
dinic.link(in2, out, one, 0); | |
} | |
if (i < n - 1) { | |
if(graph[i+1][j] == 'B') continue; | |
Point p = points[i+1][j]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
Node out2 = other.get(1); | |
dinic.link(in1, out2, one, 0); | |
dinic.link(in2, out, one, 0); | |
} | |
if (j > 0) { | |
if(graph[i][j-1] == 'B') continue; | |
Point p = points[i][j-1]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
Node out2 = other.get(1); | |
dinic.link(in1, out2, one, 0); | |
dinic.link(in2, out, one, 0); | |
} | |
if (j < m - 1) { | |
if(graph[i][j+1] == 'B') continue; | |
Point p = points[i][j+1]; | |
List<Node> other = map.get(p); | |
Node in2 = other.get(0); | |
Node out2 = other.get(1); | |
dinic.link(in1, out2, one, 0); | |
dinic.link(in2, out, one, 0); | |
} | |
if (i == 0 || j == 0 || i == n - 1 || j == m - 1) { | |
sink = map.get(new Point(-1, -1)).get(0); | |
dinic.link(out, sink, one, 0); | |
} | |
} | |
} | |
sink = map.get(new Point(-1,-1)).get(0); | |
long d = dinic.getMaxFlow(src, sink); | |
if (d == Long.MAX_VALUE) { | |
System.out.println("-1"); | |
return; | |
} | |
System.out.println(d); | |
} | |
} | |
public static class Node { | |
// thou shall not create nodes except through addNode() | |
private Node() { | |
} | |
List<Edge> edges = new ArrayList<Edge>(); | |
int index; // index in nodes array | |
// The following fields are needed only if the respective solvers | |
// are being used. We include them here for improved spatial locality. | |
// To avoid unnecessary memory consumption, be sure to remove | |
// those fields that aren't used by the solver you are using | |
// | |
int dist; // PushRelabel, Dinic, and AhujaOrlin. | |
boolean blocked; // Dinic | |
} | |
public static class Edge { | |
boolean forward; // true: edge is in original graph | |
// false: edge is a backward edge | |
Node from, to; // nodes connected | |
long flow; // current flow | |
final long capacity; | |
Edge dual; // reference to this edge's dual | |
long cost; // only used for MinCost. | |
// thou shall not create edges except through link() | |
protected Edge(Node s, Node d, long c, boolean f) { | |
forward = f; | |
from = s; | |
to = d; | |
capacity = c; | |
} | |
// remaining capacity() | |
long remaining() { | |
return capacity - flow; | |
} | |
// increase flow and adjust dual | |
void addFlow(long amount) { | |
flow += amount; | |
dual.flow -= amount; | |
} | |
} | |
/* A Max Flow solver base class. */ | |
public static abstract class MaxFlowSolver { | |
/* List of nodes, indexed. */ | |
List<Node> nodes = new ArrayList<Node>(); | |
/* Create an edge between nodes n1 and n2 */ | |
public void link(Node n1, Node n2, long capacity) { | |
/* | |
* Only the EdmondsKarp solver takes cost into account | |
* during getMaxFlow(). Setting it to 1 for problems | |
* that do not involve cost means it uses a shortest path | |
* search when finding augmenting paths. In practice, | |
* this does not seem to make a difference. | |
*/ | |
link(n1, n2, capacity, 1); | |
} | |
/* Create an edge between nodes n1 and n2 and assign cost */ | |
public void link(Node n1, Node n2, long capacity, long cost) { | |
Edge e12 = new Edge(n1, n2, capacity, true); | |
Edge e21 = new Edge(n2, n1, 0, false); | |
e12.dual = e21; | |
e21.dual = e12; | |
n1.edges.add(e12); | |
n2.edges.add(e21); | |
e12.cost = cost; | |
e21.cost = -cost; | |
} | |
/* Create an edge between nodes n1 and n2 */ | |
void link(int n1, int n2, long capacity) { | |
link(nodes.get(n1), nodes.get(n2), capacity); | |
} | |
/* Create a graph with n nodes. */ | |
protected MaxFlowSolver(int n) { | |
for (int i = 0; i < n; i++) | |
addNode(); | |
} | |
protected MaxFlowSolver() { | |
this(0); | |
} | |
public abstract long getMaxFlow(Node src, Node snk); | |
/* Add a new node. */ | |
public Node addNode() { | |
Node n = new Node(); | |
n.index = nodes.size(); | |
nodes.add(n); | |
return n; | |
} | |
} | |
/** | |
* Dinic's algorithm, Shimon Even variant. | |
*/ | |
public static class Dinic extends MaxFlowSolver { | |
long BlockingFlow(Node src, Node snk) { | |
int N = nodes.size(); | |
for (Node u : nodes) { | |
u.dist = -1; | |
u.blocked = false; | |
} | |
Node[] Q = new Node[N]; | |
/* Step 1. BFS from source to compute levels */ | |
src.dist = 0; | |
int head = 0, tail = 0; | |
Q[tail++] = src; | |
while (head < tail) { | |
Node x = Q[head++]; | |
List<Edge> succ = x.edges; | |
for (Edge e : succ) { | |
if (e.to.dist == -1 && e.remaining() > 0) { | |
e.to.dist = e.from.dist + 1; | |
Q[tail++] = e.to; | |
} | |
} | |
} | |
if (snk.dist == -1) // no flow if sink is not reachable | |
return 0; | |
/* Step 2. Push flow down until we have a blocking flow */ | |
long flow, totflow = 0; | |
do { | |
flow = dfs(src, snk, Long.MAX_VALUE); | |
totflow += flow; | |
} while (flow > 0); | |
return totflow; | |
} | |
/* | |
* Run DFS on the BFS level graph. | |
*/ | |
long dfs(Node v, Node snk, long mincap) { | |
// reached sink | |
if (v == snk) | |
return mincap; | |
for (Edge e : v.edges) { | |
// standard DFS, but consider an edge only if | |
if (!e.to.blocked // the path to the sink is not already blocked | |
&& e.from.dist + 1 == e.to.dist // it's in the BFS level graph | |
&& e.remaining() > 0) { // the edge has remaining capacity | |
long flow = dfs(e.to, snk, Math.min(mincap, e.remaining())); | |
if (flow > 0) { | |
e.addFlow(flow); | |
return flow; | |
} | |
} | |
} | |
// if we couldn't add any flow then there is no point in ever going | |
// past this node again. Mark it blocked. | |
v.blocked = true; | |
return 0; | |
} | |
@Override | |
public long getMaxFlow(Node src, Node snk) { | |
long flow, totflow = 0; | |
while ((flow = BlockingFlow(src, snk)) != 0) | |
totflow += flow; | |
return totflow; | |
} | |
public Dinic() { | |
this(0); | |
} | |
public Dinic(int n) { | |
super(n); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment