最大流以及费用流刘汝佳算法竞赛入门经典模板

最大流模版EdmondsKarp算法, (刘汝佳算法竞赛入门经典)

#include <cstdio>//C语言io
#include <cstring>//以下是c语言常用头文件
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cmath>
#include <iostream>//c++IO
#include <sstream>
#include <string>
#include <list>//c++常用容器
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>//c++泛型的一些函数
#include <functional>//用来提供一些模版
#define fo0(i,n) for(int i = 0;i < n; ++i)
#define fo1(i,n) for(int i = 1;i <= n; ++i)
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
//......................................................
const int maxn = 500+100;
struct Edge{
  int from,to,cap,flow;
  Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}

};
struct EK{
  int n,m;
  vector<Edge> edges;
  vector<int> G[maxn];
  int a[maxn];
  int p[maxn];
  void init(int n)
  {
      for(int i = 0;i < n; ++i)
        G[i].clear();
  }
  void AddEdge(int from,int to,int cap)
  {
      edges.push_back(Edge(from,to,cap,0));
      edges.push_back(Edge(from,to,0,0));
      m = edges.size();
      G[from].push_back(m-2);
      G[to].push_back(m-1);

  }
  int Maxflow(int s,int t)
  {
      int flow = 0;
      while(1)
      {
          me(a);
          queue<int> Q;
          Q.push(s);
          a[s] = INF;
          while(!Q.empty())
          {
              int x = Q.front();Q.pop();
              for(size_t i = 0;i < G[x].size();++i)
              {
                  Edge& e = edges[G[x][i]];
                  if(!a[e.to]&&e.cap>e.flow)
                  {
                      p[e.to] = G[x][i];
                      a[e.to] = min(a[x],e.cap-e.flow);
                      Q.push(e.to);
                  }

              }
              if(a[t])
                    break;
          }
          if(!a[t])
            break;
          flow += a[t];
          for(int  u = t; u != s;u = edges[p[u]].from)
          {
              edges[p[u]].flow += a[t];
              edges[p[u]^1].flow -= a[t];
          }
      }
      return flow;
  }

};

int main()
{
   int n,m;
   EK ek;
   while(cin>>n>>m)
   {
       ek.init(n);

       int u,v,w;
       while(m--)
       {
           scanf("%d %d %d",&u,&v,&w);
           ek.AddEdge(u,v,w);
       }
       printf("%d\n",ek.Maxflow(1,n));
   }


    return 0;
}

最小花费最大流

const int LEN_of_Node = 5000+10;
const int LEN_of_Edge = 100000;
const int maxn = 1e9;
struct Edge
{
    int from,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){};
};
struct EK
{

    int n,m;
    vector<Edge> edges;
    vector<int> G[LEN_of_Node];
    int inq[LEN_of_Node];
    int p[LEN_of_Node];
    int a[LEN_of_Node];
    int dis[LEN_of_Node];
    void init(int n)
    {
        this->n = n;
        for(int i = 0;i < n; ++i)
            G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap,int cost)
    {
       edges.push_back(Edge(from,to,cap,0,cost));
       edges.push_back(Edge(to,from,0,0,-cost));
       m = edges.size();
       G[from].push_back(m-2);
       G[to].push_back(m-1);
    }
    bool BellmanFord(int s,int t,int &flow,long long &cost)
    {
       for(int i = 0;i < n; ++i)
        dis[i] = maxn ;
       dis[s] = 0;
       me(inq);
       inq[s] = 1;
       a[s] = maxn;
       queue<int> Q;
       Q.push(s);
       while(!Q.empty())
       {
           int q = Q.front();
           Q.pop();
           inq[q] = 0;
           for(size_t i = 0;i < G[q].size();++i)
           {
               Edge &tmp = edges[G[q][i]];
               if(tmp.cap>tmp.flow&&dis[tmp.to] > dis[q] + tmp.cost)
               {
                   dis[tmp.to] = dis[q] + tmp.cost;
                   a[tmp.to] = min(a[q],tmp.cap-tmp.flow);
                   p[tmp.to] = G[q][i];
                   if(!inq[tmp.to])
                   {
                       inq[tmp.to] = 1;
                       Q.push(tmp.to);
                   }
               }
           }
       }
       if(dis[t]==maxn)
        return false;
       flow += a[t];
       cost += (LL) a[t]*(LL)dis[t];
       for(int u = t; u != s; u = edges[p[u]].from)
       {
           edges[p[u]].flow += a[t];
           edges[p[u]^1].flow -= a[t];
       }
// for(int now = p[t];now; now = p[edges[now].from] )
// {
// edges[now].flow += a[t];
// edges[now^1].flow -= a[t];
// }
       return true;
    }
    void MincostMaxflow(int s,int t,int &flow,long long &cost)
    {
        flow = 0;
        cost = 0;
        while(BellmanFord(s,t,flow,cost));
    }

};
EK ek;
int main(void)
{
// cout<<INT_MAX<<endl;
    int N,M,S,T;
    while(cin>>N>>M>>S>>T)
    {
       ek.init(N);
       int u,v,w,c;
       for(int i = 0;i < M; ++i)
       {
           scanf("%d %d %d %d",&u,&v,&w,&c);
           ek.AddEdge(u,v,w,c);
       }
       int flow;
       LL ans;
       ek.MincostMaxflow(S,T,flow,ans);
       printf("%d %lld\n",flow,ans);

    }
    return 0;
}