荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: kaman (Aspire追月|Fight for Final), 信区: ACMICPC
标  题: 典型算法与ACM题目解析(01)—寻找最大流的标号法zz
发信站: 荔园晨风BBS站 (Wed Nov  8 15:34:14 2006), 站内

这种算法又叫Ford-Fulkerson算法,算法的核心思想是使用标号的方法不断寻找一个图上
的可增广路径并且进行调整,直到找不到可增广路径为止,此时得到的可行流即是该网络
的最大流。

算法导论上对这种算法的伪码表示如下
    FORD-FULKERSON(G, s, t)
    1 for each edge (u, v)  E[G]
    2   do f[u, v] ← 0
    3       f[v, u] ← 0
    4 while there exists a path p from s to t in the residual network Gf
    5   do cf(p) ← min {cf(u, v) : (u, v) is in p}
    6       for each edge (u, v) in p
    7           do f[u, v] ← f[u, v] + cf(p)
    8               f[v, u] ← -f[u, v]

Google Code Jam 2006提供的第一道练习题所用的算法就是以上所说的算法

题目的大意是,给一个无向图和图上任意两点之间是否有通路,一个人从0点到1点总共最
多有多少条不同的道路可选,要求一个点(0,1除外)最多只能有一条道路覆盖,要求最多有
多少条满足这个条件的从0点到1点的道路。

由于题目给出的数据量太小,总点数只有12,估计搜索或枚举之类的方法应该可以通过,
但是这道题最好的方法还是上面所说的求最大流的FF算法,如何将这个图转化成我们求最
大流的图呢?我们常用的方法是拆点法。
将0,1之外的其它点全部都拆成两个,Xa和Xb,设到点某点Y有一条到X的路径,就设Yb->
Xa的流量为1,同时设置Xa->Xb的流量为1,那么从X点流进的流量可能大于1,流出的流量
也可能大于1,但是流经X点的流量最大为1,这也就保证了只有一条路经过X。

这个算法在平均情况下是O(V^3)的,在数据量如此之小的情况下不存在超时的可能性,当
然除非程序出现了死循环。

代码如下:

PS:由于TopCoder只要求参赛者写出一个类和一个方法即可,所以此题的代码和ACM的代码
有很大的不同,最重要的一点就是编译后不会生成.exe文件,毕竟程序里面没有main函数
嘛!

/********************************************/
/*      Google Code Jam practice 1          */
/*      Algo:max-flow                       */
/*      Author:Sempr                        */
/********************************************/

#include <vector>
#include <string>
#include <cstring>
#define SIZE 30
using namespace std;

class SalesRouting
{
    int Q[SIZE];
    int Qf[SIZE];
    int c[SIZE][SIZE];
    int f[SIZE][SIZE];
    int M, N;
    int maxflow(int s, int t)
    {
        int head, tail, i;
        int h;
        int flow = 0;
        memset(f, 0, sizeof(f));
        while (1)
        {
            head = 0;
            tail = 1;
            Q[0] = s;
            memset(Qf, -1, sizeof(Qf));
            Qf[s] = 0;
            while (head < tail)
            {
                h = Q[head++];
                for (i = 0; i < N; i++)
                {
                    if (-1 == Qf[i] && c[h][i] > f[h][i])
                    {
                        Q[tail++] = i;
                        Qf[i] = h;
                    }
                }
                if (Qf[t] != -1)
                    break;
            }
            if (-1 == Qf[t])
                break;
            h = t;
            while (h != s)
            {
                f[Qf[h]][h]++;
                f[h][Qf[h]] = -f[Qf[h]][h];
                h = Qf[h];
            }
            flow++;
        }
        return flow;
    }
    public:
    int howMany(vector <string> adj)
    {
        int i, j;
        M = adj.size();
        N = (M - 1) * 2;
        memset(c, 0, sizeof(c));
        for (i = 2; i < M; i++)
        {
            c[i * 2 - 2][i * 2 - 1] = 1;
            for (j = 2; j < M; j++)
            {
                if (adj[i][j] == '1')
                {
                    c[i * 2 - 1][j * 2 - 2] = 1;
                }
            }
        }
        for (i = 0; i < M; i++)
        {
            if (adj[i][0] == '1')
                c[0][i * 2 - 2] = 1;
            if (adj[1][i] == '1')
                c[i * 2 - 1][1] = 1;
        }
        return maxflow(0, 1);
    }
};

--
▁▃▄▅▃▂▁ /╲_                   .
         __  ╱/ ╲╲╱╲            ヌ  ゑ
       ╱  ╳ ;  /▁▂▃▄▃▂▁     リ  θ           一山一水一圣人
      /  \ ╲╱ \  / :    ╲────╮         ——白雲黃鶴ShanDong版
    ╱\   \╱╳╲ :: |/ ﹨: ╲──╮╰────────────╮
   / . \  /;╲     /\/; ; :﹨ ╲  ╰────────────╮╰───
※ 修改:·Sempr 于 08月17日19:47:30 修改本文·[FROM: bbs.whnet.edu.cn]
※ 来源:·武汉白云黄鹤站 bbs.whnet.edu.cn·
※ 修改:·Sempr 于 08月17日19:48:26 修改本文·[FROM: bbs.whnet.edu.cn]
※ 来源:·武汉白云黄鹤站 bbs.whnet.edu.cn·
※ 来源:·武汉白云黄鹤站 bbs.whnet.edu.cn·


--

     Science is what we understand well enough to explain to a computer.
     Art is everything else we do.

                                                 ———— Donald E. Knuth



※ 修改:·kaman 于 Nov  8 15:34:17 修改本文·[FROM: 192.168.14.224]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.224]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店