洛谷P3381 【模板】最小费用最大流

题目链接：https://www.luogu.com.cn/problem/P3381

代码实现

  1. import java.io.*;
  2. import java.util.*;
  4. public class Main {
  5.     // 图
  6.     private static List<List<Edge>> graph;
  8.     // 顶点数
  9.     static int V;
  11.     // 顶点的势
  12.     static int[] h;
  14.     // 到达目标结点的最短距离
  15.     static int[] dist;
  17.     // 最短路中的前驱节点
  18.     static int[] prevV;
  20.     // 最短路中的前驱节点对应的边
  21.     static int[] prevE;
  23.     public static void main(String[] args) throws IOException {
  24.         StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  25.         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  27.         in.nextToken();
  28.         int N = (int) in.nval;
  29.         in.nextToken();
  30.         int M = (int) in.nval;
  31.         in.nextToken();
  32.         int src = (int) in.nval;
  33.         in.nextToken();
  34.         int dst = (int) in.nval;
  35.         V = N + 1;
  36.         init();
  38.         while (M-- > 0) {
  39.             int from, to, capacity, cost;
  40.             in.nextToken();
  41.             from = (int) in.nval;
  42.             in.nextToken();
  43.             to = (int) in.nval;
  44.             in.nextToken();
  45.             capacity = (int) in.nval;
  46.             in.nextToken();
  47.             cost = (int) in.nval;
  48.             addEgde(from, to, capacity, cost);
  49.         }
  50.         int[] ans = minCostFlow(src, dst);
  51.         out.println(ans[0] + " " + ans[1]);
  52.         out.flush();
  53.     }
  55.     private static void init() {
  56.         graph = new ArrayList<List<Edge>>(V);
  57.         for (int i = 0; i < V; ++i) {
  58.             graph.add(new ArrayList<Edge>());
  59.         }
  60.         h = new int[V];
  61.         dist = new int[V];
  62.         prevV = new int[V];
  63.         prevE = new int[V];
  64.     }
  66.     // 向图中增加一条从from到to的容量为cap费用为cost的边
  67.     private static void addEgde(int from, int to, int cap, int cost) {
  68.         graph.get(from).add(new Edge(to, cap, cost, graph.get(to).size()));
  69.         graph.get(to).add(new Edge(from, 0, -cost, graph.get(from).size() - 1));
  70.     }
  72.     // 求解从s到t流量为f的最大容量最小费用流
  73.     private static int[] minCostFlow(final int src, final int dst) {
  74.         int res = 0;
  75.         int flow = 0;
  76.         Arrays.fill(h, 0);
  78.         while (true) {
  79.             // 使用Dijkstra算法更新h
  80.             Arrays.fill(dist, Integer.MAX_VALUE);
  81.             dist[src] = 0;
  83.             // int[0]存储最短距离
  84.             // int[1]存储结点编号
  85.             // 建立小根堆
  86.             Comparator<int[]> comparator = new Comparator<int[]>() {
  87.                 public int compare(int[] o1, int[] o2) {
  88.                     return o1[0] - o2[0];
  89.                 }
  90.             };
  91.             Queue<int[]> queue = new PriorityQueue<int[]>(comparator);
  92.             queue.offer(new int[]{0, src});
  94.             while (!queue.isEmpty()) {
  95.                 int[] pair = queue.poll();
  96.                 int v = pair[1];
  97.                 if (dist[v] < pair[0]) {
  98.                     continue;
  99.                 }
  100.                 for (int i = 0; i < graph.get(v).size(); ++i) {
  101.                     Edge edge = graph.get(v).get(i);
  102.                     if ((edge.capacity > 0) && (dist[edge.to] > dist[v] + edge.cost + h[v] - h[edge.to])) {
  103.                         dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to];
  104.                         prevV[edge.to] = v;
  105.                         prevE[edge.to] = i;
  106.                         queue.offer(new int[]{dist[edge.to], edge.to});
  107.                     }
  108.                 }
  109.             }
  111.             // 不能再增广
  112.             if (dist[dst] == Integer.MAX_VALUE) {
  113.                 break;
  114.             }
  116.             for (int v = 0; v < V; ++v) {
  117.                 h[v] += dist[v];
  118.             }
  120.             // 找到路径上容量最小的边
  121.             int minCapacity = Integer.MAX_VALUE;
  122.             for (int v = dst; v != src; v = prevV[v]) {
  123.                 minCapacity = Math.min(minCapacity, graph.get(prevV[v]).get(prevE[v]).capacity);
  124.             }
  126.             // 沿s到t的最短路尽量增广
  127.             // 计算残差网络
  128.             flow += minCapacity;
  129.             res += minCapacity * h[dst];
  130.             for (int v = dst; v != src; v = prevV[v]) {
  131.                 Edge e = graph.get(prevV[v]).get(prevE[v]);
  132.                 e.capacity -= minCapacity;
  133.                 graph.get(v).get(e.reserve).capacity += minCapacity;
  134.             }
  135.         }
  136.         return new int[]{flow, res};
  137.     }
  138. }
  140. class Edge {
  141.     int to;
  142.     int capacity;
  143.     int cost;
  144.     int reserve;
  146.     public Edge(int to, int capacity, int cost, int reserve) {
  147.         this.to = to;
  148.         this.capacity = capacity;
  149.         this.cost = cost;
  150.         this.reserve = reserve;
  151.     }
  152. }

输入样例

  1. 4 5 4 3
  2. 4 2 30 2
  3. 4 3 20 3
  4. 2 3 20 1
  5. 2 1 30 9
  6. 1 3 40 5

输出样例

  1. 50 280

可行流最小费用

根据模板简单修改。

代码实现

  1. import java.io.*;
  2. import java.util.*;
  4. public class Main {
  5.     // 图
  6.     private static List<List<Edge>> graph;
  8.     // 顶点数
  9.     static int V;
  11.     // 顶点的势
  12.     static int[] h;
  14.     // 到达目标结点的最短距离
  15.     static int[] dist;
  17.     // 最短路中的前驱节点
  18.     static int[] prevV;
  20.     // 最短路中的前驱节点对应的边
  21.     static int[] prevE;
  23.     public static void main(String[] args) throws IOException {
  24.         StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  25.         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  27.         in.nextToken();
  28.         int N = (int) in.nval;
  29.         in.nextToken();
  30.         int M = (int) in.nval;
  31.         in.nextToken();
  32.         int src = (int) in.nval;
  33.         in.nextToken();
  34.         int dst = (int) in.nval;
  35.         V = N + 1;
  36.         init();
  38.         while (M-- > 0) {
  39.             int from, to, capacity, cost;
  40.             in.nextToken();
  41.             from = (int) in.nval;
  42.             in.nextToken();
  43.             to = (int) in.nval;
  44.             in.nextToken();
  45.             capacity = (int) in.nval;
  46.             in.nextToken();
  47.             cost = (int) in.nval;
  48.             addEgde(from, to, capacity, cost);
  49.         }
  50.         int ans = minCostFlow(src, dst, 50);
  51.         out.println(ans);
  52.         out.flush();
  53.     }
  55.     private static void init() {
  56.         graph = new ArrayList<List<Edge>>(V);
  57.         for (int i = 0; i < V; ++i) {
  58.             graph.add(new ArrayList<Edge>());
  59.         }
  60.         h = new int[V];
  61.         dist = new int[V];
  62.         prevV = new int[V];
  63.         prevE = new int[V];
  64.     }
  66.     // 向图中增加一条从from到to的容量为cap费用为cost的边
  67.     private static void addEgde(int from, int to, int cap, int cost) {
  68.         graph.get(from).add(new Edge(to, cap, cost, graph.get(to).size()));
  69.         graph.get(to).add(new Edge(from, 0, -cost, graph.get(from).size() - 1));
  70.     }
  72.     // 求解从s到t流量为f的最小费用流，如果没有流量为f的流，则返回-1
  73.     private static int minCostFlow(final int src, final int dst, int flow) {
  74.         int res = 0;
  75.         Arrays.fill(h, 0);
  77.         while (flow > 0) {
  78.             // 使用Dijkstra算法更新h
  79.             Arrays.fill(dist, Integer.MAX_VALUE);
  80.             dist[src] = 0;
  82.             // int[0]存储最短距离
  83.             // int[1]存储结点编号
  84.             // 建立小根堆
  85.             Comparator<int[]> comparator = new Comparator<int[]>() {
  86.                 public int compare(int[] o1, int[] o2) {
  87.                     return o1[0] - o2[0];
  88.                 }
  89.             };
  90.             Queue<int[]> queue = new PriorityQueue<int[]>(comparator);
  91.             queue.offer(new int[]{0, src});
  93.             while (!queue.isEmpty()) {
  94.                 int[] pair = queue.poll();
  95.                 int v = pair[1];
  96.                 if (dist[v] < pair[0]) {
  97.                     continue;
  98.                 }
  99.                 for (int i = 0; i < graph.get(v).size(); ++i) {
  100.                     Edge edge = graph.get(v).get(i);
  101.                     if ((edge.capacity > 0) && (dist[edge.to] > dist[v] + edge.cost + h[v] - h[edge.to])) {
  102.                         dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to];
  103.                         prevV[edge.to] = v;
  104.                         prevE[edge.to] = i;
  105.                         queue.offer(new int[]{dist[edge.to], edge.to});
  106.                     }
  107.                 }
  108.             }
  110.             // 不能再增广
  111.             if (dist[dst] == Integer.MAX_VALUE) {
  112.                 return -1;
  113.             }
  115.             for (int v = 0; v < V; ++v) {
  116.                 h[v] += dist[v];
  117.             }
  119.             // 找到路径上容量最小的边
  120.             int minCapacity = Integer.MAX_VALUE;
  121.             for (int v = dst; v != src; v = prevV[v]) {
  122.                 minCapacity = Math.min(minCapacity, graph.get(prevV[v]).get(prevE[v]).capacity);
  123.             }
  125.             // 沿s到t的最短路尽量增广
  126.             // 计算残差网络
  127.             flow -= minCapacity;
  128.             res += minCapacity * h[dst];
  129.             for (int v = dst; v != src; v = prevV[v]) {
  130.                 Edge e = graph.get(prevV[v]).get(prevE[v]);
  131.                 e.capacity -= minCapacity;
  132.                 graph.get(v).get(e.reserve).capacity += minCapacity;
  133.             }
  134.         }
  135.         return res;
  136.     }
  137. }
  139. class Edge {
  140.     int to;
  141.     int capacity;
  142.     int cost;
  143.     int reserve;
  145.     public Edge(int to, int capacity, int cost, int reserve) {
  146.         this.to = to;
  147.         this.capacity = capacity;
  148.         this.cost = cost;
  149.         this.reserve = reserve;
  150.     }
  151. }

样例输入

  1. 4 5 4 3
  2. 4 2 30 2
  3. 4 3 20 3
  4. 2 3 20 1
  5. 2 1 30 9
  6. 1 3 40 5

样例输出

  1. 280