最小费用最大流

假设每条边除了有一个容量限制外，还有一个单位流量所需的费用(cost)。该网络中花费最小的最大流称为最小费用最大流，即总流量最大的情况下，总费用最小的流。

证：在残余网络上求最短路是最小费用

1. 设有 f 为以以上方式求出的结果， 设 f ’ 和 f 流量相同，但是费用更少
   因为 f ‘ - f 的流量流入流出为 0，所以他是成环的
   又因为 f ’ - f 的费用是负的，所以在这些环中，存在负环

结论：f 是最小费用流的充要条件是残余网络中没有负环

2. 对于流量为 0 的流 f [ 0 ] ，其残余网络为原图，原图没有负环，则 f [ 0 ] 就是最小费用流
   设流量为 i 的流 f [ i ] 是最费用小流，并且下一步我们求得流量为 i + 1 的流 f [ i+1 ]，按照方法，f [ i + 1 ] - f [ i ] 就是 f [ i ] 对应的参余网络中 s 到 t 的最短路
   假设 f [ i + 1 ] ' 的费用比 f [ i + 1 ]还小，则 f [ i + 1 ] '- f [ i ] 的费用比f[ i + 1 ] - f [ i ] 还小，所以f [ i + 1 ] '- f [ i ] 中有负环
   所以这与假设矛盾，于是可以证明这种方法是正确的

MCMF 算法

时间复杂度 ，F 为最大流量。
在最大流的 EK 算法求解最大流的基础上，把 用 BFS 求解任意增广路 改为 用 SPFA 求解单位费用之和最小的增广路 即可。
slf优化，就是对于spfa的进队操作，进之前判一下若小于队头就直接插在队头，这个还是蛮有用的，可以提升点速度；

SPFA + EK 版

// 洛谷 板子题（https://www.luogu.com.cn/problem/P3381）
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5001;
const int maxm = 5e5+1;

struct edge{
    int to, next, cap, flow, cost;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, pre[maxn], d[maxn], flow[maxn];
bool vis[maxn];

void addedge(int u, int v, int w, int c) {
    e[++tot] = {v, head[u], w, 0,  c}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0, -c}, head[v] = tot;
}

bool spfa() {
    memset(d, 0x7f, sizeof d);
    memset(vis, false, sizeof vis);
    memset(flow, 0, sizeof flow);
    deque<int> q; q.push_back(s);
    d[s]=0, flow[s] = INT_MAX;
    vis[t] = true;
    while(!q.empty()) {
        int x = q.front(); q.pop_front();
        vis[x] = false;
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] > d[x] + e[i].cost && e[i].cap > e[i].flow) {
                flow[j] = min(flow[x], e[i].cap - e[i].flow), pre[j] = i;
                d[j] = d[x] + e[i].cost;
                if (!vis[j]) {
                    vis[j] = true;
                    if (!q.empty() && d[j] < d[q.front()])  // slf 优化
                        q.push_front(j);
                    else q.push_back(j);
                }
             }
        }
    }
    return flow[t];
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head); tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
        addedge(u, v, w, c);
    }
    int maxflow = 0, mincost = 0;
    while(spfa()) {
        for(int i = t; i != s; i = e[ pre[i]^1 ].to) {
            e[ pre[i] ].flow += flow[t];
            e[ pre[i]^1 ].flow -= flow[t];
        }
        maxflow += flow[t], mincost += d[t] * flow[t];
    }
    printf("%d %d\n", maxflow, mincost);
    return 0;
}

SPFA + Dinic 版

由于费用流分层过于分散，每次跑完最短路都很难找到同层的多条增广路，所以，Dinic算法就没有太大的优势（弧优化很不划算，但剪枝优化可以试试），而且在费用流的残留网络中有负边的存在，虽然不存在负圈，但存在0圈，那么跑dfs时必须添加一个标记数组，所以直接在这个基础上做一个路径优化。
路径优化，重新定义最短路，从 t 开始跑最短路，d[x] 表示点x 到汇点的最短路，这样可以省去无效路径的搜索。

// 洛谷 板子题（https://www.luogu.com.cn/problem/P3381）
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

const int maxn = 5001;
const int maxm = 5e4+1;

struct edge{
    int to, next, cap, flow, cost;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, d[maxn];
bool vis[maxn];

void addedge(int u, int v, int w, int c) {
    e[++tot] = {v, head[u], w, 0,  c}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0, -c}, head[v] = tot;
}

bool spfa() {
    memset(d, 0x7f, sizeof d);
    memset(vis, false, sizeof vis);
    deque<int> q; q.push_back(t);
    d[t]=0;
    while(!q.empty()) {
        int x = q.front(); q.pop_front();
        vis[x] = false;
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] > d[x] - e[i].cost && e[i^1].cap > e[i^1].flow) {
                d[j] = d[x] - e[i].cost;
                if (!vis[j]) {
                    vis[j] = true;
                    if (!q.empty() && d[j] < d[q.front()]) q.push_front(j);
                    else q.push_back(j);  //  slf 优化
                }
             }
        }
    }
    return d[s] != d[0];
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
    vis[x] = true;
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (!vis[j] && d[x] - e[i].cost == d[j] && e[i].cap > e[i].flow) {
            f = dfs(j, min(e[i].cap - e[i].flow, flow - used));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    return used;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
        addedge(u, v, w, c);
    }
    int maxflow = 0, mincost = 0;
    while(spfa()) {
        while(int f = dfs(s, INT_MAX)) {  // 优化
            memset(vis, false, sizeof vis);
            maxflow += f, mincost += f * d[s];
        }
    }
    printf("%d %d\n", maxflow, mincost);
    return 0;
}

Dijkstra + Ek 版

时间复杂度：
对 Dijkstra算法 的修改主要借鉴 Johnson算法
算法流程：

1. 在费用流中，第一次跑最短路是没有负边的所以第一次可以用 Dijkstra算法。

2. 在跑第 遍最短路时：
   存储上一次的最短路， ，若 是增广路的一部分，则 ，所以在残余网络中建的反边也满足 ，我们定义边的新权值 ，这样就不存在负边了，接着跑 Dijkstra 就行，而跑出的结果 例如：
   
   
   
   
   其中， 为真实最短路，记为 , 且 。
   所以，
   所以 为本次最短路

注： Dijkstra 算法已做修改，也可以跑负边（类似 spfa 的思路）。

//  洛谷 板子题（https://www.luogu.com.cn/problem/P3381）！！开了 O2 快的起飞
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+1;
const int maxm = 1e5+1;
typedef pair<int,int> pr;

struct edge{
    int to, next, cap, flow, cost;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, d[maxn], flow[maxn], pre[maxn], h[maxn];

void addedge(int u, int v, int w, int c) {
    e[++tot] = {v, head[u], w, 0,  c}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0, -c}, head[v] = tot;
}

bool Dijkstra() {  // 修改过的 Dijkstra 可以用类似 spfa 的方法跑负边
    memset(d, 0x7f, sizeof d);
    memset(flow, 0, sizeof flow);
    priority_queue<pr, vector<pr>, greater<pr> > q;
    flow[s] = INT_MAX;
    q.push({ d[s] = 0, s });
    while(!q.empty()) {
        int x = q.top().second, val = q.top().first;
        q.pop();
        if (d[x] < val) continue;  // 没有负边时就是 Dijkstra
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] > d[x] + e[i].cost + h[x] - h[j] && e[i].cap > e[i].flow) {
                flow[j] = min(flow[x], e[i].cap - e[i].flow), pre[j] = i;
                q.push({d[j] = d[x] + e[i].cost + h[x] - h[j], j});
            }
        }
    }
    return flow[t];
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
        addedge(u, v, w, c);
    }
    memset(h, 0, sizeof h);
    int maxflow = 0, mincost = 0;
    while(Dijkstra()) {
        for(int i = 1; i <= n; ++ i) h[i] += d[i];
        for(int i = t; i != s; i = e[ pre[i]^1 ].to) {
            e[ pre[i] ].flow += flow[t];
            e[ pre[i]^1 ].flow -= flow[t];
        }
        maxflow += flow[t], mincost += h[t] * flow[t];
    }
    printf("%d %d\n", maxflow, mincost);
    return 0;
}

Dijkstra + Dinic 版

若费用流的0流图不存在负边（一般不存在），则可直接用 memset(h, 0, sizeof h) 初始 h函数，若存在负边（例如求最大费用最大流），则需要先跑一遍 spfa 来初始 h函数，可以把 spfa 和 Dijkstra 分开写，也可以用上个版本修改过的 Dijkstra。费用流的源点是固定的，所以可直接从源点跑 spfa。
但也可以不考虑源点，在 Johnson算法 中建立一个虚点连接所有的点，这些虚拟的边都是流量无限，费用为零的，然后从这个虚点跑 spfa 来初始 h函数，需要注意的是该方法 h[虚点] = 0，所以关于源点的 h[s] 不一定为零，即需要修改公式为 h[x] += d[x] - h[s]。
注：不用 Johnson算法 的思路就不用修改公式，还有 Johnson算法 需要按路径优化后的最短路（点x 到汇点的最短距离）来初始化 h函数

//  洛谷 板子题（https://www.luogu.com.cn/problem/P3381）！！开了 O2 快的起飞
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5001;
const int maxm = 5e4+1;

typedef pair<int,int> pr;

struct edge{
    int to, next, cap, flow, cost;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, d[maxn], h[maxn];
bool vis[maxn];

void addedge(int u, int v, int w, int c) {
    e[++tot] = {v, head[u], w, 0,  c}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0, -c}, head[v] = tot;
}

void johnson() { // 用 spfa 代替也行，初始 h 函数
    deque<int>q;
    for(int i = 1; i <= n; ++ i) { // 模拟一个虚点对所有点进行一次松弛
        h[i] = vis[i] = 0;
        q.push_back(i);
    }
    while(!q.empty()) {
        int x = q.front(); q.pop_front();
        vis[x] = false;
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (h[j] > h[x] - e[i].cost && e[i^1].cap > e[i^1].flow) {
                h[j] = h[x] - e[i].cost;
                if (!vis[j]) {
                    vis[j] = true;
                    if (!q.empty() && h[j] < h[q.front()])
                        q.push_front(j);
                    else q.push_back(j);
                }
            }
        }
    }
}

void spfa() { // 可代替 Johnson算法 初始 h函数
    memset(h, 0x7f, sizeof h);
    memset(vis, false, sizeof vis);
    deque<int> q; q.push_back(t);
    h[t] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop_front();
        vis[x] = false;
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (h[j] > h[x] - e[i].cost && e[i^1].cap > e[i^1].flow) {
                h[j] = h[x] - e[i].cost;
                if (!vis[j]) {
                    vis[j] = true;
                    if (!q.empty() && h[j] < h[q.front()]) q.push_front(j);
                    else q.push_back(j);
                }
            }
        }
    }
}


bool Dijkstra() { // 纯正的 Dijkstra算法 （跑不了负边）
    memset(d, 0x7f, sizeof d);
    memset(vis, false, sizeof vis);
    priority_queue<pr, vector<pr>, greater<pr> > q;
    q.push({ d[t] = 0, t });  // 路径优化，从 t 开跑
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (!vis[j] && d[j] > d[x] - e[i].cost + h[x] - h[j] && e[i^1].cap > e[i^1].flow) {
                q.push({d[j] = d[x] - e[i].cost + h[x] - h[j], j});
            }
        }
        h[x] += d[x] - h[t];  // 累加为当前最短路，所以该点不能再用于后续松弛操作
    }
    return vis[s];
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
    vis[x] = false;
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (vis[j] && h[x] - e[i].cost == h[j] && e[i].cap > e[i].flow) {
            f = dfs(j, min(e[i].cap - e[i].flow, flow - used));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    return used;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
        addedge(u, v, w,  c);
    }
    int maxflow = 0, mincost = 0;
    johnson(); // 若初始网络无负边简单清空 h 函数即可, memset(h, 0, sizeof h);
    while(Dijkstra()) {
        while(int f = dfs(s, INT_MAX)) {
            memset(vis, true, sizeof vis);
            maxflow += f, mincost += f * h[s];
        }
    }
    printf("%d %d\n", maxflow, mincost);
    return 0;
}

zkw 费用流

利用了 KM 算法中顶标的方法，当一条边的费用为零时，该边是可用的，增边的方法就是按最小代价（一定能扩展出一条边）降低所有标记点的所有边的费用，增加反边的费用。
算法流程：多次dfs用增广直到找不到一条增广路为止，用一个vis数组记录下最后一次增广过程中经过的点，再以最小代价扩增一条新边，然后接着回去dfs增广，重复这个过程，直到无法扩增一条新边为止。
注： 该方法是用 km算法 中顶标的思路模拟出 DIjkstra 的过程，所以若初始图中有负边的情况，该方法失效！！！

//  洛谷 板子题（https://www.luogu.com.cn/problem/P3381）
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5001;
const int maxm = 5e4+1;

struct edge{
    int to, next, cap, flow, cost;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t;
bool vis[maxn];

void addedge(int u, int v, int w, int c) {
    e[++tot] = {v, head[u], w, 0,  c}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0, -c}, head[v] = tot;
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
    vis[x] = true;
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to;
        if (!vis[j] && e[i].cost == 0 && e[i].cap > e[i].flow) {
            int f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    return used;
}

void zkw() {
    int maxflow = 0, mincost = 0, f, co = 0;
    while(1) {
        memset(vis, false, sizeof vis);
        while(f = dfs(s, INT_MAX)) {
            memset(vis, false, sizeof vis);
            maxflow += f, mincost += f * co;
        }
        int dis = INT_MAX;
        for(int x = 1; x <= n; ++ x) {
            if (vis[x]) {
                for(int i = head[x]; ~i; i = e[i].next) {
                    if (e[i].cap > e[i].flow && !vis[ e[i].to ]) {
                        dis = min(e[i].cost, dis);
                    }
                }
            }
        }
        if (dis == INT_MAX) break;  // 无可添加的新边
        for(int x = 1; x <= n; ++ x) {
            if (vis[x]) {
                for(int i = head[x]; ~i; i = e[i].next) {
                    e[i].cost -= dis, e[i^1].cost += dis;
                }
            }
        }
        co += dis; // 累加费用
    }
    printf("%d %d\n", maxflow, mincost);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
        addedge(u, v, w, c);
    }
    zkw();
    return 0;
}

变种最短路

对于 spfa 来说不管是什么图，都可以跑最短路或最长路，但对于 Dijkstra 来说它只能在不管经过哪条边都是累增的图上跑最短路，或者是不管经过哪条边都是累降的图上跑最长路（累降图求最长路都可以转换为累增图求最短路）。
而一般图的最短路是累加得到的，若图中所有边权全为正，则可以用 Dijkstra 求最短路，若图中所有边权全为负，则可以用 Dijkstra 求最长路（可以边权取反跑最短路），比较特殊一点的图是累乘的得到的，若图中所有边权都大于1，则可以用 Dijkstra 求最短路，若图中所有边权都小于1且大于0，则可以用 Dijkstra 求最长路（可以边权取倒数跑最短路）

Johnson 算法

若是累加最短路，上面 Dijkstra + EK 版已经证明过了。
若是累乘最短路，Dijkstra魔改 证：

1. 在费用流中，在第一次跑最短路是没有边权小于 1 的边存在，所以第一次可以用 Dijkstra 算法
2. 在跑第 遍最短路时：
   存储上一次的最短路， ，若 是增广路的一部分，则 ，所以在残余网络中间把边取倒数也满足 ，我们定义边的新权值 ，这样就不存在边权是小于 1 的了，接着跑 Dijkstra 就行， 而跑出的结果 例如：
   
   
   
   
   其中， 为真实最短路，记为 ，且 。
   所以，
   所以 为本次最短路

注：h 函数初始为 1.0，若开始图中存在边权小于 1 的边，则用 spfa 初始 h函数。

zkw费用流 版

P2410 【[SDOI2009]最优图像】 （https://www.luogu.com.cn/problem/P2410）
网络流行列的经典模型 + 变种最短路（累乘）。
建图：

1. 行号标记序号为 1~n 的点，列号标记序号为 1+n ~ n+m 的点，源点 s 标记序号为 n+m+1 的点，汇点 t 标记序号为 n+m+2 的点。
2. 从每一行向每一列连一条边，容量为 1，费用为 p[i][j] * 0.01.
3. 从源点 s 向每一行连一条边，容量为 a[i]，费用为 1.00.
4. 从每一列向汇点 t 连一条边，容量为 b[j]，费用为 1.00.

思路：
简单来说，zkw费用流是用 km算法 里顶标的概念去模拟跑一边 Dijkstra，所以做题的关键是找对贪心方法，怎么做呢？首先我们要一个累增的跑法，而题目要求一个边权全小于 1 的最长路，我们把每个边都取它的倒数，这样边权就都是 val >= 1 的，所以累乘起来就是累增的，所以建完图就可以直接用 zkw费用流 了。

注意：与累加不同的是边权为 val = 1.0 是该边已被扩展的标志。

// 络谷 （https://www.luogu.com.cn/problem/solution/P2410）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int maxm = 1e6+1;
const double eps = 1e-6;

struct edge{
    int to, next, cap, flow; double cost; edge(){}
    edge(int to, int next, int cap, int flow, double cost): to(to), next(next), cap(cap), flow(flow), cost(cost) {}
}e[maxm]; int head[maxn], tot;
int n, m, s, t, graph[maxn][maxn];
bool vis[maxn];

void addedge(int u, int v, int w, double c) {
    e[++tot] = edge(v, head[u], w, 0, 1.0 / c), head[u] = tot;
    e[++tot] = edge(u, head[v], 0, 0, c), head[v] = tot;
}

void init() {
    memset(head, -1, sizeof head), tot = -1;
    s = n + m + 1, t = n + m + 2;
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
    vis[x] = true;
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (!vis[j] && fabs(e[i].cost - 1) <= eps && e[i].cap > e[i].flow) {
            f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    return used;
}

void zkw() {
    while(1) {
        memset(vis, false, sizeof vis);
        while(dfs(s, INT_MAX)) {
            memset(vis, false, sizeof vis);
        }
        double dis = DBL_MAX;
        for(int x = 1; x <= s; ++ x) {
            if (!vis[x]) continue;
            for(int i = head[x]; ~i; i = e[i].next) {
                if (e[i].to == t) continue;
                if (e[i].cap > e[i].flow && !vis[e[i].to]) {
                    dis = min(dis, e[i].cost);
                }
            }
        }
        if (fabs(dis - DBL_MAX) <= eps) return ;

        for(int x = 1; x <= s; ++ x) {
            if (!vis[x]) continue;
            for(int i = head[x]; ~i; i = e[i].next) {
                if (e[i].to == t) continue;
                e[i].cost /= dis, e[i^1].cost *= dis;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            int c; scanf("%d", &c);
            if (c) addedge(i, j + n, 1, c * 0.01);
        }
    }
    for(int i = 1; i <= n; ++ i) {
        int w; scanf("%d", &w);
        addedge(s, i, w, 1.0);
    }
    for(int j = 1; j <= m; ++ j) {
        int w; scanf("%d", &w);
        addedge(j + n, t, w, 1.0);
    }
    zkw();  
    for(int x = 1; x <= n; ++ x) {
        for(int i = head[x]; ~i; i = e[i].next) {
            if (e[i].cap == 1 && e[i].flow == 1) {
                graph[x][ e[i].to - n ] = 1;
            }
        }
    }
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            printf("%d", graph[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Dijkstra魔改 版

此题 zkw 是正解，但用 Dijkstra魔改 版跑的更快。
同样的把边权都取倒数，用 Dijkstra魔改 跑最短路即可。
除了使用 Dijkstra 来优化最短路外，还要用一些优化，比如，

1. 路径优化，最短路从 t 开始跑，在 dfs 时可以省去无效的搜索。
2. 剪枝优化，当一个点的所有渠道的容量都流满时，可以省去后序对该点的搜索。

// 络谷 （https://www.luogu.com.cn/problem/solution/P2410）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int maxm = 1e6+1;

struct edge {
    int to, next, cap, flow; double cost; edge(){}
    edge(int to, int next, int cap, int flow, double cost): to(to), next(next), cap(cap), flow(flow), cost(cost){}
}e[maxm]; int head[maxn], tot;
int n, m, s, t, graph[maxn][maxn];
double d[maxn], h[maxn];
bool vis[maxn];

void addedge(int u, int v, int w, double c) {
    e[++tot] = edge(v, head[u], w, 0, 1.0/c), head[u] = tot;
    e[++tot] = edge(u, head[v], 0, 0, c    ), head[v] = tot;
}

bool Dijkstra() {
    memset(d, 0x7f, sizeof d);
    memset(vis, false, sizeof vis);
    priority_queue< pair<double,int>, vector< pair<double,int> >, greater< pair<double,int> > > q;
    q.push({d[t] = 1.0, t});  // 路径优化，最短路为从 x 点到 t点的最短路
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (!vis[j] && d[j] > d[x] * e[i^1].cost * h[x] / h[j] && e[i^1].cap > e[i^1].flow) {
                q.push({ d[j] = d[x] * e[i^1].cost * h[x] / h[j], j });
            }
        }
        h[x] *= d[x];  // 更新次最短路后，该点就不能参与后序的松弛
    }
    return vis[s];
}

int dfs(int x, int flow, int used = 0) {
    if (x == t) return flow;
    vis[x] = false;
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        int j = e[i].to, f;
        if (vis[j] && fabs(h[x] - h[j] * e[i].cost) <= 0.000001 && e[i].cap > e[i].flow) {
            f = dfs(j, min(flow - used, e[i].cap - e[i].flow));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    if (used) vis[x] = true; // 剪枝优化
    return used;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof head), tot = -1;
    s = n + m + 1, t = n + m + 2;
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            int x; scanf("%d", &x);
            if (x) addedge(i, j+n, 1, x*0.01);
        }
    }
    for(int i = 1; i <= n; ++ i) {
        int x; scanf("%d", &x);
        addedge(s, i, x, 1.0);
    }
    for(int i = 1; i <= m; ++ i) {
        int x; scanf("%d", &x);
        addedge(i+n, t, x, 1.0);
    }
    for(int i = 1; i <= t; ++ i) h[i] = 1.0; // 初始 h 函数
    while(Dijkstra()) dfs(s, INT_MAX);
    for(int x = 1; x <= n; ++ x) {
        for(int i = head[x]; ~i; i = e[i].next) {
            if (e[i].cap == 1 && e[i].flow == 1) {
                graph[x][ e[i].to-n ] = 1;
            }
        }
    }
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            printf("%d", graph[i][j]);
        }
        printf("\n");
    }
    return 0;
}