杰 & C++ & Python & DM

图论最大网络流(一) POJ 1273 解题报告

        题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
        本题是最大流算法的简单应用。
        最大网络流的基本思想很简单——从某个初始流开始,反复的增加流的流量知道不能再改进为止。最后得到的流将是一个最大流。
        定理P 是网络 G 中从起点到终点满足一下条件的一条路径:
                  (a) 对P中的每条正向边(i,j)Fij   <  Cij
                 
                (b)对P中的每条反向边(i,j)Fij    >  0
                 设 D是由P中所有正向边(i,j)对应的数和P中所有反向边(i,j)对应的数组成。
                          Δ =min D
         
                                               Fij                   如果(i,j)不在P中
                     F*ij={  FijΔ  如果(i,j)在P中且是正向的
               Fij-Δ   如果(i,j)在P中且不是正向的


   根据上述定理,如果找不到路径满足上述定理,那么得到的流便是最大的。我们可以构造一个算法:
   1.从一个流开始;
   2.寻找一个满足上述定理的路径,如果这样的路径不存在,则停止,流是最大的;
   3.将流过这条路径的流量增加△,转到第2行。
   Ford-Fulkerson方法是按照上述定理构造,解决最大流问题的有效方法,一般采用深搜策略;而Edmonds-Karp算法是Ford-Fulkerson方法的广搜的实现;相对而言,后者的效率稍微高一些。
        
      下面是POJ 1273的代码,采用的是Edmonds-Karp算法。
   

 1#include <cstdio>
 2#include <queue>
 3const int INF=0x0fffffff;
 4const int SIZE=202;
 5
 6int bfs(int (*mat)[SIZE],int start,int end,int* path)
 7{
 8    int flow[SIZE];//存储一次BFS遍历之后流的可改进量;
 9    std::queue<int> q;
10    int i;
11    
12    for(i=0;i<SIZE;++i)
13        path[i]=-1;
14    path[start]=0,flow[start]=INF;
15
16    q.push(start);
17    while(!q.empty())
18    {
19        int top=q.front();
20        q.pop();
21        if(top==end) break;
22        for(i=1;i<=end;++i)
23        {
24            if(i != start && path[i]==-1 && mat[top][i])
25            {
26                flow[i]=flow[top]<mat[top][i] ? flow[top] : mat[top][i];
27                q.push(i);
28                path[i]=top;
29            }

30        }

31    }

32    if(path[end]==-1return -1;
33    return flow[end];
34
35
36}

37int Edmonds_Karp(int (*mat)[SIZE],int start,int end)
38{
39    int maxflow=0,step,cur,pre;
40    int path[SIZE];    ////存储当前已访问过的节点的增广路径;
41    while((step=bfs(mat,start,end,path)) != -1)//找不到增广路径时退出
42    {
43        maxflow += step;
44        cur=end;
45        while(cur != start)
46        {
47            pre=path[cur];
48            mat[pre][cur] -= step;    //更新正向边的实际容量
49            mat[cur][pre] += step;    //添加反向边
50            cur=pre;
51        }

52    }

53    return maxflow;
54}

55
56int main()
57{
58    int mat[SIZE][SIZE];
59    int vecNum,edgeNum;
60    int i;
61    int a,b,c;
62    
63    while(scanf("%d%d",&edgeNum,&vecNum)!=EOF)
64    {
65        memset(mat,0,sizeof(mat));
66        for(i=0;i<edgeNum;++i)
67        {
68            scanf("%d%d%d",&a,&b,&c);
69            mat[a][b]+=c;
70        }

71        
72        int re=Edmonds_Karp(mat,1,vecNum);
73        printf("%d\n",re);
74
75    }

76    return 0;    
77}

78

 


 

posted on 2009-04-26 19:18 jaysoon 阅读(939) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

收藏夹

C++

搜索

最新评论

阅读排行榜

评论排行榜