Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Dinnic {
- FastScanner in;
- PrintWriter out;
- class Edge {
- int fr, to;
- int cost;
- int flow;
- Edge backEdge;
- public Edge(int fr, int to, int cost) {
- super();
- this.fr = fr;
- this.to = to;
- this.cost = cost;
- flow = 0;
- }
- }
- ArrayList<Edge>[] g;
- int[] d;
- int[] last;
- int n;
- boolean bfs() {
- Arrays.fill(d, -1);
- ArrayList<Integer> queue = new ArrayList<Integer>();
- int it = 0;
- queue.add(0);
- d[0] = 0;
- while (it < queue.size()) {
- int v = queue.get(it);
- for (Edge e : g[v]) {
- if (d[e.to] == -1 && e.flow < e.cost) {
- d[e.to] = d[v] + 1;
- queue.add(e.to);
- }
- }
- it++;
- }
- return d[n - 1] != -1;
- }
- int dfs(int v, int flow) {
- if (flow == 0 || v == n - 1) return flow;
- for (; last[v] < g[v].size(); last[v]++) {
- Edge e = g[v].get(last[v]);
- if (d[e.to] != d[v] + 1) continue;
- int pushed = dfs(e.to, Math.min(flow, e.cost - e.flow));
- if (pushed != 0) {
- e.flow += pushed;
- e.backEdge.flow -= pushed;
- return pushed;
- }
- }
- return 0;
- }
- void solve() {
- n = in.nextInt();
- int m = in.nextInt();
- g = new ArrayList[n];
- for (int i = 0; i < n; i++)
- g[i] = new ArrayList<Edge>();
- for (int i = 0; i < m; i++) {
- int fr = in.nextInt() - 1;
- int to = in.nextInt() - 1;
- int cost = in.nextInt();
- Edge e1 = new Edge(fr, to, cost);
- Edge e2 = new Edge(to, fr, 0);
- e1.backEdge = e2;
- e2.backEdge = e1;
- g[fr].add(e1);
- g[to].add(e2);
- }
- d = new int[n];
- last = new int[n];
- int flow = 0;
- while (bfs()) {
- while (true) {
- Arrays.fill(last, 0);
- int add = dfs(0, Integer.MAX_VALUE);
- if (add == 0) break;
- flow += add;
- }
- }
- out.println(flow);
- }
- void run() {
- try {
- in = new FastScanner(new File("maxflow.in"));
- out = new PrintWriter(new File("maxflow.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- public static void main(String[] args) {
- new Dinnic().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement