最小費用流の負辺除去
(mincostflow/negativeedge.cpp)

• View this file on GitHub
• Last update: 2020-10-27 18:08:33+09:00

解説記事

最小費用流の負辺除去

Depends on

• 最小費用流 (mincostflow/primaldual.cpp)

Verified with

• test/aoj/2627.test.cpp

Code

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "primaldual.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
// O((F+F') E \log V), F': sum of caps with negative cost
template<typename Flow, typename Cost>
struct NegativeEdge{
  PrimalDual<Flow, Cost> G;
  vector<Flow> fs;
  Cost sum;
  int S,T;
  NegativeEdge(int n):G(n+2),fs(n+2,0),sum(0),S(n),T(n+1){}

  void use_edge(int u,int v,Flow cap,Cost cost){
    fs[u]-=cap;
    fs[v]+=cap;
    sum=sum+cost*cap;
  }

  void add_edge(int u,int v,Flow cap,Cost cost){
    if(cost<Cost(0)){
      use_edge(u,v,cap,cost);
      swap(u,v);
      cost=-cost;
    }
    G.add_edge(u,v,cap,cost);
  }

  bool build(){
    Flow f=0;
    for(int i=0;i<S;i++){
      if(fs[i]>0){
        f+=fs[i];
        G.add_edge(S,i,+fs[i],Cost(0));
      }
      if(fs[i]<0){
        G.add_edge(i,T,-fs[i],Cost(0));
      }
    }
    return G.build(S,T,f);
  }

  bool build(int ts,int tt,Flow tf){
    fs[ts]+=tf;
    fs[tt]-=tf;
    return build();
  }

  Cost get_cost(){
    return sum+G.get_cost();
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: mincostflow/negativeedge.cpp: line 6: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page