最大流（转）

   http://yuanhuixie.blogcn.com/

    流网络G=(V,E)是一个有向图，每一条边都有一非负容量 c(u,v)>=0.流网络中有两个特殊的点：源点 s 和汇点 t 。
   最大流问题中，给出一个具有源点和汇点的流网络，希望找出从源点到汇点的最大值流。
   解决最大流问题的　Ford-Fulkerson 方法依赖于三种重要的思想：残留网络、增广路径和割。
   Ford-Fulkerson是一种迭代的方法，通过更新有边相连的每对顶点 u,v之间的网络流 f[u,v],来计算出图 G=(V,E)中的最大流。

  

class Link
    {
        public int key;
        public int c;
        public Link next;

        public int Key
        {
            get
            { return key; }
            set
            { key = value; }
        }

        public int C
        {
            get
            { return c; }
            set
            { c = value; }
        }

        public Link Next
        {
            get
            { return next; }
            set
            { next = value; }
        }

        public Link()
        {
            key = 0;
            c = 0;
            next = null;
        }

        public int Min()  //返回残余容量
        {
            Link R=this.Next;
            int min = this.C;
            while (R != null)
            {
                if (min > R.C)
                    min = R.C;
                R = R.Next;
            }
            return min;
        }
       
    }

     public int[,] Ford_Fulkerson(int[,] G, int s, int t)
        {
            int c = 0;
            Link P = new Link();   //P用于表示图 G 的一条增广路径。
            int[,] f = new int[G.Length, G.Length];
            for(int i=0;i<G.Length;i++)
                for (int j = 0; j < G.Length; j++)
                {
                    if (G[i, j] != 0)  //如果（u,v）是图G的边，把那条边的流值初始化为０
                    {
                        f[i, j] = 0;
                        f[j, i] = 0;
                    }
                }
            while ((P = ExistPath(G))!=null)  //这里判断图 G中是否有残余流网络，此函数可以用广度优先搜索，但是我还是没写好
            {
                c = P.Min(); //取出增广路径的残余容量 c
                while(P.Next!=null)
                {
                    f[P.Key, P.Next.Key] += c;
                    f[P.Next.Key, P.Key] = 0 - f[P.Key, P.Next.Key];
                    P = P.Next;
                }
            }
            return f;
        }

昨天写了最大流里面的 Ford-Fulkerson 算法，但是里面有个寻找函数 ExistPath(int[,] G, int s, int t, int[,] f)  我没写出来，今天写好了，现在再发一次：


 

 public int[,] Ford_Fulkerson(int[,] G, int s, int t)
        {
            int c = 0;
            Link P = new Link();   //P用于表示图 G 的一条增广路径。
            int[,] f = new int[G.Length, G.Length];
            for (int i = 0; i < G.Length; i++)
                for (int j = 0; j < G.Length; j++)
                {
                    if (G[i, j] != 0)  //如果（u,v）是图G的边，把那条边的流值初始化为０
                    {
                        f[i, j] = 0;
                        f[j, i] = 0;
                    }
                }
            while ((P = ExistPath(G, s, t, f)) != null)  //这里判断图 G中是否有残余流网络，返回增广路径
            {
                c = P.Min(); //取出增广路径的残余容量 c
                while (P.Next != null)
                {
                    f[P.Key, P.Next.Key] += c;
                    f[P.Next.Key, P.Key] = 0 - f[P.Key, P.Next.Key];
                    P = P.Next;
                }
            }
            return f;
        }

        public Link ExistPath(int[,] G, int s, int t, int[,] f)
        {
            int j = s, k = 0, Next = 0;
            int[] Pass = new int[G.Length];
            for (int i = 0; i < G.Length; i++)
                Pass[i] = -1;

            Pass[k] = s;    //用 Pass[] 记下遍历过程中经过的节点的顺序
            Link L2 = new Link();
            Link L = L2;

            for (int i = 0; i < G.Length; i++)
            {
                if ((Next = NextNode(G, Pass, j)) != -1)
                    Pass[k++] = Next;
                j = Next;
                if (Next == t)  //当到达汇点时就停止
                    break;
            }
            for (int i = 0; i < G.Length; i++)
            {
                L2.Key = Pass[i];
                L2 = L2.Next;
                if (Pass[i] == t)  //当搜索过程中有到达汇点的就表示存在有增广路径
                {
                    L2.Key = Pass[i];
                    return L;
                }
            }
            return null;
        }

        public int NextNode(int[,] G, int[,] Pass, int j)
        {
            for (int i = 0; i < G.Length; i++)
            {
                if (Pass[i] == -1)   //当节点没有被经过
                {
                    if (G[j, i] != 0 && f[j, i] != G[j, i])  //当边（j,i）存在 且有残余容量时
                    {
                        return i;
                    }
                }
            }
            return -1;
        }