algorithm - Dinic 算法实现和一个 spoj 难题

Question

我正在尝试在 http://www.spoj.com/problems/FASTFLOW/ 上解决这个问题

我想 dinic 的算法适合这个问题。但它在 O(E.V^2) 时间内运行，这在最坏的情况下对于这个问题来说太慢了。对于不同的算法或改进该算法的运行时间有什么建议吗？

编辑:我包括了我对 dinic 算法的实现。显然，它包含一些错误......任何人都可以提供一些测试用例或帮助调试程序逻辑。

//#define DEBUG       //comment when you have to disable all debug macros.
#define NDEBUG    //comment when all assert statements have to be disabled.
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <climits>
#include <ctime>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <sys/time.h>
#include <iomanip>
#include <cstdarg>
#include <utility> //std::pair
#include <cassert>
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define log2(x) (log(x)/log(2))
#define ARRAY_SIZE(arr) (1[&arr]-arr)      
#define INDEX(arr,elem)        (lower_bound(all(arr),elem)-arr.begin())
#define lld long long int
#define MOD 1000000007
#define gcd __gcd
#define equals(a,b) (a.compareTo(b)==0)    //for strings only
using namespace std;


#ifdef DEBUG
#define debug(args...)            {dbg,args; cerr<<endl;}
#else
#define debug(args...)              // Just strip off all debug tokens
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
        {    
            cerr<<v<<" ";    
            return *this;    
        }

}dbg;

/**********************************MAIN CODE***************************************************/

//runs in O(V^2E) time.
//might consider using a 1-d array of size V*V for large values of V

vector<vector<lld> > flow, capacity, level_graph;
lld V;
vector<lld> *adj, *level_adj;

void init(lld v)
{
    adj=new vector<lld>[v+1];
    level_adj=new vector<lld>[v+1];   
    V=v;
    flow.resize(V+1);
    capacity.resize(V+1);
    level_graph.resize(V+1);
    for(lld i=0;i<=V;i++)
        flow[i].resize(V+1), capacity[i].resize(V+1), level_graph[i].resize(V+1);
}

void add_edge(lld u, lld v, lld uv, lld vu=0)
{
    capacity[u][v]=uv;
    capacity[v][u]=vu;
    adj[u].push_back(v);
    flow[u][v]=uv;             //will store the present capacity. facility for the residual graph
    flow[v][u]=vu;
    if(vu) adj[v].push_back(u);
}

void update_residual_graph(lld source, lld destination, lld *parent)        //push augment flow in the residual graph and modify the latter.
{
    lld i=destination, aug=LLONG_MAX;
    while(parent[i]!=-2)
    {
        //debug(i);
        aug=min(aug,flow[parent[i]][i]);
        i=parent[i];
    }
    i=destination;
    while(parent[i]!=-2)
    {
        flow[parent[i]][i]-=aug;
        flow[i][parent[i]]=capacity[parent[i]][i]-flow[parent[i]][i];
        i=parent[i];
    }
}

bool DFS(lld source, lld destination)
{
    stack<lld> state;
    bool visited[V+1], present;
    lld parent[V+1],t;
    memset(visited, false, sizeof(visited));
    memset(parent, -1, sizeof(parent));
    parent[source]=-2;
    state.push(source);
    visited[source]=true;
    while(!state.empty())
    {
        t=state.top();
        present=false;
        for(vector<lld>::iterator it=level_adj[t].begin(); it!=level_adj[t].end();it++)
        {           
            parent[*it]=t;
            if(!visited[*it] && level_graph[t][*it])
            {
                present=true;
                state.push(*it);
                visited[*it]=true;
                if(*it==destination)
                    update_residual_graph(source,destination,parent);   //update residual graph
            }

        }
        if(!present)
            state.pop();
    }
    return parent[destination]!=-1;
}


bool BFS(lld source, lld destination)
{
    //create level graph usign BFS
    fill(level_graph.begin(), level_graph.end(), vector<lld>(V+1,-1));
    lld i,j;
    for(i=1;i<=V;i++)
        level_adj[i].clear();


    queue<lld> state;
    lld level[V+1],t;      //record of minimum distance from source
    memset(level,-1, sizeof(level));
    state.push(source);
    level[source]=0;
    while(!state.empty())
    {
        t=state.front();
        state.pop();
        for(vector<lld>::iterator it=adj[t].begin();it!=adj[t].end();it++)
        {
            if((level[*it]==-1 && flow[t][*it]) || (level[*it]==level[t]+1))
            {
                level_graph[t][*it]=flow[t][*it];
                level_adj[t].push_back(*it);
                level[*it]=level[t]+1;
                state.push(*it);
            }
        }
    }
    if(level[destination]==-1)
        return false;

    //call DFS and update the residual graph
    return DFS(source,destination);

}

lld maximum_flow(lld source, lld destination)
{
    while(BFS(source,destination));
    lld max_flow=0;
    for(vector<lld>::iterator it=adj[source].begin(); it!=adj[source].end(); it++)
        max_flow+=flow[*it][source];
    return max_flow;
}

int main()
{
    lld e,u,v,n,c;
    //cout<<"V:"<<endl;
    cin>>n>>e;
    init(n);

    while(e--)cin>>u>>v>>c, add_edge(u,v,c);

    cout<<maximum_flow(1,n)<<endl;

}

Answer 1

Cherkassky--Goldberg 提出的具有全局重标记启发式的推重标记算法应该足够了(每 m 步，使用广度优先搜索重新计算标签)。启发式的实际运行时间比最坏情况的立方边界要好得多。 (您也可以进行间隙重新标记，但实现起来比较棘手，并且对于此应用程序可能不是必需的。)