网络流与二分图

定义##

• 记图 G = (V, E)

最大流问题#####

• 记每条边所能传输的最大流量为 c(e)
• 记每条边所能传输的最大流量为 f(e)
• 传输量应当满足以下限制 0 <= f(e) <= c(e)
• 对于任意除源点和汇点之外的节点应当有流入的流量等于流出的流量。
• 目标是最大化从源点发出的数据量

割#####

• 对于某一个顶点集合 S 属于 V，从 S 出发指向S的外部的那些边的集合，记为割 (S, V \ S), 这些边的容量之和称之为割的容量

最小割问题#####

• 对于给定网络， 为了保证没有从 s 到 t 的路径， 需要删去的边的容量的最小值是多少？

匹配#####

• 在 G 中两两没有公共端点的集合 M 属于 E

边覆盖#####

• 在 G 中的任意顶点都至少是 F 中某条边的端点的边的集合 F 属于 E

独立集#####

• 在 G 中两两互不相连的顶点集合 S 属于 V

顶点覆盖#####

• G中的任意边都有至少一个端点属于 S 的顶点集合 S 属于 V

性质##

最大流 = 最小割#####

• 任意一个流都小于等于任意一个割
• 构造出一个流（最大流）等于一个割
• 显然最大流等于最小割
• PS：关于这个证明我感觉下面解释的比较好。

Figure - A minimum cut in the network
We will assume that we are in the situation in which no augmenting path in the network has been found. Let's color in yellow, like in the figure above, every vertex that is reachable by a path that starts from the source and consists of non-full forward edges and of non-empty backward edges. Clearly the sink will be colored in blue, since there is no augmenting path from the source to the sink. Now take every edge that has a yellow starting point and a blue ending point. This edge will have the flow equal to the capacity, otherwise we could have added this edge to the path we had at that point and color the ending point in yellow. Note that if we remove these edges there will be no directed path from the source to the sink in the graph. Now consider every edge that has a blue starting point and a yellow ending point. The flow on this edge must be 0 since otherwise we could have added this edge as a backward edge on the current path and color the starting point in yellow. Thus, the value of the flow must equal the value of the cut, and since every flow is less or equal to every cut, this must be a maximum flow, and the cut is a minimum cut as well.
原文

最大匹配 = 最小顶点覆盖#####

Figure - C.GIF

• 记二分图 G = (U or V, E)，在通过最大流求解最大匹配(设最大匹配为K)所得到的残留网络中，令 S = （从s不可到达的属于U的顶点）or（从s可以到达的属于V的顶点）， 则S是G的一个最小顶点覆盖。
• |S| = |K|
  我们考虑（从s不可到达的属于U的顶点 L）， 此时s向L连的边一定是满流的， 所以它一定会向V匹配一条边E（L，R）， 而此时这条边的右端点（设为R，R属于V）， 一定是不可到达的， 如果R可以到达， s就可以通过E的反向边到达L。
  我们考虑（从s可以到达的属于V的顶点 R）， 此时R向t连的边一定是满流的， 所以它一定是由V匹配的一条边E（L， R）得出的， 而此时这条边的左端点（设为L， L属于U）， 一定是可以到达的（通过反向边）。
  所以我们得出此时二分图匹配的边和S中的顶点一一对应， 所以|S| = |K|。
• S覆盖了所有的边。
  我们假设有的边没有被覆盖， 则它的端点分为三种情况。
• 两个端点都不属于最大匹配
  把这条边加进最大匹配可以得到更优的匹配， 显然不可能。
• 两个端点都是最大匹配的端点
  从残量网络的角度考虑显然这条边属于最大匹配。
• 一个端点是最大匹配的端点， 另一个端点不是
  简便起见， 我们规定左端点是最大匹配的端点而右端点不是。
  显然左端点属于（从s可以到达的属于U的顶点）， 我们可以走右端点而走出一条交错路（增广路）， 就又可以增广了，显然不可能。
• S是最小的点覆盖。
  单单覆盖最大匹配的顶点就至少需要|S|个顶点， 再小的话就有点没有被覆盖了。

对于连通图， |最大匹配| + |最小边覆盖| = |V|#####

Figrue-B.png

• 考虑我们要求出一个最小边覆盖， 显然一个边要尽可能多地覆盖两个之前没有覆盖过的顶点（红色）
• 剩下的边保证一条边覆盖一个定点就好了。（蓝色）
• 证明完毕

|最大独立集| + |最小顶点覆盖| = |V|#####

由最大独立集的定义可知这些顶点两两之间没有边相连， 那最小顶点覆盖只需要盖掉剩下的顶点即可。

代码##

Dinic#####

struct Edge
{
    int d, cap, rev;
    Edge(int d, int cap, int rev) {
        this->d = d, this->cap = cap, this->rev = rev;
    }
};
 
vector<Edge> G[MAX_V];
int level[MAX_V], iter[MAX_V];
 
void add_edge(int s, int d, int cap) {
    G[s].push_back(Edge(d, cap, G[d].size()));
    G[d].push_back(Edge(s, 0, G[s].size() - 1));
}
 
void build_level(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0, q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int i = 0;i < G[v].size();++i) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[e.d] < 0) {
                level[e.d] = level[v] + 1;
                q.push(e.d);
            }
        }
    }
}
 
int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v];i < G[v].size();++i) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.d]) {
            int d = dfs(e.d, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d, G[e.d][e.rev].cap += d;//把cap换成flow也对，想一想为什么
                return d;
            }
        }
    }
    return 0;
}
 
int max_flow(int s, int t) {
    int flow = 0;
    while (true) {
        build_level(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f = dfs(s, t, INF);
        while (f > 0) flow += f, f = dfs(s, t, INF);
    }
    return flow;
}

Bipartite_matching#####

vector<int> G[MAX_V];
int V, matched[MAX_V];
bool used[MAX_V];

void add_edge(int u, int v) {
    G[u].push_back(v), G[v].push_back(u);
}

int dfs(int v) {
    used[v] = true;
    for (int i = 0;i < G[v].size();++i) {
        int u = G[v][i], w = matched[u];
        if ((w < 0) || (!used[w] && dfs(w))) {
            matched[u] = v, matched[v] = u;
            return true;
        }
    }
    return false;
}

int bipartite_matching() {
    int result = 0;
    memset(matched, -1, sizeof(matched));
    for (int v = 0;v < V;++v) {
        if (matched[v] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(v)) ++result;
        }
    }
    return result;
}

MinCostMaxFlow#####

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#define MAX_V (55*55*2)
#define MAX_N 55
#define OFFSET 51*50
#define INF 10000000
using namespace std;
typedef long long ll;
namespace MCMF {
    struct Edge
    {
        int d, cap, cost;
        Edge(int d, int cap, int cost)
            :d(d), cap(cap), cost(cost) { }
    };
    vector<Edge> edges;
    vector<int> G[MAX_V];
    inline int rev(int x) { return x ^ 1; }
    void add_edge(int s, int d, int cap, int cost) {
        int k = edges.size();
        edges.push_back(Edge(d, cap, cost));
        edges.push_back(Edge(s, 0, -cost));
        G[s].push_back(k), G[d].push_back(k + 1);
    }
    void init(int n) {
        for (int i = 0;i <= n;++i) G[i].clear();
        edges.clear();
    }
    int dist[MAX_V], pree[MAX_V], inq[MAX_V], prev[MAX_V];
    void spfa(int s) {
        queue<int> q;
        memset(pree, -1, sizeof(pree));
        memset(prev, -1, sizeof(prev));
        memset(dist, 0x3F, sizeof(dist));
        q.push(s), inq[s] = true, dist[s] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop(), inq[v] = false;
            for (size_t i = 0;i < G[v].size();++i) {
                int k = G[v][i];
                Edge &e = edges[k];
                if (e.cap > 0 && dist[v] + e.cost < dist[e.d]) {
                    dist[e.d] = dist[v] + e.cost, pree[e.d] = k, prev[e.d] = v;
                    if (!inq[e.d]) q.push(e.d), inq[e.d] = true;
                }
            }
        }
    }
    int argu(int s, int t, int &cnt, ll &f) {
        spfa(s);
        if (prev[t] == -1) return 0;
        int maxf = cnt;
        for (int i = t;i != s;i = prev[i])
            maxf = min(maxf, edges[pree[i]].cap);
        for (int i = t;i != s;i = prev[i]) {
            int k = pree[i];
            edges[k].cap -= maxf, edges[rev(k)].cap += maxf;
            f += edges[k].cost * maxf;
        }
        return maxf;
    }
    ll solve(int s, int t, int cnt) {
        ll flow = 0; int flag = true;
        while (cnt > 0 && flag) {
            flag = argu(s, t, cnt, flow);
            cnt -= flag;
        }
        return !cnt ? flow : -1;
    }
}
int N, K, A[MAX_N][MAX_N];
inline int in(int x,int y) { return x * 50 + y; }
inline int out(int x, int y) { return x * 50 + y + OFFSET; }
int main(int argc,char *argv[]) {
    scanf("%d%d", &N, &K);
    for (int i = 1;i <= N;++i)
        for (int j = 1;j <= N;++j) {
            scanf("%d", &A[i][j]);
            MCMF::add_edge(in(i, j), out(i, j), 1, -A[i][j]);
            MCMF::add_edge(in(i, j), out(i, j), INF, 0);
            if (i != N) add_edge(out(i, j), in(i + 1, j));
            if (j != N) add_edge(out(i, j), in(i, j + 1));
        }
    printf("%d\n", MCMF::solve(out(1, 1), in(N, N), K));
}

引用：
二分图最大匹配的König定理及其证明
挑战程序设计竞赛（第二版）
[Poj 1459] 网络流(一) {基本概念与算法}