minimum cost flow


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

  • 辺クラス
    class Edge {
    	int to, cap, cost, rev;
    	Edge(int to, int cap, int cost, int rev) {
    		this.to = to;
    		this.cap = cap;
    		this.cost = cost;
    		this.rev = rev;
    	}
    }
  • 最小費用流(Bellman-Ford)
    final int INF = Integer.MAX_VALUE/2;
    List<Edge>[] list;
    int[] d;
    int[] prevv, preve;
     
    void addEdge(int from, int to, int cap, int cost) {
    	list[from].add(new Edge(to, cap, cost,list[to].size()));
    	list[to].add(new Edge(from, 0, -cost, list[from].size()-1));
    }
     
    int min_cost_flow(int s, int t , int f) {
    	int n = list.length;
    	d = new int[n];
    	prevv = new int[n]; preve = new int[n];
    	int res = 0;
    	while (f > 0) {
    		Arrays.fill(d, INF);
    		d[s] = 0;
    		boolean update = true;
    		while (update) {
    			update = false;
    			for (int v = 0; v < n; v++) {
    				if (d[v] == INF) continue;
    				for (int i = 0; i < list[v].size(); i++) {
    					Edge e = list[v].get(i);
    					if (e.cap > 0 && d[e.to] > d[v] + e.cost) {
    						d[e.to] = d[v] + e.cost;
    						prevv[e.to] = v;
    						preve[e.to] = i;
    						update = true;
    					}
    				}
    			}
    		}
     
    		if (d[t] == INF) return -1;
     
    		int c = f;
    		for (int v = t; v != s; v = prevv[v]) {
    			c = Math.min(c, list[prevv[v]].get(preve[v]).cap);
    		}
    		f -= c;
    		res += c * d[t];
    		for (int v = t; v != s; v = prevv[v]) {
    			Edge e = list[prevv[v]].get(preve[v]);
    			e.cap -= c;
    			list[v].get(e.rev).cap += c;
    		}
    	}
     
    	return res;
    }