1

http://www.spoj.com/problems/FASTFLOW/でこの問題を解決しようとしています

この問題には dinic のアルゴリズムが適していると思います。しかし、最悪の場合、この問題には遅すぎる O(EV^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;

}
4

1 に答える 1

1

Cherkassky -- Goldberg によって提案されたグローバルな再ラベル付けヒューリスティックを使用したプッシュ再ラベル アルゴリズムで十分なはずです (m ステップごとに、幅優先探索でラベルを再計算します)。ヒューリスティックを使用した実際の実行時間は、最悪の場合の 3 次境界よりもはるかに優れています。(ギャップの再ラベル付けもできますが、実装が難しく、おそらくこのアプリケーションには必要ありません。)

于 2013-09-27T19:17:20.920 に答える