Skip to content

Self loop handling (in flow-problem library) #43 #61

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
NASU41 merged 5 commits into from
Mar 10, 2021
Merged

Self loop handling (in flow-problem library) #43 #61

Changes from 1 commit
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
6dbe977
self-loop handling
suisen-cp Mar 10, 2021
79ba007
add test for MaxFlow
suisen-cp Mar 10, 2021
1f919da
Self loop handling (Min Cost Flow) #43
suisen-cp Mar 10, 2021
de81778
fix access modifiers of members of MaxFlow.CapEdge
suisen-cp Mar 10, 2021
0495145
fix Readme of MaxFlow/MinCostFlow
suisen-cp Mar 10, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
add test for MaxFlow
  • Loading branch information
@suisen-cp
suisen-cp committed Mar 10, 2021
commit 79ba007b1b8898480c0bba13ad20644f778b69f3
201 changes: 173 additions & 28 deletions MaxFlow/Main.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,39 +1,29 @@
import java.util.Arrays;
import java.util.Scanner;

public class Main {
static Solver practice2_d = new practice2_d();
static Solver arc074_d = new arc074_d();
static Solver abc193_f = new abc193_f();

public static void main(String[] args) {
// practice2_d.run();
// arc074_d.run();
abc193_f.run();
}
}

abstract class Solver implements Runnable { public abstract void run(); }

/**
* @problem
* AtCoder Library Practice Contest D - Maxflow
* {@link https://atcoder.jp/contests/practice2/tasks/practice2_d}
* {@see https://atcoder.jp/contests/practice2/tasks/practice2_d}
* @submission
* {@link https://atcoder.jp/contests/practice2/submissions/20808482}
* {@see https://atcoder.jp/contests/practice2/submissions/20808482}
*/
public class Main {
static class Answer {
final int c;
final char[][] g;
Answer(int c, char[][] g) { this.c = c; this.g = g; }
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(c);
for (char[] row : g) {
sb.append('\n').append(row);
}
return sb.toString();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
int m = Integer.parseInt(sc.next());
char[][] g = new char[n][];
Arrays.setAll(g, i -> sc.next().toCharArray());
sc.close();
System.out.println(solve(n, m, g));
}

public static Answer solve(int n, int m, char[][] g) {
class practice2_d extends Solver {
public Answer solve(int n, int m, char[][] g) {
MaxFlow mf = new MaxFlow(n * m + 2);
int s = n * m;
int t = s + 1;
Expand Down Expand Up @@ -104,5 +94,160 @@ public static Answer solve(int n, int m, char[][] g) {
if (ans != cnt) throw new AssertionError();
return new Answer(ans, g);
}

static class Answer {
final int c;
final char[][] g;
Answer(int c, char[][] g) { this.c = c; this.g = g; }
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(c);
for (char[] row : g) {
sb.append('\n').append(row);
}
return sb.toString();
}
}

public void run() {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
int m = Integer.parseInt(sc.next());
char[][] g = new char[n][];
Arrays.setAll(g, i -> sc.next().toCharArray());
sc.close();
System.out.println(solve(n, m, g));
}
}

/**
* @problem
* AtCoder Regular Contest 074 F - Lotus Leaves
* {@see https://atcoder.jp/contests/arc074/tasks/arc074_d}
* @submission
* {@see https://atcoder.jp/contests/arc074/submissions/20808863}
*/
class arc074_d extends Solver {
static final int INF = 1 << 20;
public int solve(int h, int w, char[][] g) {
int si = -1, sj = -1, ti = -1, tj = -1;
boolean[][] grid = new boolean[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (g[i][j] == 'S') {
si = i; sj = j;
grid[i][j] = true;
} else if (g[i][j] == 'T') {
ti = i; tj = j;
grid[i][j] = true;
} else if (g[i][j] == 'o') {
grid[i][j] = true;
}
}
}
int s = h + w;
int t = s + 1;
MaxFlow mf = new MaxFlow(h + w + 2);
mf.addEdge(s , si , INF);
mf.addEdge(s , sj + h, INF);
mf.addEdge(ti , t , INF);
mf.addEdge(tj + h, t , INF);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (grid[i][j]) {
mf.addEdge(i, j + h, 1);
mf.addEdge(j + h, i, 1);
}
}
}
int flow = (int) mf.maxFlow(s, t);
return flow >= INF ? -1 : flow;
}

public void run() {
Scanner sc = new Scanner(System.in);
int h = Integer.parseInt(sc.next());
int w = Integer.parseInt(sc.next());
char[][] g = new char[h][];
Arrays.setAll(g, i -> sc.next().toCharArray());
sc.close();
System.out.println(solve(h, w, g));
}
}

/**
* @problem
* AtCoder Beginner Contest 193 F - Zebraness
* {@see https://atcoder.jp/contests/abc193/tasks/abc193_f}
* @submission
* {@see https://atcoder.jp/contests/abc193/submissions/20808965}
*/
class abc193_f extends Solver {
static final int[] dx4 = {1, 0, -1, 0};
static final int[] dy4 = {0, 1, 0, -1};

public int solve(int n, char[][] c) {
int[][] id = new int[n][n];
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (c[i][j] == '?') {
id[i][j] = cnt++;
}
}
}

int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i < n - 1) {
if (c[i][j] == 'B' && c[i + 1][j] == 'W' || c[i][j] == 'W' && c[i + 1][j] == 'B') {
ans++;
}
}
if (j < n - 1) {
if (c[i][j] == 'B' && c[i][j + 1] == 'W' || c[i][j] == 'W' && c[i][j + 1] == 'B') {
ans++;
}
}
}
}
MaxFlow mf = new MaxFlow(cnt + 2);
int s = cnt, t = cnt + 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (c[i][j] == '?') {
int b = 0, w = 0;
for (int d = 0; d < 4; d++) {
int ni = i + dx4[d];
int nj = j + dy4[d];
if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
if (c[ni][nj] == 'B') {
b++;
} else if (c[ni][nj] == 'W') {
w++;
} else if (d < 2) {
mf.addEdge(id[i][j], id[ni][nj], 1);
mf.addEdge(id[ni][nj], id[i][j], 1);
ans++;
}
}
mf.addEdge(id[i][j], t, (i + j) % 2 == 1 ? b : w);
mf.addEdge(s, id[i][j], (i + j) % 2 == 1 ? w : b);
ans += b + w;
}
}
}
return (int) (ans - mf.maxFlow(s, t));
}

public void run() {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
char[][] c = new char[n][];
Arrays.setAll(c, i -> sc.next().toCharArray());
sc.close();
System.out.println(solve(n, c));
}
}