max flow


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

  • 辺クラス
    class Edge {
    	int to;
    	int cap;
    	int rev;
    	Edge(int to, int cost, int rev) {
    		this.to = to;
    		this.cap = cost;
    		this.rev = rev;
    	}
    }
  • Ford-Fulkerson法(隣接リスト)
    final int INF = Integer.MAX_VALUE/2;
    List<Edge>[] list;
    boolean[] used;
     
    void addEdge(int from, int to, int cap) {
    	list[from].add(new Edge(to, cap,list[to].size()));
    	list[to].add(new Edge(from, 0, list[from].size()-1));
    }
     
    int dfs(int v, int t, int f) {
    	if (v == t) return f;
    	used[v] = true;
    	for (int i = 0; i < list[v].size(); i++) {
    		Edge e = list[v].get(i);
    		if (!used[e.to] && e.cap > 0) {
    			int d = dfs(e.to, t, Math.min(f, e.cap));
    			if (d > 0) {
    				e.cap -= d;
    				list[e.to].get(e.rev).cap += d;
    				return d;
    			}
    		}
    	}
    	return 0;
    }
     
    int ford_fulkerson(int s, int t) {
    	int flow = 0;
    	while (true) {
    		Arrays.fill(used, false);
    		int f = dfs(s, t, INF);
    		if (f == 0) return flow;
    		flow += f;
    	}
    }