AlgorithmDatastruct – 禁绝边境线

[Project]JpegDecoder DHT to Huffman Code Part

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2017年2月20日 | Comments 0 Comment

//DHT PART

        static List<DHTCode> DHTReader()
        {
            int LengthDHT = OriginPicture.ReadByte() * 0xFF + OriginPicture.ReadByte();
            int TableNo = OriginPicture.ReadByte();
            int[] L = new int[16];
            int LengthV = 0;
            for (int i = 0; i < 16; i++)
            {
                L[i] = OriginPicture.ReadByte();
                LengthV += L[i];
            }
            int[] V = new int[LengthV];
            for (int i = 0; i < LengthV; i++)
            {
                V[i] = OriginPicture.ReadByte();
            }
            List<DHTCode> DHTCodeCollection = new List<DHTCode>();
            //if (L[0] == 0) DHTCodeCollection[0] = new DHTCode(1, 1, "0", V[0]);
            //else DHTCodeCollection[0] = new DHTCode(0, 2, "00", V[0]);
            string PrevCode = "";
            int FirstI = 0;
            int CurrDHT = 0;
            for (int i = 0; i < 16; i++)
            {
                if (L[i] != 0)
                {
                    for (int j = 0; j < L[i]; j++)
                    {
                        if (PrevCode=="")
                        {
                            string C = "";
                            for (int Cont = 0; Cont <= i; Cont++)
                            {
                                C += '0';
                            }
                            PrevCode = C;
                            DHTCodeCollection.Add(new DHTCode(CurrDHT, C.Length, C, V[CurrDHT]));
                            CurrDHT++;
                        }
                        else
                        {
                            string C = PrevCode;
                            int Prev = Convert.ToInt32(C, 2);
                            Prev++;
                            C = Convert.ToString(Prev, 2);
                            Prev = PrevCode.Length - C.Length;
                            for (int Set = 0; Set < Prev; Set++)
                            {
                                C = "0" + C;
                            }
                            DHTCodeCollection.Add(new DHTCode(CurrDHT, C.Length, C, V[CurrDHT]));
                            CurrDHT++;
                            PrevCode = C;
                        }
                    }
                    FirstI = i;
                    break;
                }
            }
            for (int i = FirstI + 1; i < 16; i++)
            {
                for (int j = 0; j < L[i]; j++)
                {
                    string C = PrevCode;
                    int Prev = Convert.ToInt32(C, 2);
                    Prev++;
                    C = Convert.ToString(Prev, 2);
                    Prev = PrevCode.Length - C.Length;
                    for (int Set = 0; Set < Prev; Set++)
                    {
                        C = "0" + C;
                    }
                    Prev = i - C.Length + 1;
                    for (int Set = 0; Set < Prev; Set++)
                    {
                        C = C + "0";
                    }
                    DHTCodeCollection.Add(new DHTCode(CurrDHT, C.Length, C, V[CurrDHT]));
                    CurrDHT++;
                    PrevCode = C;
                }
            }
            return DHTCodeCollection;
        }
    }

[C#]Make Heap

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2017年2月13日 | Comments 0 Comment

写的略蠢……把一个数组转成堆的形式

    public class Heap
    {
        public HeapNode Root = new HeapNode();
        public void Heapify(HeapNode CurrNode)
        {
            int Select = 0;//0:Curr 1:Right 2:Left
            if ((CurrNode.L != null && CurrNode.Value > CurrNode.L.Value) && ((CurrNode.R != null && CurrNode.Value > CurrNode.R.Value) || (CurrNode.R == null))) Select = 0;
            else if (CurrNode.L != null && CurrNode.Value > CurrNode.L.Value) Select = 1;
            else if (CurrNode.R != null) Select = 2;
            if (Select == 1)
            {
                int temp = CurrNode.Value;
                CurrNode.Value = CurrNode.R.Value;
                CurrNode.R.Value = temp;
                Heapify(CurrNode.R);
            }
            if (Select == 2)
            {
                int temp = CurrNode.Value;
                CurrNode.Value = CurrNode.L.Value;
                CurrNode.L.Value = temp;
                Heapify(CurrNode.L);
            }
        }
        public void MakeHeap(HeapNode CurrNode)
        {
            if (CurrNode.L != null) MakeHeap(CurrNode.L);
            if (CurrNode.R != null) MakeHeap(CurrNode.R);
            Heapify(CurrNode);
        }
        public HeapNode IntData(int[] a, int CurrPos)
        {
            HeapNode Node = new HeapNode();
            if (a.Length < CurrPos + 1) return null;
            Node.Value = a[CurrPos];
            Node.L = IntData(a, (CurrPos + 1) * 2 - 1);
            Node.R = IntData(a, (CurrPos + 1) * 2);
            return Node;
        }
        public Heap(int[] a)
        {
            Root = IntData(a, 0);
            MakeHeap(Root);
        }
    }

[C#]Queue

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2017年1月25日 | Comments 0 Comment

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Lite_STL_Sharp
{
    public class Queue<T>
    {
        Exception NullTopEx = new Exception("Null queue");
        public int Length
        {
            get;
            private set;
        }
        private QueueNode<T> Head;
        public Queue()
        {
            Head = null;
            Length = 0;
        }
        public void Push(T data)
        {
            QueueNode<T> newNode = new QueueNode<T>(data);
            QueueNode<T> t = Head;
            if (t == null)
            {
                Head = newNode;
                Length += 1;
                return;
            }
            while (t.Next != null)
            {
                t = t.Next;
            }
            t.Next = newNode;
            Length += 1;
        }
        public void Pop()
        {
            if (Head == null)
            {
                throw NullTopEx;
            }
            Head = Head.Next;
            Length -= 1;
        }
        public T GetFront()
        {
            if (Head == null)
            {
                throw NullTopEx;
            }
            return Head.Data;
        }
        public int GetLength()
        {
            QueueNode<T> t = Head;
            int len = 0;
            while (t != null)
            {
                ++len;
                t = t.Next;
            }
            return len;
        }
        public void Clear()
        {
            Head = null;
            Length = 0;
        }
    }
    public class QueueNode<T>
    {
        public T Data;
        public QueueNode<T> Next;
        public QueueNode()
        {
            Data = default(T);
            Next = null;
        }
        public QueueNode(T data)
        {
            Data = data;
            Next = null;
        }
        public QueueNode(QueueNode<T> next)
        {
            Data = default(T);
            Next = next;
        }
        public QueueNode(T data, QueueNode<T> next)
        {
            Data = data;
            Next = next;
        }
    }
}

[C#]二叉树前序遍历中序遍历求后序遍历

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2017年1月20日 | Comments 0 Comment

基础算法题，主要是递归
http://hihocoder.com/problemset/problem/1049

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HIHOCODER_WEEK010
{
    class Program
    {
        static void Main(string[] args)
        {
            string fstOrder = Console.ReadLine();
            string midOrder = Console.ReadLine();
            Node root = solve(fstOrder, midOrder);
            lstOrder(root);
        }
        static Node solve(string fstOrder,string midOrder)
        {
            if (fstOrder.Length == 1 && midOrder.Length == 1)
            {
                Node newNode = new Node(fstOrder[0]);
                return newNode;
            }
            char Mid = fstOrder[0];
            string newMidOrderL = midOrder.Split(Mid)[0];
            string newMidOrderR = midOrder.Split(Mid)[1];
            string newFstOrderL = fstOrder.Substring(1, newMidOrderL.Length);
            string newFstOrderR = fstOrder.Substring(newMidOrderL.Length + 1, newMidOrderR.Length);
            Node node = new Node(Mid);
            Node nodeL = new Node(), nodeR = new Node();
            if (newFstOrderL.Length!=0)
            {
                nodeL = solve(newFstOrderL, newMidOrderL);
            }
            if (newFstOrderR.Length!=0)
            {
                nodeR = solve(newFstOrderR, newMidOrderR);
            }
            node.L = nodeL;
            node.R = nodeR;
            return node;
        }
        static void lstOrder(Node root)
        {
            if (root.L != null) lstOrder(root.L);
            if (root.R != null) lstOrder(root.R);
            if (root.value != '\0') Console.Write(root.value);
        }
    }
    public class Node
    {
        public char value;
        public Node L;
        public Node R;
        public Node()
        {
            value = '\0';
            L = null;
            R = null;
        }
        public Node(char c)
        {
            value = c;
            L = null;
            R = null;
        }
    }
}

Decision Tree – ID3算法 (editing)

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2016年12月21日 | Comments 0 Comment

1.决策树概念
机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。
从数据产生决策树的机器学习技术叫做决策树学习,通俗说就是决策树。[Wikipedia]
所以在我的理解中，决策树就是由一定数据生成的一棵树，这棵树包含了由数据中各种关系产生的判断条件。我们可以通过另外一组数据，通过这些判断条件来推测出我们所需要的值。
举一个经典的例子：打网球。
+—–+———-+————-+———-+——-+——+
| DAY | OUTLOOK | TEMPERATURE | HUMIDITY | WINDY | PLAY |
+—–+———-+————-+———-+——-+——+
| 1 | SUNNY | 85 | 85 | FALSE | NO |
+—–+———-+————-+———-+——-+——+
| 2 | SUNNY | 80 | 90 | TRUE | NO |
+—–+———-+————-+———-+——-+——+
| 3 | OVERCAST | 83 | 78 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 4 | RAIN | 70 | 96 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 5 | RAIN | 68 | 80 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 6 | RAIN | 65 | 70 | TRUE | NO |
+—–+———-+————-+———-+——-+——+
| 7 | OVERCAST | 64 | 65 | TRUE | YES |
+—–+———-+————-+———-+——-+——+
| 8 | SUNNY | 72 | 95 | FALSE | NO |
+—–+———-+————-+———-+——-+——+
| 9 | SUNNY | 69 | 70 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 10 | RAIN | 75 | 80 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 11 | SUNNY | 75 | 70 | TRUE | YES |
+—–+———-+————-+———-+——-+——+
| 12 | OVERCAST | 72 | 90 | TRUE | YES |
+—–+———-+————-+———-+——-+——+
| 13 | OVERCAST | 81 | 75 | FALSE | YES |
+—–+———-+————-+———-+——-+——+
| 14 | RAIN | 71 | 80 | TRUE | NO |
+—–+———-+————-+———-+——-+——+
这样一个数据表就可以用来构建一个决策树。我们需要选择的是到底要不要打网球，那么我们把要不要打网球作为根，然后是天气，如果晴天，那么考虑湿度，如果是雨天，看是否刮风，还有阴天，是4/4都是要去打网球。这样就构建出了一个决策树。
2.ID3算法
ID3算法是一个通过信息熵增减来进行决策的算法。
(待续）

[C#]Stack

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2016年12月9日 | Comments 0 Comment

    public class Stack<T>
    {
        private StackNode<T> Head;
        Exception NullTopEx = new Exception("Null stack head");
        public Stack()
        {
            Head = null;
        }
        public void Push(T data)
        {
            StackNode<T> s = new StackNode<T>(data)
            {
                Next = Head
            };
            Head = s;
        }
        public void Pop()
        {
            if (Head == null)
            {
                throw NullTopEx;
            }
            Head = Head.Next;
        }
        public T GetTop()
        {
            if (Head == null)
            {
                throw NullTopEx;
            }
            return Head.Data;
        }
        public int GetHeight()
        {
            StackNode<T> t = Head;
            int len = 0;
            while (t != null)
            {
                ++len;
                t = t.Next;
            }
            return len;
        }
    }
    public class StackNode<T>
    {
        public T Data;
        public StackNode<T> Next;
        public StackNode()
        {
            Data = default(T);
            Next = null;
        }
        public StackNode(T data)
        {
            Data = data;
            Next = null;
        }
        public StackNode(StackNode<T> next)
        {
            Data = default(T);
            Next = next;
        }
        public StackNode(T data, StackNode<T> next)
        {
            Data = data;
            Next = next;
        }
    }

[C#]LinkedList

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2016年12月9日 | Comments 0 Comment

    public class LinkedList<T>
    {
        Exception NullLinkListEx = new Exception("Null LinkList");
        Exception NullLLorNoIndx = new Exception("Null LinkList or index out of range");
        Exception OutofIndexRang = new Exception("Index out of range");
        public T this[int index]
        {
            get
            {
                return GetElem(index);
            }
            set
            {
                EditElem(index, value);
            }
        }
        private LinkListNode<T> Head { get; set; }
        public LinkedList()
        {
            Head = null;
        }
        public int GetLength()
        {
            LinkListNode<T> p = Head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }
        public void Clear()
        {
            Head = null;
        }
        public bool IsEmpty()
        {
            if (Head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        public void Append(T item)
        {
            LinkListNode<T> q = new LinkListNode<T>(item);
            LinkListNode<T> p = new LinkListNode<T>();
            if (Head == null)
            {
                Head = q;
                return;
            }
            p = Head;
            while (p.Next != null)
            {
                p = p.Next;
            }
            p.Next = q;
        }
        public void Insert(T item, int i)
        {

            if (IsEmpty() || i < 1 || i > GetLength())
            {
                throw NullLLorNoIndx;
            }
            if (i == 1)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = Head
                };
                Head = q;
                return;
            }
            LinkListNode<T> p = Head;
            LinkListNode<T> r = new LinkListNode<T>();
            int j = 1;
            while (p.Next != null && j < i)
            {
                r = p;
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = p
                };
                r.Next = q;
            }
        }
        public void InsertPost(T item, int i)
        {
            if (IsEmpty() || i < 1 || i > GetLength())
            {
                throw NullLLorNoIndx;
            }
            if (i == 1)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = Head.Next
                };
                Head.Next = q;
                return;
            }
            LinkListNode<T> p = Head;
            int j = 1;
            while (p != null && j < i)
            {
                p = p.Next;
                ++j;
            }
            if (j == i)
            {
                LinkListNode<T> q = new LinkListNode<T>(item)
                {
                    Next = p.Next
                };
                p.Next = q;
            }
        }
        public T Delete(int i)
        {
            if (IsEmpty() || i < 0 || i > GetLength())
            {
                throw NullLLorNoIndx;
            }
            LinkListNode<T> q = new LinkListNode<T>();
            if (i == 1)
            {
                q = Head;
                Head = Head.Next;
                return q.Data;
            }
            LinkListNode<T> p = Head;
            int j = 1;
            while (p.Next != null && j < i)
            {
                ++j;
                q = p;
                p = p.Next;
            }
            if (j == i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                throw OutofIndexRang;
            }
        }
        public void EditElem(int i, T data)
        {
            if (IsEmpty() || i < 0)
            {
                throw NullLinkListEx;
            }
            LinkListNode<T> p = new LinkListNode<T>();
            p = Head;
            int j = 0;
            while (p.Next != null && j < i)
            {

                ++j;
                p = p.Next;
            }
            if (j == i)
            {
                p.Data = data;
            }
            else
            {
                throw OutofIndexRang;
            }
        }
        public T GetElem(int i)
        {
            if (IsEmpty() || i < 0)
            {
                throw NullLinkListEx;
            }
            LinkListNode<T> p = new LinkListNode<T>();
            p = Head;
            int j = 0;
            while (p.Next != null && j < i)
            {

                ++j;
                p = p.Next;
            }
            if (j == i)
            {
                return p.Data;
            }
            else
            {
                throw OutofIndexRang;
            }
        }
        public int Locate(T value)
        {
            if (IsEmpty())
            {
                throw NullLinkListEx;
            }
            LinkListNode<T> p = new LinkListNode<T>();
            p = Head;
            int i = 1;
            while (!p.Data.Equals(value) && p.Next != null)
            {
                p = p.Next;
                ++i;
            }
            return i;
        }
    }
    public class LinkListNode<T>
    {
        public T Data { get; set; }
        public LinkListNode<T> Next { get; set; }
        public LinkListNode(T item, LinkListNode<T> p)
        {
            Data = item;
            Next = p;
        }
        public LinkListNode(LinkListNode<T> p)
        {
            Next = p;
        }
        public LinkListNode(T val)
        {
            Data = val;
            Next = null;
        }
        public LinkListNode()
        {
            Data = default(T);
            Next = null;
        }
    }

RMQ问题-ST算法

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2016年11月12日 | Comments 0 Comment

ST算法（Sparse Table）
\(f(i,j) = min(f(i,j-1),f(i+{2}^{(j-1)},j-1))\)
\(f(i,j)\)是区间\([i,i+{2}^{(j-1)}]\)中的最小值，\(f[i,0]=a[i]\)
对于每一个查询\([m,n]\)，找到一个k有\({2}^{k}\leq n-m+1\)
那么有两个区间：\([m,m+{2}^{k-1}]\)和\([n-{2}^{k+1},n]\)
前者为\(f(m,k)\)后者为\(f(n-{2}^{k+1},k)\)
这两个区间的最小值即为查询\([m,n]\)的最小值。

    class RMQ
    {
        int[,] dp;
        public RMQ(int n, int[] array, int MAXM)
        {
            dp = new int[MAXM, Convert.ToInt32(Math.Log(MAXM) / Math.Log(2)) + 2];
            for (int i = 0; i < n; ++i)
            {
                dp[i, 0] = array[i];
            }
            for (int j = 1; (1 << j) <= n; j++)
            {
                for (int i = 0; i + (1 << j) - 1 < n; i++)
                {
                    dp[i, j] = Math.Min(dp[i, j - 1], dp[i + (1 << (j - 1)), j - 1]);
                }
            }
        }
        public int findRMQ(int l, int r)
        {
            int k = Convert.ToInt32(Math.Floor((Math.Log(r - l + 1)) / Math.Log(2)));
            return Math.Min(dp[l, k], dp[r - (1 << k) + 1, k]);
        }
    }

HIHOCODER-WEEK118 最小路径覆盖

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2016年10月7日 | Comments 0 Comment

对于一个有向无环图，最少路径覆盖数=点数-二分图最大匹配
例题+题解：http://hihocoder.com/contest/hiho118/problem/1
代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DINIC
{
    class Program
    {
        static void Main(string[] args)
        {
            int n;
            int[,] flow = new int[1100, 1100];
            int a, b;
            string[] inp;
            inp = Console.ReadLine().Trim().Split(' ');
            a = Convert.ToInt32(inp[0]);
            b = Convert.ToInt32(inp[1]);
            n = 2 * a + 2;
            for (int i = 0; i < b; i++)
            {
                int u, v;
                inp = Console.ReadLine().Trim().Split(' ');
                u = Convert.ToInt32(inp[0]);
                v = Convert.ToInt32(inp[1]);
                u += 1;
                v = v + a + 1;
                flow[u, v] = 1;
            }
            for (int i = 0; i < a; i++)
            {
                flow[1, i + 2] = 1;
                flow[i + 2 + a, n] = 1;
            }
            DINIC d = new DINIC(n, flow);
            a = a - d.ans;
            Console.WriteLine(a);
        }
    }

    class DINIC
    {
        const int INF = 50000;
        const int MAXN = 40005;
        int[,] flow;
        int[] dis;
        int n, res;
        public int ans;
        public DINIC(int a, int[,] f)//a:arc count  b:point count f:squre
        {
            n = a;
            flow = f;
            ans = 0;
            while (bfs() != 0)
            {
                while ((res = dfs(1, INF)) != 0) ans += res;
            }
        }
        private void set(int[] a, int present)
        {
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = present;
            }
        }
        private int bfs()
        {
            dis = new int[MAXN];
            set(dis, -1);
            dis[1] = 0;
            Queue<int> q = new Queue<int>();
            q.Enqueue(1);
            while (q.Count != 0)
            {
                int k = q.Dequeue();
                for (int i = 1; i <= n; i++)
                {
                    if (flow[k, i] > 0 && dis[i] < 0)
                    {
                        dis[i] = dis[k] + 1;
                        q.Enqueue(i);
                    }
                }
            }
            if (dis[n] > 0) return 1;
            else return 0;
        }
        private int dfs(int x, int mx)
        {
            int a;
            if (x == n) return mx;
            for (int i = 1; i <= n; i++)
            {

                if ((flow[x, i] > 0) && (dis[i] == dis[x] + 1))
                {
                    a = dfs(i, Math.Min(mx, flow[x, i]));
                    if (a != 0)
                    {
                        flow[x, i] -= a;
                        flow[i, x] += a;
                        return a;
                    }
                }
            }
            return 0;
        }
    }
}

HIHOCODER-WEEK117 二分图多重匹配

By 罗宋汤里要是没有西红柿和胡萝卜就好了 | 2016年9月28日 | Comments 0 Comment

题目链接：http://hihocoder.com/contest/hiho117/problem/1
我觉得题目里面的关于二分图多重匹配的题解讲得相当透彻，构图之后直接DINIC就可以了。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DINIC
{
    class Program
    {
        static void Main(string[] args)
        {
            int T = Convert.ToInt32(Console.ReadLine());
            while ((T--)>0)
            {
                string[] recv;
                recv = Console.ReadLine().Trim().Split();
                int n = Convert.ToInt32(recv[0]);
                int m = Convert.ToInt32(recv[1]);
                recv = Console.ReadLine().Trim().Split();
                int[] M = new int[m];
                int[,] f = new int[n + m + 3, n + m + 3];
                for (int i = 0; i < m ; i++) 
                {
                    M[i] = Convert.ToInt32(recv[i]);
                }
                for (int i = 2; i <= n + 1; i++)
                {
                    recv = Console.ReadLine().Trim().Split();
                    int a = Convert.ToInt32(recv[0]);
                    f[1, i] = a;
                    int b = Convert.ToInt32(recv[1]);
                    for (int j = 2; j < 2 + b; j++)
                    {
                        int bi = Convert.ToInt32(recv[j]);
                        f[i, bi + n + 1] = 1;
                    }
                }
                for (int i = n + 2; i <= n + 1 + m; i++)
                {
                    f[i, n + m + 2] = M[i - n - 2];
                }
                DINIC d = new DINIC(n + m + 2, f);
                bool flag = true;
                for (int i = 0; i < m; i++)
                {
                    if (f[n + i + 2, n + m + 2] == 0) continue;
                    else
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag) Console.WriteLine("Yes");
                else Console.WriteLine("No");
            }
        }
    }

    class DINIC
    {
        const int INF = 0x3f3f3f3f;
        const int MAXN = 500;
        const double pi = Math.PI;
        int[,] flow = new int[MAXN, MAXN];
        int[] dis;
        int n, res;
        public int ans;
        public DINIC(int a, int[,] f)//a:arc count  b:point count f:squre
        {
            n = a;
            flow = f;
            ans = 0;
            while (bfs() != 0)
            {
                while ((res=dfs(1, INF)) != 0) ans += res;
            }
        }
        private void set(int[] a, int present)
        {
            for (int i=0;i<a.Length;i++)
            {
                a[i] = present;
            }
        }
        private int bfs()
        {
            dis = new int[MAXN];
            set(dis, -1);
            dis[1] = 0;
            Queue<int> q = new Queue<int>();
            q.Enqueue(1);
            while (q.Count != 0)
            {
                int k = q.Dequeue();
                for (int i = 1; i <= n; i++)
                {
                    if (flow[k, i] > 0 && dis[i] < 0) 
                    {
                        dis[i] = dis[k] + 1;
                        q.Enqueue(i);
                    }
                }
            }
            if (dis[n] > 0) return 1;
            else return 0;
        }
        private int dfs(int x, int mx)
        {
            int a;
            if (x == n) return mx;
            for (int i = 1; i <= n; i++)
            {
                
                if ((flow[x, i] > 0) && (dis[i] == dis[x] + 1))
                {
                    a = dfs(i, Math.Min(mx, flow[x, i]));
                    if (a!=0)
                    {
                        flow[x, i] -= a;
                        flow[i, x] += a;
                        return a;
                    }
                }
            }
            return 0;
        }
    }
}