Finding All Permutations of a given String

Problem: Find all permutations of a given string and display them in lexicographically increasing order.

GFG Link: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

GFG Practice Link: https://practice.geeksforgeeks.org/problems/permutations-of-a-given-string/0

My Solution:

1. Use recursion to get the strings.
2. Use a TreeMap to get order.

Java:


Time Complexity:
O(n * n!) not considering the time for lexicographical sort.

Rod Cutting Problem

Problem Statement: Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6).

GFG Link: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/

Practice Link: https://practice.geeksforgeeks.org/problems/rod-cutting/0

Solution:

Getting postorder traversal of a binary tree from inorder and preorder traversal

Problem Statement: Given inorder and preorder traversal of a binary tree, find its postorder traversal.

GFG Link : https://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/

Solution:

Matrix Chain Multiplication

Problem Statement: Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications. There are many options to multiply a chain of matrices because matrix multiplication is associative i.e. no matter how one parenthesize the product, the result will be the same.

GfG Link : https://practice.geeksforgeeks.org/problems/matrix-chain-multiplication/0

Solution:

Similar to Parenthesization DP http://www.codebytes.in/2019/01/parenthesization-dp-problem.html

Shortest Common Supersequence

Problem Statement : https://www.geeksforgeeks.org/shortest-common-supersequence/

Solution:

Printing the Longest Common Subsequence

Problem Statement: Given two strings, print their longest common subsequence.

GFG Link : https://www.geeksforgeeks.org/printing-longest-common-subsequence/

Solution:

Output:

1
AGGTAB GXTXAYB

4 3 3 2 2 0 0 
4 3 3 2 2 1 1 
0 3 3 2 2 1 1 
0 3 3 2 2 1 1 
0 2 2 2 2 1 1 
0 1 1 1 1 1 1 

len = 4
0, 0
1, 0
2, 1
2, 2
3, 2
4, 3
4, 4
5, 5
5, 6
GTAB

Parenthesization DP Problem

Problem Statement : https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/

Solution (Bottom-Up DP):

01 Knapsack Problem

Problem Statement:

Source : https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

Solution:

Maximum sum path in matrix

Problem statement : Given a N X N  matrix Matrix[N][N] of positive integers.  There are only three possible moves from a cell Matrix[r][c].

1. Matrix[r+1][c]

2. Matrix[r+1][c-1]

3. Matrix[r+1][c+1]

Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.

GeeksForGeeks link : https://practice.geeksforgeeks.org/problems/path-in-matrix/0

Algorithm : DP

Solution:

Ways to cover distance, DP

Problem Statement (https://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/):

Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.

Examples :

Input:  n = 3
Output: 4

Below are the four ways
 1 step + 1 step + 1 step
 1 step + 2 step
 2 step + 1 step
 3 step

Input:  n = 4
Output: 7

Explanation:

If we know the number of ways to reach the distances k-3, k-2, k-1, then the kth distance is just 3, 2 and 1 hops away respectively. So dp[k] = dp[k-3] + dp[k-2] + dp[k-1]

Code:

Minimum Sum Partition Problem

Statement: Given an array, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

Geeksforgeeks problem link : https://practice.geeksforgeeks.org/problems/minimum-sum-partition/0

Solution Explanation:

Simple recursive solution might be :

From index 0 start including each element into either of the partitions and recurse for the next index.
This is exponential complexity O(2^n)

What we can do is start from index 0. We either include it in first or second partition. For next index in the function call we include weight of first and second partition. When it reaches the end index it has a certain first partition and second partition sum and returns the difference between them. The indices previous to this receive the difference as return value and check to see if including the current index to the first or second partition gives overall less difference at the last index, given the current weight supplied by previous index.

A particular function call state is defined by the sum of first/second partition elements and the index we are seeing.

solve(int index, int firstPartitionSum, int secondPartitionSum)

DP[Index][FirstPartitionSum]

Code:

Minimum String Edit Distance DP Problem

Problem Statement : [SPOJ EDIST]

You are given two strings, A and B. Answer, what is the smallest number of operations you need to
transform A to B?

Operations are:

Delete one letter from one of strings
Insert one letter into one of strings
Replace one of letters from one of strings with another letter

Algorithm :

DP[str1.length][str2.length]

At each point pair (x, y) (x index in string 1 and y index in string 2), you either have matching values in strings or dont.

If you have matching values, you can proceed to x+1, y+1.

Otherwise, you have 3 choices:

1. Delete 1 letter from first string
2. Insert 1 letter to first string
3. Replace 1 letter to match second string

Each operation adds 1 to the cost of making strings equal.

if (str1[i] == str2[j])
return dp[i][j] = solve(i + 1, j + 1);
else return dp[i][j] = 1 + Math.min(Math.min(solve(i + 1, j), solve(i, j + 1)), solve(i + 1, j + 1));

Code:

Longest Common Subsequence

Longest common subsequence is a classic DP problem.

Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Solution:

1. Use DP:

Array : dp[first.length][second.length]
Function: compute(int x, int y)

A dp array of size DP[length(first)][length(second)] stores the state of the current computation.

At every function call compute(x, y) we are considering matching the char at xth index of first string with yth index of second string. If it matches we add 1 to the length of subsequence.

If it does not match, we have to skip it. We do so by just returning the value of sebsequent index matches:

skip current xth index in first string:
compute(x+1, y)

skip current yth index in second string:
compute(x, y+1)

Each of these calls return the max subsequence length  starting at their supplied indices.

At current x,y configuration since the characters don't match we consider max return value among these 2 calls and assign the current dp[x][y] state to this value. So subsequent calls to this function compute(x, y) return dp[x][y] value.

This is equivalent to saying that we have already computed what is the max common subsequence length is we start from x in first string and y in second string so just take the value and don't compute again.

This way we avoid a lot of unnecessary computation.

Time complexity:

O(MN)

where M = length(string1) N = length(string2)

For each x we match every y. Since results are stored in dp[][] we don't do the matching for particular x and y more than once.

Practice Problem SPOJ : EELCS

Code:

Loop Detection in a Linked List

Problem Statement: Given a linked list head pointer, you need to output 1 if the list contains a loop or 0 if it doesn't.

This is two pointer approach. You can also solve this using a HashSet of node addresses to see if same node address appeared again or not.

Function:

Decimal to Hex Conversion

Converting decimal to hexadecimal numbers.

Codechef problem link : https://www.codechef.com/problems/HEX

Solution:

SPOJ BTCODE_H (Maths) Solution - Java

Test Case given-

N = 2, K = 2.

# of words containing only 0 and 1 that are of length 2 -> 4

00
01
10
11

Now insertion of words may happen as:

00 00                      
00 01           01 00
00 10           10 00
00 11           11 00

01 01      
01 10           10 01
01 11           11 01

10 10
10 11           11 10

11 11

Total # cases -> 16.

# cases where trie has 3 nodes = 4
                                4 nodes = 4
                                5 nodes = 8

Expected value of the number of nodes ->

(3*4 + 4*4 + 5*8)                                    68
----------------------         =             ---------------------             =              4.25
          16                                                16

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class BTCODE_HSimple {
    
    //Exponentiation by Repeated Sqauring
    public static double power(double a, int b){
        if(b==0)return 1;
        if(b==1)return a;
        if(b%2==1){
            return a*power(a*a, (b-1)/2);
        }else return power(a*a, b/2);
    }
    
    public static void main(String[] args){
        int n = IO.nextInt(); 
        while(n-->0){
            int N = IO.nextInt();
            int K = IO.nextInt();
            double ans = 1;
            for(int i=1;i<=K;++i){
                double p = power(0.5, i); 
                ans += 1;
                double op = 1-p; 
                for(int j=1;j<N;++j){ 
                    ans += power(op, j);
                } 
            }
            System.out.printf("%.2f\n", ans);
        }
    }



    /**************************************IO**************************************/
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

TAP2012D SPOJ (Trie with HashMaps) solution Java

You need to put all the names first and second team players in the same trie. If your logic involves putting the names of team1 into trie and then using team2 player names, you're likely to get WAs. For eg. changing the order of queries for team2 names will get you different answers in some cases.

Check out these test cases:-

5
H HE HER HEREB HEREBY
HEREBY HEREB HERE HER HE

7
THIS IS JUST A SE NT ENCE
SENTTH IS JU SIS AS SE THUS

Check out my solution if you're still stuck.

Source:

import java.io.*;
import java.util.*;
 
class Node{
    HashMap<Character, Integer> children;
    int first =  0;
    int second = 0; 
     
    Node(){
        children = new HashMap<>();  
    }
    
    void init(){
        children.clear(); 
        first = 0;
        second = 0; 
    }
}

class TrieMap {
    static final int MAX = 500000; 
    static int gIndex;
    static Node trie[]; 
    static int count=0;
    
    public static void insert(String s, int type){  
        int cIndex = 0;
      
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i); 
            Integer nIndex = trie[cIndex].children.get(c); 
            if(nIndex==null){ 
                    trie[cIndex].children.put(c, ++gIndex);  
                    if(trie[gIndex]==null)trie[gIndex] = new Node(); 
                    trie[gIndex].init();
                    cIndex = gIndex; 
                    nIndex = cIndex;  
            }else{
                cIndex = nIndex;  
            }
            
            if(type==1)trie[nIndex].first++; 
            else       trie[nIndex].second++;
        }  
    } 
    
    static int ans=0;
    public static int query(int cIndex, int depth){  
        
        int sub = 0;
        for(Map.Entry<Character, Integer> me:trie[cIndex].children.entrySet()){ 
            int value = me.getValue();
            
            if(trie[value].first>0 && trie[value].second>0){
                int r = query(value, depth+1);
                sub+=r;
                trie[cIndex].first -= r;
                trie[cIndex].second -= r;
            }
        } 
        int min  = Math.min(trie[cIndex].first, trie[cIndex].second); 
        if(cIndex!=0)ans+=depth*min; 
        return min+sub;
    } 
    
    public static void main(String[] args){
          
        trie = new Node[MAX];  
        
        while(true){ 
            int n = IO.nextInt();
            if(n==-1)return;
            trie[0] = new Node();
            trie[0].init();  
            count=0;
            gIndex = 0;
            for(int i=0;i<n;++i){
                String s = IO.nextString(); 
                insert(s, 1);
            } 
            ans=0; 
            for(int i=0;i<n;++i){  
                insert(IO.nextString(), 2);  
            }   
            query(0, 0);
            IO.println(ans);
        }
    }
    




    /***********************************IO***************************************/
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

LEONARDO SPOJ (Implementation) Solution - JAVA

Algorithm :-

1. Odd length cycles are OK.
2. The graph should have two even length cycles of the same length if even cycles exist. (There may be multiple even cycles).
3. Self loops are OK.

Point #2:

Consider an alphabet having only 6 letters i.e. ABCDEF. Now we have to apply the same permutation twice to get "CDEABF". The permutation we apply is "BCDAEF". Applying it twice (steps):-

|--->CDABEF
P
|--->BCDAEF
P
|----ABCDEF

Where P stands for the application of the permutation "BCDAEF". Now if we only consider the final alphabet string and the original one,

CDABEF

ABCDEF

Notice our even length cycle "BCDA" has split up into two even cycles of equal length. (CA and DB).

You can similarly figure out that odd length cycles remain odd length cycles and of course, self loops have no effect.

Self loops:

There are two self loops in the above example E-E and F-F.

Now just write code to check whether there are even number of even length cycles. If this is the case, the answer is yes, otherwise no.

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class LEONARDO { 
    
    public static void main(String[] args){
        int n = IO.nextInt();
        String REF = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        while(n-->0){
            String s = IO.nextString();
            
            int[] pos = new int[256];
          
            for(int i=0;i<s.length();++i){
                pos[s.charAt(i)] = i;
            }
            
            boolean m[] = new boolean[256]; 
            
            int cyclesReg[] = new int[26]; 
            for(int i=0;i<s.length();++i){
                char c = s.charAt(i); 
                boolean f = false;
                int length =0 ;
                while(!m[c]){  
                    f = true;
                    length++;
                    m[c] = true;
                    int p = pos[c];
                    c = REF.charAt(p);
                } 
                if(f){ 
                    cyclesReg[length]++;
                }
            }
             
            boolean f = true;
            for(int i=0;i<cyclesReg.length;++i){
                if(i%2==0 && cyclesReg[i]%2!=0){f =  false;break;}
            }
            if(f)IO.println("Yes");
            else IO.println("No");
        }
    }
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

EN - SPOJ (DFS) Solution - JAVA

Algorithm:

1. Find any path form source to sink (DFS/BFS). It is given that a path exists.
2. Now from the beginning node of this path,

             remove the current node from graph (set it visited).
             check if the path still exists.
             If it doesn't, the removed vertex is what you want.
             else check the same for the next node in the path until
             sink.
   
 
Source:

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException; 

public class EN2 {  
    int maxnodes, maxedges, src, dest, edges;
    int[] top, head, prev;
    boolean marked;
    
    public void init(int maxnodes, int maxedges){
        this.maxnodes = maxnodes;
        this.maxedges = maxedges;  
        head = new int[maxedges];
        prev = new int[maxedges]; 
        top = new int[maxnodes];
        clear();
    }
    
    public void clear(){ 
        Arrays.fill(top, -1);
        edges = 0;
    } 
    
    public void addEdge(int u, int v, int capacity){
        head[edges] = v; 
        prev[edges] = top[u];
        top[u] = edges++;  
    }
    
     
    boolean dfs(int u){ 
        if(rec[u])return false;
        rec[u] = true;
         
        boolean sig=false;
        for(int e=top[u]; e>=0;e = prev[e]){
            int v = head[e];   
            from[v] = u;
            if(v==dest){from[dest] = u;return true;}
            sig = (dfs(v)==true);  
            if(sig)return sig;
        } 
        return sig;
    }
    
    int checkNodes(int u, int s, int t){  
        if(u==s)return -1; 
        int r = checkNodes(from[u], s, t);
        if(r!=-1)return r;
        Arrays.fill(rec, false);
        rec[u] = true;
        if(!dfs(s))return u;else return -1;
    }
     
    static boolean rec[];
    static int from[]; 
    public static void main(String[] args){
        int nC = IO.nextInt(); 
        
        EN2 instance = new EN2(); 
        
        //Input contains cases when m>100011. So a large value for m.
        instance.init((30011), 999999*2);
        
        while(nC-->0){  
            instance.clear(); 
            
            int n = IO.nextInt()-1;  
            
            rec = new boolean[n+1]; 
            from = new int[n+1];
            
            Arrays.fill(from, -1);
            instance.src = 0;
            instance.dest = n;
            
            int m = IO.nextInt(); 
            for(int i=0;i<m;++i){
                int a = IO.nextInt()-1;
                int b = IO.nextInt()-1; 
                instance.addEdge(a, b, 1); 
            }
            instance.dfs(0);
            int ret = instance.checkNodes(n, 0, n);
            IO.println(ret==-1?(n+1):(ret+1)); 
        }
        
    }  
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

FASTFLOW SPOJ (Maxflow Dinic's Algorithm) Solution JAVA

Algorithm : Dinic's Fastflow

Source :

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class FASTFLOW {
    static final int INF = 0x7fffffff;
    int maxnodes, maxedges, src, dest, edges;
    int[] top, work, Q;
    int[] head, prev, flow, cap, dist;
    boolean marked;

    public void init(int maxnodes, int maxedges) {
        this.maxnodes = maxnodes;
        this.maxedges = maxedges;
        top = new int[maxnodes];
        work = new int[maxnodes];
        Q = new int[maxnodes];
        dist = new int[maxnodes];

        head = new int[maxedges];
        prev = new int[maxedges];

        flow = new int[maxedges];
        cap = new int[maxedges];

        clear();
    }

    public void clear() {
        Arrays.fill(top, -1);
        edges = 0;
    }

    public void addEdge(int u, int v, int capacity) {
        head[edges] = v;
        cap[edges] = capacity;
        flow[edges] = 0;
        prev[edges] = top[u];
        top[u] = edges++;
         
        head[edges] = u;
        cap[edges] = 0;
        flow[edges] = 0;
        prev[edges] = top[v];
        top[v] = edges++;
    }

    boolean dinic_bfs() {
        Arrays.fill(dist, -1);
        dist[src] = 0;
        int sizeQ = 0;
        Q[sizeQ++] = src;
        for (int i = 0; i < sizeQ; ++i) {
            int u = Q[i];
            for (int e = top[u]; e >= 0; e = prev[e]) {
                int v = head[e];
                if (flow[e] < cap[e] && dist[v] < 0) {
                    dist[v] = dist[u] + 1;
                    Q[sizeQ++] = v;
                }
            }
        }
        return dist[dest] >= 0;
    }

    int dinic_dfs(int u, int f) {
        if (u == dest) {
            return f;
        }
        for (int e = work[u]; e >= 0; work[u] = e = prev[e]) {
            int v = head[e];
            if (flow[e] < cap[e] && dist[v] == dist[u] + 1) {
                int df = dinic_dfs(v, Math.min(f, cap[e] - flow[e]));
                if (df > 0) {
                    flow[e] += df;
                    flow[e^1] -= df;
                    return df;
                }
            }
        }
        return 0;
    }

    public double maxFlow(int src, int dest) {
        this.src = src;
        this.dest = dest;
        double flow = 0;
        while (dinic_bfs()) {
            System.arraycopy(top, 0, work, 0, maxnodes);
            while (true) {
                int df = dinic_dfs(src, INF);
                if (df == 0) {
                    break;
                }
                flow += df;
            }
        }
        return flow;
    }
     
    
    public static void main(String[] args){ 
        FASTFLOW instance = new FASTFLOW();
        
        
        int N, M;
        N = IO.nextInt();
        M = IO.nextInt(); 
        instance.init(N, M*4); 
        int sourceI = 0, sinkI = N-1; 

        for(int i=0;i<M;++i){
            int x, y, c;
            x = IO.nextInt()-1;
            y = IO.nextInt()-1; 
            c = IO.nextInt(); 

            if(x==y)continue;

            instance.addEdge(x, y, c);
            instance.addEdge(y, x, c);
        }


        System.out.printf("%.0f\n", (instance.maxFlow(sourceI, sinkI))); 
    }
    
    private static class IO {

        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars;

        private static int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public static int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public static char nextChar() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) c;
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private static void println(Object... a) {
            for (Object o : a) {
                System.out.print(o);
            }
            System.out.println();
        }
    }
}