最新费用流的模板

ccf 货物调度

        #include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cwchar>
#include <cwctype>
#include <exception>
#include <locale>
#include <numeric>
#include <new>
#include <stdexcept>
#include <limits>
#include <valarray>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#include <bitset>
#include <algorithm>
#include <functional>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 2147483647;
const int MAXN = 700+10;

struct edge
{
    int to, cap, cost, rev;
    edge(int t = -1, int ca = 0, int co = 0, int r = -1)
    {
        to = t;
        cap = ca;
        cost = co;
        rev = r;
    }
};
vector<edge> E;
vector<int> G[MAXN + 5];
bool vis[MAXN + 5];

void add_edge(int u, int v, int cap, int cost)
{
    int id = E.size();
    E.push_back(edge(v, cap, cost, id + 1));
    E.push_back(edge(u, 0, -cost, id));
    G[u].push_back(id);
    G[v].push_back(id + 1);
}

int n, dist;

int dfs(int v, int t, int& cost, int cf)
{
    if(cf == 0) return 0;
    if(v == t) {
        cost += dist * cf;
        return cf;
    }
    vis[v] = true;
    int gf = cf;
    rep(i, G[v].size()) {
        edge& e = E[G[v][i]];
        if(e.cost == 0 && !vis[e.to]) {
            int f = dfs(e.to, t, cost, min(cf, e.cap));
            cf -= f;
            e.cap -= f;
            E[e.rev].cap += f;
        }
    }
    return gf - cf;
}

bool label()
{
    int cur = INF;
    rep1(i, n) if(vis[i])
    rep(j, G[i].size()) {
        edge& e = E[G[i][j]];
        if(!vis[e.to] && e.cap > 0) cur = min(cur, e.cost);
    }
    if(cur == INF) return false;
    rep1(i, n) if(vis[i])
    rep(j, G[i].size()) {
        edge& e = E[G[i][j]];
        e.cost -= cur;
        E[e.rev].cost += cur;
    }
    dist += cur;
    return true;
}

void MCNF(int s, int t, int& flow, int& cost)
{
    dist = 0;
    flow = cost = 0;
    int cf = 0;
    do do {
        memset(vis, false, sizeof(vis));
        flow += cf = dfs(s, t, cost, INF);
    } while(cf > 0);
    while(label());
}

const int maxn = 1e2+10;
int a[maxn][8], b[maxn][8];
int v[maxn], w[maxn];
typedef pair<int, int> pii;
vector<pii> GG[maxn];

int main()
{
    int m, f = 0, c = 0;
    scanf("%d%d", &n, &m);
    int ss=n*7+1, tt = n*7+2;
    int x, y, z;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=7; j++) scanf("%d", &a[i][j]);
            for(int j=1; j<=7; j++) scanf("%d", &b[i][j]);
            scanf("%d%d", &v[i], &w[i]);
        }
        for(int i=1; i<=m; i++){
            cin>>x>>y>>z;
            GG[x].push_back(make_pair(y, z));
            GG[y].push_back(make_pair(x, z));
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=7; j++){
                add_edge(ss, (i-1)*7+j, a[i][j], 0);
            }
            for(int j=1; j<=7; j++){
                add_edge((i-1)*7+j, tt, b[i][j], 0);
            }
            for(int j=1; j<=7; j++){
                if(j<7)add_edge((i-1)*7+j, (i-1)*7+j+1, v[i], w[i]);
                else add_edge((i-1)*7+j, (i-1)*7+1, v[i], w[i]);
            }
            for(int j=0; j<GG[i].size(); j++){
                PII temp = GG[i][j];
                int v = temp.first;
                int ww = temp.second;
                for(int k=1; k<=7; k++){
                    add_edge((i-1)*7+k, (v-1)*7+k, INF, ww);
                }
            }
        }
        n = 7*n+2;
    MCNF(ss, tt, f, c);
    printf("%d\n", c);
    return 0;
}

    

原文：https://www.cnblogs.com/babydragon/p/11791108.html