版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434649
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
开始最小费用流的学习,算法思路:找寻最短费用的增广路径,证明采用反证法。《挑战》P225有详细的证明过程,具体看书。
Bellman-Ford算法:
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/2135.txt";
void solve() {
int N = ni();
int M = ni();
init(N);
for (int i = 0; i < M; ++i){
int from = ni();
int to = ni();
int cost = ni();
addEdge(from - 1, to - 1, 1, cost);
addEdge(to - 1, from - 1, 1, cost);
}
out.println(minCostFlow(0, N - 1, 2));
}
//最小费用算法 Bellman-Ford算法
class Edge{
int from;
int to;
int cap;
int cost;
int rev;
public Edge(int from, int to, int cap, int cost, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.cost = cost;
this.rev = rev;
}
}
List<Edge>[] g;
int V;
int[] distance;
int[] prevv;
int[] preve;
static final int INF = 1 << 29;
public void init(int n){
V = n;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();
distance = new int[V];
prevv = new int[V];
preve = new int[V];
}
public void addEdge(int from, int to, int cap, int cost){
g[from].add(new Edge(from, to, cap, cost, g[to].size()));
g[to].add(new Edge(to, from, 0, -cost, g[from].size() - 1)); //增广路径的经典反悔推倒重来
}
public int minCostFlow(int s, int t, int f){
int res = 0;
while (f > 0){ //在指定流量下的最小费用,如果找不到增广路径则返回-1
Arrays.fill(distance, INF);
distance[s] = 0;
boolean update = true;
while (update){
update = false;
for (int v = 0; v < V; ++v){
if (distance[v] == INF) continue; //如果该顶点为INF则没必要更新
for (int i = 0; i < g[v].size(); ++i){
Edge e = g[v].get(i);
if (e.cap > 0 && distance[e.to] > distance[e.from] + e.cost){
distance[e.to] = distance[e.from] + e.cost; //松弛法更新
prevv[e.to] = v; //记录前置顶点
preve[e.to] = i; //记录前置边
update = true;
}
}
}
}
if (distance[t] == INF){
return -1;
}
int d = f;
for (int v = t; v != s; v = prevv[v]){
d = Math.min(d, g[prevv[v]].get(preve[v]).cap); //更新增广路径的最小流量
}
f -= d;
res += d * distance[t];
for (int v = t; v != s; v = prevv[v]){ //构造残余网络
Edge e = g[prevv[v]].get(preve[v]);
e.cap -= d;
g[v].get(e.rev).cap += d;
}
}
return res;
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new Main().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}
时间复杂度为O(|F||V||E|)O(\vert F\vert \vert V\vert \vert E \vert)。
Dijkstra算法的具体实现并没搞懂,暂且就不实现了,日后复习再来看看。
规则:已经运输过的路线不能再选择,且每个顶点存储的容量为1,所以导致运输容量为1。增加超级源点和超级汇点,构造容量为2,费用为0,这样舰队分批送到汇点的即为最小费用,依旧像生产流水线。
代码如下:
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/3068.txt";
void solve() {
int cnt = 0;
while (true){
int N = ni();
int M = ni();
if (N + M == 0) break;
init (N + 2);
int s = 0;
int t = N + 1;
addEdge(s, 1, 2, 0);
addEdge(N, t, 2, 0);
for (int i = 0; i < M; ++i){
int from = ni();
int to = ni();
int cost = ni();
addEdge(from + 1, to + 1, 1, cost);
}
int minCost = minCostFlow(s, t, 2);
if (minCost == -1){
out.println("Instance #" + (++cnt) + ": Not possible");
}
else{
out.println("Instance #" + (++cnt) + ": " + minCost);
}
}
}
//最小费用流 Bellman Ford
class Edge{
int from;
int to;
int cost;
int cap;
int rev;
public Edge(int from, int to, int cap, int cost, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.cost = cost;
this.rev = rev;
}
}
static final int INF = 1 << 29;
List<Edge>[] g;
int V;
int[] prevv;
int[] preve;
int[] distance;
public void init(int n){
V = n;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();
prevv = new int[V];
preve = new int[V];
distance = new int[V];
}
public void addEdge(int from, int to, int cap, int cost){
g[from].add(new Edge(from, to, cap, cost, g[to].size()));
g[to].add(new Edge(to, from, 0, -cost, g[from].size() - 1));
}
public int minCostFlow(int s, int t, int f){
int res = 0;
while (f > 0){
boolean update = true;
Arrays.fill(distance, INF);
distance[s] = 0;
while (update){
update = false;
for (int v = 0; v < V; ++v){
if (distance[v] == INF) continue;
for (int i = 0; i < g[v].size(); ++i){
Edge e = g[v].get(i);
if (e.cap > 0 && distance[e.to] > distance[e.from] + e.cost){
distance[e.to] = distance[e.from] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
if (distance[t] == INF){
return -1;
}
int d = f;
for (int v = t; v != s; v = prevv[v]){
d = Math.min(d, g[prevv[v]].get(preve[v]).cap);
}
f -= d;
res += d * distance[t];
for (int v = t; v != s; v = prevv[v]){
Edge e = g[prevv[v]].get(preve[v]);
e.cap -= d;
g[v].get(e.rev).cap += d;
}
}
return res;
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new Main().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}
比较简单,对于一个男人计算与每个房子的距离,建立cost,且容量为1,增加超级源点和汇点,生成n条流水线,n为男人的个数。
代码如下:
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/2195.txt";
void solve() {
while (true){
int N = ni();
int M = ni();
if (N + M == 0) break;
char[][] board = new char[N][M];
int n = 0;
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
board[i][j] = nc();
if (board[i][j] == 'H') n ++;
}
}
int[][] posMan = new int[n][2];
int[][] posHos = new int[n][2];
for (int i = 0, c1 = 0, c2 = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
if (board[i][j] == 'H'){
posMan[c1++] = new int[]{i, j};
}
if (board[i][j] == 'm'){
posHos[c2++] = new int[]{i, j};
}
}
}
init(2 * n + 2);
int s = 0;
int t = 2 * n + 1;
for (int i = 0; i < n; ++i){
addEdge(s, i + 1, 1, 0);
addEdge(n + i + 1, t, 1, 0);
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
int cost = Math.abs(posMan[i][0] - posHos[j][0]) + Math.abs(posMan[i][1] - posHos[j][1]);
addEdge(i + 1, n + j + 1, 1, cost);
}
}
out.println(minCostFlow(s, t, n));
}
}
//最小费用流 Bellman Ford
class Edge{
int from;
int to;
int cost;
int cap;
int rev;
public Edge(int from, int to, int cap, int cost, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.cost = cost;
this.rev = rev;
}
}
static final int INF = 1 << 29;
List<Edge>[] g;
int V;
int[] prevv;
int[] preve;
int[] distance;
public void init(int n){
V = n;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();
prevv = new int[V];
preve = new int[V];
distance = new int[V];
}
public void addEdge(int from, int to, int cap, int cost){
g[from].add(new Edge(from, to, cap, cost, g[to].size()));
g[to].add(new Edge(to, from, 0, -cost, g[from].size() - 1));
}
public int minCostFlow(int s, int t, int f){
int res = 0;
while (f > 0){
boolean update = true;
Arrays.fill(distance, INF);
distance[s] = 0;
while (update){
update = false;
for (int v = 0; v < V; ++v){
if (distance[v] == INF) continue;
for (int i = 0; i < g[v].size(); ++i){
Edge e = g[v].get(i);
if (e.cap > 0 && distance[e.to] > distance[e.from] + e.cost){
distance[e.to] = distance[e.from] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
if (distance[t] == INF){
return -1;
}
int d = f;
for (int v = t; v != s; v = prevv[v]){
d = Math.min(d, g[prevv[v]].get(preve[v]).cap);
}
f -= d;
res += d * distance[t];
for (int v = t; v != s; v = prevv[v]){
Edge e = g[prevv[v]].get(preve[v]);
e.cap -= d;
g[v].get(e.rev).cap += d;
}
}
return res;
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new Main().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}
思路:依旧是最小费用流,需要注意抵达end结点时,它的值不算在内。构造伪点,每个结点分裂成两个顶点,分别为权值为负,容量为1的顶点和权值为0,容量为无穷的顶点,这样当一个顶点被访问过后,依旧可以访问该顶点,此时权值为0(由题意得),接着再让这些顶点连接到下顶点和右顶点即可。
代码如下:
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/3422.txt";
void solve() {
int N = ni();
int K = ni();
int[][] board = new int[N][N];
for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
board[i][j] = ni();
}
}
init(2 * N * N + 1);
int s = 0;
int t = 2 * N * N;
addEdge(s, id_of(0, 0, N), K, 0);
for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
int current = id_of(i, j, N);
addEdge(current, current + 1, 1, -board[i][j]);
addEdge(current, current + 1, K , 0);
if (i + 1 < N){
int down = id_of(i + 1, j, N);
addEdge(current + 1, down, K, 0);
}
if (j + 1 < N){
int right = id_of(i, j + 1, N);
addEdge(current + 1, right, K, 0);
}
}
}
out.println(-minCostFlow(s, t, K));
}
public int id_of(int i, int j, int N){
return 2 * (N * i + j) + 1;
}
//最小费用流 Bellman Ford
class Edge{
int from;
int to;
int cost;
int cap;
int rev;
public Edge(int from, int to, int cap, int cost, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.cost = cost;
this.rev = rev;
}
}
static final int INF = 1 << 29;
List<Edge>[] g;
int V;
int[] prevv;
int[] preve;
int[] distance;
public void init(int n){
V = n;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();
prevv = new int[V];
preve = new int[V];
distance = new int[V];
}
public void addEdge(int from, int to, int cap, int cost){
g[from].add(new Edge(from, to, cap, cost, g[to].size()));
g[to].add(new Edge(to, from, 0, -cost, g[from].size() - 1));
}
public int minCostFlow(int s, int t, int f){
int res = 0;
while (f > 0){
boolean update = true;
Arrays.fill(distance, INF);
distance[s] = 0;
while (update){
update = false;
for (int v = 0; v < V; ++v){
if (distance[v] == INF) continue;
for (int i = 0; i < g[v].size(); ++i){
Edge e = g[v].get(i);
if (e.cap > 0 && distance[e.to] > distance[e.from] + e.cost){
distance[e.to] = distance[e.from] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
if (distance[t] == INF){
return -1;
}
int d = f;
for (int v = t; v != s; v = prevv[v]){
d = Math.min(d, g[prevv[v]].get(preve[v]).cap);
}
f -= d;
res += d * distance[t];
for (int v = t; v != s; v = prevv[v]){
Edge e = g[prevv[v]].get(preve[v]);
e.cap -= d;
g[v].get(e.rev).cap += d;
}
}
return res;
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new Main().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}