-
Notifications
You must be signed in to change notification settings - Fork 24
Expand file tree
/
Copy pathMain.java
More file actions
116 lines (105 loc) · 3.44 KB
/
Main.java
File metadata and controls
116 lines (105 loc) · 3.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static Solver practice2_e = new practice2_e();
static Solver GRL_6_B = new GRL_6_B();
public static void main(String[] args) {
// practice2_e.run();
GRL_6_B.run();
}
}
abstract class Solver implements Runnable { public abstract void run(); }
/**
* @problem
* AtCoder Library Practice Contest E - MinCostFlow
* {@see https://atcoder.jp/contests/practice2/tasks/practice2_e}
* @submission
* {@see https://atcoder.jp/contests/practice2/submissions/20811599}
*/
class practice2_e extends Solver {
static class Answer {
final long ans;
final char[][] g;
Answer(long ans, char[][] g) {
this.ans = ans;
this.g = g;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(ans);
for (char[] r : g) {
sb.append('\n').append(r);
}
return sb.toString();
}
}
public void run() {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());
int k = Integer.parseInt(sc.next());
long[][] a = new long[n][n];
for (long[] r : a) Arrays.setAll(r, j -> Long.parseLong(sc.next()));
sc.close();
System.out.println(solve(n, k, a));
}
static final long INF = 1l << 50;
public Answer solve(int n, int k, long[][] a) {
MinCostFlow mcf = new MinCostFlow(n + n + 2);
int s = n + n , t = s + 1;
mcf.addEdge(s, t, n * k, INF);
for(int i = 0; i < n; i++) {
mcf.addEdge(s, i, k, 0);
mcf.addEdge(i + n, t, k, 0);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mcf.addEdge(i, j + n, 1, INF - a[i][j]);
}
}
MinCostFlow.FlowAndCost res = mcf.minCostFlow(s, t, n * k);
long ans = INF * res.flow - res.cost;
MinCostFlow.WeightedCapEdge[] es = mcf.getEdges();
char[][] g = new char[n][n];
for (char[] r : g) Arrays.fill(r, '.');
for (MinCostFlow.WeightedCapEdge e : es) {
if (e.flow == 1 && e.from != s && e.to != t) {
g[e.from][e.to - n] = 'X';
}
}
return new Answer(ans, g);
}
}
/**
* @problem
* GRL_6 B - Minimum Cost Flow
* {@see https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B}
* @submission
* {@see https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5281698#1}
*/
class GRL_6_B extends Solver {
public int solve(int n, int m, int f, int[][] edges) {
MinCostFlow mcf = new MinCostFlow(n);
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int c = edge[2];
int d = edge[3];
mcf.addEdge(u, v, c, d);
}
MinCostFlow.FlowAndCost fc = mcf.minCostFlow(0, n - 1, f);
return (int) (fc.flow == f ? fc.cost : -1);
}
public void run() {
Scanner sc = new Scanner(System.in);
int v = Integer.parseInt(sc.next());
int e = Integer.parseInt(sc.next());
int f = Integer.parseInt(sc.next());
int[][] edges = new int[e][4];
for (int[] edge : edges) {
Arrays.setAll(edge, i -> Integer.parseInt(sc.next()));
}
sc.close();
System.out.println(solve(v, e, f, edges));
}
}