最大流（转）
http://yuanhuixie.blogcn.com/流网络G=(V,E)是一个有向图，每一条边都有一非负容量 c(u,v)>=0.流网络中有两个特殊的点：源点 s 和汇点 t 。
最大流问题中，给出一个具有源点和汇点的流网络，希望找出从源点到汇点的最大值流。
解决最大流问题的 Ford-Fulkerson 方法依赖于三种重要的思想：残留网络、增广路径和割。
Ford-Fulkerson是一种迭代的方法，通过更新有边相连的每对顶点 u,v之间的网络流 f,来计算出图 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; for(int i=0;i<G.Length;i++) for (int j = 0; j < G.Length; j++) { if (G != 0)//如果（u,v）是图G的边，把那条边的流值初始化为０ { f = 0; f = 0; } } while ((P = ExistPath(G))!=null)//这里判断图 G中是否有残余流网络，此函数可以用广度优先搜索，但是我还是没写好 { c = P.Min(); //取出增广路径的残余容量 c while(P.Next!=null) { f += c; f = 0 - f; 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; for (int i = 0; i < G.Length; i++) for (int j = 0; j < G.Length; j++) { if (G != 0)//如果（u,v）是图G的边，把那条边的流值初始化为０ { f = 0; f = 0; } } while ((P = ExistPath(G, s, t, f)) != null)//这里判断图 G中是否有残余流网络，返回增广路径 { c = P.Min(); //取出增广路径的残余容量 c while (P.Next != null) { f += c; f = 0 - f; 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; for (int i = 0; i < G.Length; i++) Pass = -1; Pass = 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 = Next; j = Next; if (Next == t)//当到达汇点时就停止 break; } for (int i = 0; i < G.Length; i++) { L2.Key = Pass; L2 = L2.Next; if (Pass == t)//当搜索过程中有到达汇点的就表示存在有增广路径 { L2.Key = Pass; return L; } } return null; } public int NextNode(int[,] G, int[,] Pass, int j) { for (int i = 0; i < G.Length; i++) { if (Pass == -1) //当节点没有被经过 { if (G != 0 && f != G)//当边（j,i）存在 且有残余容量时 { return i; } } } return -1; }
页:
[1]