这是我最大流模板的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[1010], d[1010], qq[1010], qb[1010];
int w[1010], hsh[1005];
struct node{
	int v, c, id;
};
vector<node> G[1005];
int ans, mxf, ttmp;
int m, n, s, t, u, mn, hj;
bool fl;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++){
    	int u, v, c, fl = 0;
    	cin >> u >> v >> c;
    	G[u].push_back({v, c, G[v].size()});
    	G[v].push_back({u, 0, G[u].size()});
	}
    hsh[0] = n;
    for (int i = 1; i <= n; i++)
		p[i] = 1;
    u = s;
    mxf = INT_MAX;
    while (d[s] < n){
        w[u] = mxf;
        fl = 0;
        for (int i = 0; i < G[u].size(); i++){
        	auto tmp = G[u][i];
        	int v = tmp.v, c = tmp.c, id = tmp.id;
        	if (v < p[u])
        		continue;
            if (c > 0 && d[u] == d[v] + 1){
                fl = 1;
                p[u] = v;
                if (c < mxf)
					mxf = c;
                qq[v] = u;
                qb[v] = i;
                u = v;
                if (u == t){
                    ans += mxf;
                    while (u != s){
                        ttmp = u;
                        u = qq[u];
                        G[u][qb[ttmp]].c -= mxf;
                        G[ttmp][G[u][qb[ttmp]].id].c += mxf;
                    }
                    mxf = INT_MAX;
                }
                break;
            }
        }
        if (fl)
			continue;
        mn = n - 1;
        for (auto tmp : G[u])
            if (tmp.c && d[tmp.v] < mn)
                hj = tmp.v, mn = d[tmp.v];
        p[u] = hj;
        hsh[d[u]]--;
        if (!hsh[d[u]])
			break;
        d[u] = mn + 1;
        hsh[d[u]]++;
        if (u != s){
        	u = qq[u];
        	mxf = w[u];
		}
    }
    cout << ans;
}

可以发现只得了 76 分而且样例都过不了。

但是套到这道题能过。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[10010], d[10010], qq[10010], qb[10010];
int w[10010], hsh[10005];
struct node{
	int v, c, id;
};
vector<node> G[10005];
int ans, mxf, ttmp;
int m, n, s, t, u, mn, hj;
bool fl;
void add(int u, int v, int c){
	G[u].push_back({v, c, G[v].size()});
	G[v].push_back({u, 0, G[u].size()});
}
void sap(){
	hsh[0] = n;
    for (int i = 1; i <= n; i++)
		p[i] = 1;
    u = s;
    mxf = INT_MAX;
    while (d[s] < n){
        w[u] = mxf;
        fl = 0;
        for (int i = 0; i < G[u].size(); i++){
        	auto tmp = G[u][i];
        	int v = tmp.v, c = tmp.c, id = tmp.id;
        	if (v < p[u])
        		continue;
            if (c > 0 && d[u] == d[v] + 1){
                fl = 1;
                p[u] = v;
                if (c < mxf)
					mxf = c;
                qq[v] = u;
                qb[v] = i;
                u = v;
                if (u == t){
                    ans += mxf;
                    while (u != s){
                        ttmp = u;
                        u = qq[u];
                        G[u][qb[ttmp]].c -= mxf;
                        G[ttmp][G[u][qb[ttmp]].id].c += mxf;
                    }
                    mxf = INT_MAX;
                }
                break;
            }
        }
        if (fl)
			continue;
        mn = n - 1;
        for (auto tmp : G[u])
            if (tmp.c && d[tmp.v] < mn)
                hj = tmp.v, mn = d[tmp.v];
        p[u] = hj;
        hsh[d[u]]--;
        if (!hsh[d[u]])
			break;
        d[u] = mn + 1;
        hsh[d[u]]++;
        if (u != s){
        	u = qq[u];
        	mxf = w[u];
		}
    }
    cout << ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	s = n * m + 1;
	t = n * m + 2;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			int vl;
			cin >> vl;
			if (vl == 1)
				add(s, (i - 1) * m + j, 11451419);
			else if (vl == 2)
				add((i - 1) * m + j, t, 11451419);
			if (j != 1)
				add((i - 1) * m + j, (i - 1) * m + j - 1, 1);
			if (j != m)
				add((i - 1) * m + j, (i - 1) * m + j + 1, 1);
			if (i != 1)
				add((i - 1) * m + j, (i - 2) * m + j, 1);
			if (i != n)
				add((i - 1) * m + j, i * m + j, 1);
		}
	n = n * m + 2;
	sap();
}

这就幽默了。