2015年6月4日 星期四

2015/06/04 flow Dinic 模板

/*
    flow Dinic 模板
    改自 資幹講義
*/
struct E
{
    int t, c;
    E(int _t = 0, int _c = 0){ t = _t; c = _c; }
};

vector<E> es, et;

struct Flow
{
    // 0 is source and N-1 is sink

    #define MAXN 5010
    #define INF 2000000000

    int start, end;

    int N, M, dis[MAXN], ptr[MAXN];
    vector<int> e[MAXN];

    void init(int _N)
    {
        N = _N; M = 0;
        start = 0;
        end = N-1;
    }

    void add(int a, int b, int c)
    {
        e[a].push_back(M++); et.push_back(E(b, c) );
        e[b].push_back(M++); et.push_back(E(a, 0) );
    }

    bool BFS()
    {
        fill(dis, dis+N, INF);
        dis[start] = 0;

        queue<int> que;
        que.push(start);

        while( !que.empty() )
        {
            int f = que.front(); que.pop();

            for(int ei = 0; ei < (int)e[f].size(); ei++)
            {
                E ee = es[e[f][ei] ];

                if( ee.c == 0 || dis[ee.t] != INF ) continue;
                dis[ee.t] = dis[f]+1;
                que.push(ee.t);
            }
        }

        return dis[end] != INF;
    }

    int go(int x, int c)
    {
        if( x == end ) return c;

        int tmp = 0;

        for(int ei = ptr[x]; ei < (int)e[x].size(); ei++)
        {
            E &ee = es[e[x][ei] ];

            if( ee.c == 0 || dis[x]+1 != dis[ee.t] ) continue;

            tmp = go(ee.t, min(c, ee.c));

            if( tmp != 0 )
            {
                ee.c -= tmp;
                es[e[x][ei]^1 ].c += tmp;

                ptr[x] = ei;
                return tmp;
            }
        }

        ptr[x] = e[x].size();
        return 0;
    }

    int maxflow()
    {
        es = et;
        int Ans = 0;

        while( BFS() )
        {
            fill(ptr, ptr+N, 0);

            while(1)
            {
                int tmp = go(start, INF);
                if( tmp ) Ans += tmp;
                else break;
            }
        }

        return Ans;
    }

};

沒有留言:

張貼留言