编程论坛 » 数据结构与算法 » 请教关于网络流的问题

keloy 发表于 2008-3-24 22:07

请教关于网络流的问题

关于网络最大流的实现,小弟知道网络流在是通过找到每个图里面的的一个s-t的最大的流，然后再扩充路径得到一个余图，再查找余图中的一个s-t的最大流，直到没有为止，而且知道最大剪切定理在证明最大留的正确性。
但是小弟一直没想明白的是[color=Red]怎么用广搜的策略来得到一个最大流[/color]，看了很多的代码的都没有看出广搜策略是怎么实现的。主要是没有注释和实例，如果哪位大侠回我的贴的话，请给个[color=Red]实例[/color]吧，只要清楚就可以了，不需要太难的，谢谢了…………

feier7501 发表于 2008-3-25 20:55

网络上好像没有这个算法的实现

/*find函数里的就是bfs的过程，这个程序是我今天刚完成的，可能有错误，但是我测试了一下并没有错误*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
const SIZE=20;
struct node {
        int father,index;
};
struct queue {
        int head,tail;
        node n[SIZE];
};
struct ARC {
        int cap,now;
};
struct graph {
        ARC arc[SIZE][SIZE];
        int ArcNum;
        int src,dest;
        int max;
        void init();
        int find(int &min);
        int maxflow();
};
void graph::init()
{
        scanf("%d",&ArcNum);
        int i,j,k,c;
        for(i=0;i<SIZE;i++)
                for(j=0;j<SIZE;j++)
                        arc[i][j].cap=arc[i][j].now=0;               
        for(k=0;k<ArcNum;k++)
        {
                scanf("%d %d %d",&i,&j,&c);
                arc[i][j].cap=c;
        }
        max=0;
}
int graph::find(int &min)
{
        int visited[SIZE],i,j;
        queue q;
        q.head=q.tail=-1;
        q.tail++;
        q.n[q.tail].index=src;
        q.n[q.tail].father=0;
        memset(visited,0,sizeof(visited));
        visited[src]=1;
        while(q.head < q.tail && q.tail<SIZE)
        {
                int j=q.n[++q.head].index;
                for(i=1;i<SIZE;i++)
                {
                        if(arc[j][i].cap && (arc[j][i].cap-arc[j][i].now) && !visited[i] && i!=dest)
                        {
                                visited[i]=1;
                                q.tail++;
                                q.n[q.tail].father=q.head;
                                q.n[q.tail].index=i;
                        }
                        else if(arc[j][i].cap && (arc[j][i].cap-arc[j][i].now) && !visited[i] && i==dest)
                        {
                                visited[i]=1;
                                q.tail++;
                                q.n[q.tail].father=q.head;
                                q.n[q.tail].index=i;
                                int k=q.tail,kf=q.n[k].father,f=q.n[kf].index,c=q.n[k].index;
                                min=INT_MAX;
                                while(c!=src)
                                {
                                        if(arc[f][c].cap-arc[f][c].now < min)
                                                min=arc[f][c].cap-arc[f][c].now;                                       
                                        c=f;
                                        kf=q.n[kf].father;
                                        f=q.n[kf].index;                                       
                                }
                                f=q.tail;
                                c=q.n[f].index;
                                if(min>0)
                                {
                                        max+=min;
                                        while(f)
                                        {
                                                arc[f][c].now+=min;
                                                f=q.n[f].father;
                                                c=q.n[f].index;
                                        }
                                        return 1;
                                }
                                else
                                        return 0;
                        }
                }
        }
}
int graph::maxflow()
{
        scanf("%d %d",&src,&dest);
        int min,i;
        for(i=0;i<10;i++)
                if(find(min) && min>=0)
                        continue;
                else if(min<=0)
                        break;

        return max;
}
int main()
{
        graph g;
        g.init();
        printf("%d\n",g.maxflow());
        return 0;
}
/*
测试数据：
input:
11
1 2 6
1 3 9
1 4 5
2 5 4
3 5 5
3 6 4
4 6 4
5 6 4
5 7 15
6 2 6
6 7 6
1 7
output:15
*/

feier7501 发表于 2008-3-25 20:57

改正一下

int graph::maxflow()
{
    scanf("%d %d",&src,&dest);
    int min,i;
    for(i=0;i<10;i++)
        if(find(min) && min>=0)
            continue;
        else if(min<0)//此处改一下
            break;

    return max;
}

feier7501 发表于 2008-3-25 21:06

再改一下

int graph::maxflow()
{
        scanf("%d %d",&src,&dest);
        int min,i;       
        while(find(min));       

        return max;
}
这样应该没问题了。

keloy 发表于 2008-3-25 22:13

谢谢了，我还得慢慢的看，不过谢谢了……

查看完整版本: 请教关于网络流的问题