Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Decomposition {
- FastScanner in;
- PrintWriter out;
- class Edge {
- int fr, to;
- int cost;
- int id;
- int flow;
- Edge backEdge;
- public Edge(int fr, int to, int cost, int id) {
- super();
- this.fr = fr;
- this.to = to;
- this.cost = cost;
- this.id = id;
- }
- }
- 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;
- }
- long dfs(int v, long 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;
- long 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;
- }
- boolean[] was;
- ArrayList<Long> tmp = new ArrayList<Long>();
- long dfs2(int v, long flow) {
- if (v == n - 1)
- return flow;
- was[v] = true;
- for (Edge e : g[v]) {
- if (e.flow > 0 && !was[e.to]) {
- tmp.add((long) e.id);
- long pushed = dfs2(e.to, Math.min(flow, e.flow));
- e.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, i + 1);
- Edge e2 = new Edge(to, fr, 0, i + 1);
- e1.backEdge = e2;
- e2.backEdge = e1;
- g[fr].add(e1);
- g[to].add(e2);
- }
- d = new int[n];
- last = new int[n];
- while (bfs()) {
- while (true) {
- Arrays.fill(last, 0);
- long add = dfs(0, Long.MAX_VALUE);
- if (add == 0)
- break;
- }
- }
- ArrayList<ArrayList<Long>> ans = new ArrayList<ArrayList<Long>>();
- was = new boolean[n];
- while (true) {
- tmp = new ArrayList<Long>();
- Arrays.fill(was, false);
- long add = dfs2(0, Long.MAX_VALUE);
- if (add == 0)
- break;
- ans.add(tmp);
- tmp.add(add);
- }
- out.println(ans.size());
- for (int i = 0; i < ans.size(); i++) {
- out.print(ans.get(i).get(ans.get(i).size() - 1) + " "
- + (ans.get(i).size() - 1) + " ");
- for (int j = 0; j < ans.get(i).size() - 1; j++)
- out.print(ans.get(i).get(j) + " ");
- out.println();
- }
- }
- void run() {
- try {
- in = new FastScanner(new File("decomposition.in"));
- out = new PrintWriter(new File("decomposition.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 Decomposition().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement