P3376 【模板】网络最大流

因为只是一道模板题，不涉及建图这里就不展开介绍。

$sap$ 实现最大流，不会的可以参考这篇文章用上了弧优化以及 $gap$ 优化。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 200 + 7;
const int M = 5e3 + 7;

struct Node {
    int flow;
    int v, next;
};
struct Map {
    int head[N], tot, cur[N];
    Node edge[M << 1];
    void init() { ms(head, -1); tot = 1; }
    void add(int u, int v, int flow) {
        edge[++tot].v = v; edge[tot].flow = flow; edge[tot].next = head[u]; head[u] = tot;
        edge[++tot].v = u; edge[tot].flow = 0; edge[tot].next = head[v]; head[v] = tot;
    }
}G1;
int n, m;/*改数组大小！！*/
int be, ed;

queue<int> q;
int dep[N], gap[N];
ll maxflow;
void bfs() {
    ms(dep, -1); ms(gap, 0);
    dep[ed] = 0;
    gap[0] = 1;
    q.push(ed);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v;
            if (dep[v] == -1) {
                dep[v] = dep[u] + 1;
                ++gap[dep[v]];
                q.push(v);
            }
        }
    }
}

int dfs(int u, int flow) {
    if (u == ed) {
        maxflow += flow;
        return flow;
    }
    int used = 0;
    for (int i = G1.cur[u]; ~i; i = G1.edge[i].next) {
        G1.cur[u] = i;
        int v = G1.edge[i].v, w = G1.edge[i].flow;
        if (dep[v] + 1 == dep[u] and w > 0) {
            int d = dfs(v, min(flow - used, w));
            if (d > 0) {
                G1.edge[i].flow -= d;
                G1.edge[i ^ 1].flow += d;
                used += d;
            }
            if (used == flow)    return used;
        }
    }
    --gap[dep[u]];
    if (!gap[dep[u]])    dep[be] = n + 1;
    ++dep[u];
    ++gap[dep[u]];
    return used;
}

void sap() {
    bfs();
    while (dep[be] < n) { // n 一定要是整个网络流中全部点的数量
        memcpy(G1.cur, G1.head, sizeof G1.head);
        dfs(be, INF);
    }
}

void solve() {
    G1.init();
    n = read(), m = read(), be = read(), ed = read();
    rep(i, 1, m) {
        int u = read(), v = read(), flow = read();
        G1.add(u, v, flow);
    }
    sap();
    print(maxflow);
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        solve();
    }
    return 0;
}

P3381 【模板】最小费用最大流

求解增广路的时候用 $spfa$ 替换掉 $bfs$ 即可求解到最小费用，同理求解最大费用的时候把原图中输入的费用取相反数，再跑最短路，求解到最小费用后取个负号就是最大费用了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 5e3 + 7;
const int M = 5e4 + 7;

struct Node {
    int flow, cost;
    int v, next;
};
struct Map {
    int head[N], tot, cur[N];
    Node edge[M << 1];
    void init() { ms(head, -1); tot = 1; }
    void add(int u, int v, int flow, int cost) {
        edge[++tot].v = v; edge[tot].flow = flow; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot;
        edge[++tot].v = u; edge[tot].flow = 0; edge[tot].cost = -cost; edge[tot].next = head[v]; head[v] = tot;
    }
}G1;
int n, m;/*改数组大小！！*/
int be, ed;
int maxflow, mincost;

queue<int> q;
bool vis[N];
int flow[N], cost[N], id[N], pre[N];

bool spfa() {
    ms(vis, 0); ms(flow, 0x3f); ms(cost, 0x3f);
    q.push(be);
    vis[be] = 1, cost[be] = 0, pre[ed] = -1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v;
            if (G1.edge[i].flow > 0 and cost[v] > cost[u] + G1.edge[i].cost) {
                cost[v] = cost[u] + G1.edge[i].cost;
                pre[v] = u;
                id[v] = i;
                flow[v] = min(flow[u], G1.edge[i].flow);
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return pre[ed] != -1;
}

void mcmf() {
    while (spfa()) {
        int now = ed;
        maxflow += flow[ed];
        mincost += flow[ed] * cost[ed];
        while (now != be) {
            G1.edge[id[now]].flow -= flow[ed];
            G1.edge[id[now] ^ 1].flow += flow[ed];
            now = pre[now];
        }
    }
}

void solve() {
    G1.init();
    n = read(); m = read(); be = read(), ed = read();
    rep(i, 1, m) {
        int u = read(), v = read(), flow = read(), dis = read();
        G1.add(u, v, flow, dis);
    }
    mcmf();
    printf("%d %d\n", maxflow, mincost);
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        solve();
    }
    return 0;
}

下面的篇幅是洛谷网络流 $24$ 题的建图过程，下面大部分篇幅将会只对题目进行建模， $sap$ 和 $mcmf$ 的代码就不一直重复给出了。

1/24 飞行员配对方案问题

给出的关系之间建立有向边，边权为 $1$ 。

建立超级源点 $(0)$ 和超级汇点 $(n+1)$ ，分别向图中 $n$ 个点连边，边权为 $1$ ，跑最大流即可。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 200 + 7;
const int M = 5e3 + 7;

struct Node {
    int flow;
    int v, next;
};
struct Map {
    int head[N], tot, cur[N];
    Node edge[M << 1];
    void init() { ms(head, -1); tot = 1; }
    void add(int u, int v, int flow) {
        edge[++tot].v = v; edge[tot].flow = flow; edge[tot].next = head[u]; head[u] = tot;
        edge[++tot].v = u; edge[tot].flow = 0; edge[tot].next = head[v]; head[v] = tot;
    }
}G1;
int n, m;/*改数组大小！！*/
int be, ed;

queue<int> q;
int dep[N], gap[N];
ll maxflow;
void bfs() {
    ms(dep, -1); ms(gap, 0);
    dep[ed] = 0;
    gap[0] = 1;
    q.push(ed);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v;
            if (dep[v] == -1) {
                dep[v] = dep[u] + 1;
                ++gap[dep[v]];
                q.push(v);
            }
        }
    }
}

int dfs(int u, int flow) {
    if (u == ed) {
        maxflow += flow;
        return flow;
    }
    int used = 0;
    for (int i = G1.cur[u]; ~i; i = G1.edge[i].next) {
        G1.cur[u] = i;
        int v = G1.edge[i].v, w = G1.edge[i].flow;
        if (dep[v] + 1 == dep[u] and w > 0) {
            int d = dfs(v, min(flow - used, w));
            if (d > 0) {
                G1.edge[i].flow -= d;
                G1.edge[i ^ 1].flow += d;
                used += d;
            }
            if (used == flow)    return used;
        }
    }
    --gap[dep[u]];
    if (!gap[dep[u]])    dep[be] = n + 1;
    ++dep[u];
    ++gap[dep[u]];
    return used;
}

void sap() {
    bfs();
    while (dep[be] < n) { // n 一定要是整个网络流中全部点的数量
        memcpy(G1.cur, G1.head, sizeof G1.head);
        dfs(be, INF);
    }
}

void solve() {
    G1.init();
    m = read(); n = read();
    int u, v;
    while (~scanf("%d %d", &u, &v)) {
        if (u == -1 and v == -1)    break;
        G1.add(u, v, 1);
        G1.add(v, u, 0);
    }
    be = 0, ed = n + 1;
    rep(i, 1, m)    G1.add(be, i, 1);
    rep(i, m + 1, n)    G1.add(i, ed, 1);
    n = n + 2;
    sap();
    print(maxflow);
    for (int i = 2; i <= G1.tot; i += 2) {
        int u = G1.edge[i ^ 1].v;
        int v = G1.edge[i].v;
        if (u == be or u == ed or v == be or v == ed)    continue;
        if (G1.edge[i ^ 1].flow != 0) {
            printf("%d %d\n", u, v);
        }
    }
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        solve();
    }
    return 0;
}

2/24 负载平衡问题

建立一个源点 $(0)$ 和汇点 $(n+1)$ 。

首先求合得到 $n$ 个仓库最终会留下的平均值 $avg$ 。

对于 $a_i>avg$ 的仓库来说，把它和汇点连边。流量是 $a_i-avg$ 相当于去掉了多余的部分，费用为 $0$ 。

对于 $a_i<avg$ 的仓库来说，把它和源点连边。流量是 $avg-a_i$ ，费用为 $0$ 。

相邻仓库之间建立流量为 $INF$ ，费用为 $1$ 的边。这样直接跑最小费用最大流就是结果了。

下面我们对正确性进行概述，我们建立的源点汇点图，源点流出的流量一定会等于汇点流入的流量，那么每个仓库流入汇点的弧一定是饱和弧。而且花费只会在仓库之间产生，并且费用是 $1$ ，就是我们要搬运的数量，那么最小费用保证了它的最小性，所以该构造方法成立。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 100 + 7;
const int M = N * N + 7;

struct Node {
    int flow, cost;
    int v, next;
};
struct Map {
    int head[N], tot, cur[N];
    Node edge[M << 1];
    void init() { ms(head, -1); tot = 1; }
    void add(int u, int v, int flow, int cost) {
        edge[++tot].v = v; edge[tot].flow = flow; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot;
        edge[++tot].v = u; edge[tot].flow = 0; edge[tot].cost = -cost; edge[tot].next = head[v]; head[v] = tot;
    }
}G1;
int n, m;/*改数组大小！！*/
int be, ed;
int maxflow, mincost;

queue<int> q;
bool vis[N];
int flow[N], cost[N], id[N], pre[N];

bool spfa() {
    ms(vis, 0); ms(flow, 0x3f); ms(cost, 0x3f);
    q.push(be);
    vis[be] = 1, cost[be] = 0, pre[ed] = -1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v;
            if (G1.edge[i].flow > 0 and cost[v] > cost[u] + G1.edge[i].cost) {
                cost[v] = cost[u] + G1.edge[i].cost;
                pre[v] = u;
                id[v] = i;
                flow[v] = min(flow[u], G1.edge[i].flow);
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return pre[ed] != -1;
}

void mcmf() {
    while (spfa()) {
        int now = ed;
        maxflow += flow[ed];
        mincost += flow[ed] * cost[ed];
        while (now != be) {
            G1.edge[id[now]].flow -= flow[ed];
            G1.edge[id[now] ^ 1].flow += flow[ed];
            now = pre[now];
        }
    }
}

int a[N];
void solve() {
    G1.init();
    n = read(); be = 0, ed = n + 1;
    int sum = 0;
    rep(i, 1, n)    a[i] = read(), sum += a[i];
    int avg = sum / n;
    rep(i, 1, n) {
        if (a[i] < avg)
            G1.add(be, i, avg - a[i], 0);
        else if (a[i] > avg)
            G1.add(i, ed, a[i] - avg, 0);
        if (i == 1) {
            G1.add(1, n, INF, 1);
            G1.add(n, 1, INF, 1);
        }
        else {
            G1.add(i, i - 1, INF, 1);
            G1.add(i - 1, i, INF, 1);
        }
    }
    mcmf();
    printf("%d\n", mincost);
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        solve();
    }
    return 0;
}

3/24 软件补丁问题

虚假的网络流，状压加上最短路即可通过。

使用二进制进行压缩之后，只有 $b1$ 全为 $1$ ， $b2$ 全为 $0$ 才可以使用这条路。

使用之后起点的 $f1$ 全部变成 $0$ ， $f2$ 全部变成 $1$ 就成了终点。

const int N = 20 + 1;
const int M = 100 + 7;
struct Node {
    int t;
    int b1, b2, f1, f2;
}p[N];
ll n, m;
char s[N];
int be, ed;

bool vis[1 << N];
int dis[1 << N];
priority_queue<pai, vector<pai>, greater<pai>> pq;
void dijkstra() {
    ms(dis, 0x3f);
    dis[be] = 0;
    pq.push({ 0,be });
    while (pq.size()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        rep(i, 1, m) {
            if ((u & p[i].b1) == p[i].b1 and !(u & p[i].b2)) {
                int v = ((u | p[i].f1) ^ p[i].f1) | p[i].f2;
                if (dis[v] > dis[u] + p[i].t) {
                    dis[v] = dis[u] + p[i].t;
                    pq.push({ dis[v],v });
                }
            }
        }
    }
}

void solve() {
    n = read(), m = read();
    rep(i, 1, m) {
        p[i].t = read();
        scanf("%s", s);
        rep(j, 0, n - 1) {
            if (s[j] == '+')    p[i].b1 |= 1 << j;
            else if (s[j] == '-')    p[i].b2 |= 1 << j;
        }
        scanf("%s", s);
        rep(j, 0, n - 1) {
            if (s[j] == '-')    p[i].f1 |= 1 << j;
            else if (s[j] == '+')    p[i].f2 |= 1 << j;
        }
    }
    be = (1 << n) - 1; ed = 0;
    dijkstra();
    if (dis[ed] == INF) print(0);
    else print(dis[ed]);
}

4/24 魔术球问题

反向思考+拆点+最大流。

首先对于这样的一个问题，如果正向思考，给你 $n$ 根柱子，你还是要回归到用球去堆满它的问题上。所以我们换个方向，如果给你球的数量，你可以回答我一共需要几个柱子吗？

这个问题显然比原题问题更加简单。首先设计堆放操作，考虑拆点，把每个小球拆成 $2$ 个点。左边用来和源点连接，右边用来和汇点连接。左边编号为 $2*i$ ，右边编号为 $2*i+1$ (如果是第 $i$ 个小球的话)。

那么可以堆积的小球，也就是我们枚举到的第 $i$ 号球，找一个 $1\to i-1$ 的 $j$ ，满足 $i+j$ 是完全平方数。

对于这样的 $i,j$ 进行连边，流量是 $1$ ，源点和汇点流出和流入的流量也是 $1$ 。

这样跑最大流就可以知道我们加入当前这个球之后我们最少要几个柱子。

最后一个问题，如何保证我们每次放球都是在最顶上呢？这个问题是显然的，我们每次求解最大流之后，边的情况并不会改变，也就是之前是饱和弧的现在依旧是饱和。我们又是顺序枚举的 $i$ ，每次添加点进去一定是新开柱子或者保持原先的柱子数量。

如果保留边权流量之后，下一次求解最大流发现流动不了，说明这个球并不能顺利去到汇点，只能新开一个柱子给它了。

bool vis[N];
void display(int u) {
    for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
        int v = G1.edge[i].v;
        if (v == be or v == ed or G1.edge[i].flow or vis[v / 2])    continue;
        printf("%d ", v / 2);
        vis[v / 2] = 1;
        display(v / 2 * 2);
    }
}

void solve() {
    G1.init();
    n = read();
    be = 0, ed = 1;
    cnt = 2;
    // 小球编号 2 3 ...
    int now = 0;
    deque<int> ans;
    while (ans.size() <= n) {
        ++now;
        G1.add(be, now * 2, 1);
        G1.add(now * 2 + 1, ed, 1);
        cnt += 2;
        for (int i = sqrt(now) + 1; i * i < 2 * now; ++i) {
            G1.add((i * i - now) * 2, now * 2 + 1, 1);
        }
        sap();
        if (!maxflow)    ans.push_back(now);
    }
    --now;
    ans.pop_back();
    print(now);
    while (ans.size()) {
        int u = ans.front();
        ans.pop_front();
        printf("%d ", u);
        vis[u] = 1;
        display(u * 2);
        puts("");
    }
}

5/24 孤岛营救问题

虚假的网络流，状压+ $bfs$ 即可过。

用的 $map$ 存储地图信息和钥匙信息。

const int N = 11;
struct Node {
    int x, y, step, statu;
};
int n, m, p;
map<pai, map<pai, int>> mp;
map<pai, vector<int>> key;
bool vis[N][N][1 << N];
queue<Node> q;

int bfs() {
    int be = 0;
    for (auto& bit : key[{1, 1}])
        be |= 1 << bit;
    vis[1][1][be] = 1;
    q.push({ 1,1,0,be });
    while (q.size()) {
        auto [x, y, step, statu] = q.front();
        q.pop();
        if (x == n and y == m)    return step;
        rep(i, 0, 3) {
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if (dx <1 or dx >n or dy < 1 or dy > m)    continue;
            if (mp.count({ dx,dy })) {
                auto& now = mp[{dx, dy}];
                if (now.count({ x,y })) {
                    int tmp = mp[{dx, dy}][{x, y}];
                    if (tmp == -1)    continue;  // 墙
                    if (!(statu & (1 << tmp)))    continue; // 还没钥匙
                }
            }
            int dstatu = statu;
            for (auto& bit : key[{dx, dy}])
                dstatu |= 1 << bit;
            if (vis[dx][dy][dstatu])    continue;
            vis[dx][dy][dstatu] = 1;
            q.push({ dx,dy,step + 1,dstatu });
        }
    }
    return -1;
}

void solve() {
    n = read(), m = read(), p = read();
    int k = read();
    rep(i, 1, k) {
        pai x = { read(),read() };
        pai y = { read(),read() };
        mp[x][y] = mp[y][x] = read() - 1;
    }
    int s = read();
    rep(i, 1, s) {
        pai x = { read(),read() };
        key[x].push_back(read() - 1);
    }
    print(bfs());
}

6/24 汽车加***驶问题

分层图+最小费用。

层： $0\to k$ ，第 $i$ 层代表还剩下 $k$ 的油，每层 $n*n$ 个节点。
节点：
1. 第 $f$ 层的 $\{i,j\}$ 格子，我们编号为 $f*101*101+i*101+j$ 。
2. 源点编号 $11*101+1$
3. 汇点编号 $11*101+2$
弧：
1. 源点向 $(k,1,1)$ 连一条流量为 $1$ 费用为 $0$ 的源边。
2. 每一层的 $(p,n,n)\ p\in[0,k]$ 都向汇点连一条流量为 $1$ 费用为 $0$ 的汇边。
3. 如果是加油站：
  1. 把每一层的 $(i,j)$ 都向第 $k$ 层的 $(i,j)$ 连边，流量为 $1$ ，费用为 $A$ 。
  2. 把第 $k$ 层的 $(i,j)$ 都向四周连边，流量为 $1$ ，费用为 $0$ 或者 $B$ 。
4. 如果不是加油站：
  1. 把每一层的 $(i,j)$ 都向第 $k$ 层的 $(i,j)$ 连边，流量为 $1$ ，费用为 $A+C$ 。
  2. 把每一层的 $(i,j)$ 都向下一层的四周连边，流量为 $1$ ，费用为 $0$ 或者 $B$ 。
最小费用最大流：
1. 最大流：1
2. 最小费用： $ans$

再思考的话，最大流始终为 $1$ ，因为我们的源边只有 $1$ 。所以分层图之后直接跑最短路也是可以求解的。

const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };

void solve() {
    G1.init();
    n = read(); k = read(); A = read(), B = read(), C = read();
    be = 11 * 101 * 101 + 1, ed = 11 * 101 * 101 + 2;

    G1.add(be, encode(k, 1, 1), 1, 0); // 源边
    rep(i, 0, k)    G1.add(encode(i, n, n), ed, 1, 0); // 汇边

    rep(i, 1, n) {
        rep(j, 1, n) {
            int have = read();

            rep(p, 0, k - 1) // 加油
                G1.add(encode(p, i, j), encode(k, i, j), 1, have ? A : A + C);

            rep(p, 0, 3) {
                int dx = i + dir[p][0], dy = j + dir[p][1];
                if (dx < 1 or dx > n or dy < 1 or dy > n)    continue;
                rep(now, have ? k : 1, k) // 向四周移动
                    G1.add(encode(now, i, j), encode(now - 1, dx, dy), 1, p >> 1 ? B : 0);
            }
        }
    }
    mcmf();
    printf("%d\n", mincost);
}

7/24 圆桌问题

最大流+输出方案。

节点：
1. 源点 $(0)$
2. 汇点 $(n+m+1)$
3. 单位节点 $(1\to n)$
4. 餐桌节点 $(n+1\to n+m)$
弧：
1. 源点向全部单位连流量为单位人数的边。
2. 全部餐桌向汇点连流量为餐桌容量的边。
3. 每个单位都向每个餐桌连流量为 $1$ 的边。
最大流：

如果最大流等于单位总人数那么就输出方案。

否则输出无解。

if (maxflow != sum)    print(0);
else {
    print(1);
    rep(u, 1, n) {
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v, flow = G1.edge[i].flow;
            if (v == be or v == ed or flow)    continue;
            print(v - n, 32);
        }
        puts("");
    }
}

8/24 试题库问题

最大流+输出方案。

点：
1. 源点 $(0)$
2. 试题种类 $(1\to k)$
3. 试题编号 $(k+1\to k+n)$
4. 汇点 $(k+n+1)$
弧：
1. 源点向试题类型连边，流量为该种试题需要的数量。
2. 种类向具体编号连边，流量为 $1$ 。
3. 编号向汇点连边，流量为 $1$ 。
最大流：

如果最大流等于 $m$ ，说明有解，输出方案。

否则无解。

if (maxflow != sum)    puts("No Solution!");
else {
    rep(u, 1, k) {
        printf("%d:", u);
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v, flow = G1.edge[i].flow;
            if (v == be or v == ed or flow)    continue;
            printf(" %d", v - k);
        }
        puts("");
    }
}

9/24 最小路径覆盖问题

拆点最大流+输出方案。

点
1. 源点 $(0)$
2. 汇点 $(1)$
3. 图中节点拆点，入点 $i*2$ ，出点 $i*2+1$
弧：
1. 源点向入点连边，流量是 $1$ 。
2. 出点向汇点连边，流量是 $1$ 。
3. 有向边 $(i,j)$ 把 $i$ 的入点连向 $j$ 的出点，流量是 $1$ 。
最大流：

最大流代表着可以接在别人之后的数量。

换言之， $n-maxflow$ 就是需要的最少路径数。

输出方案可以跑反向边，一路递归找起点，并且输出一次做上标记，防止多次输出。

bool vis[N];

void display(int u) {
    if (vis[u])    return;
    print(u, 32);
    vis[u] = 1;
    for (int i = G1.head[u * 2]; ~i; i = G1.edge[i].next) {
        int v = G1.edge[i].v, flow = G1.edge[i].flow;
        if (!flow and v != be and !vis[v / 2])
            display(v / 2);
    }
}

void solve() {
    G1.init();
    n = read(), m = read();
    be = 0, ed = 1;
    rep(i, 1, n) {
        G1.add(be, i << 1, 1);
        G1.add(i << 1 | 1, ed, 1);
    }
    rep(i, 1, m) {
        int u = read(), v = read();
        G1.add(u << 1, v << 1 | 1, 1);
    }
    tot = n * 2 + 2;
    sap();
    for (int u = 1; u <= n; ++u) {
        if (!vis[u]) {
            display(u);
            puts("");
        }
    }
    print(n - maxflow);
}

10/24 分配问题

最小费用最大流+最大费用最大流。

点
1. 源点 $(0)$
2. 工人 $1\to n$
3. 工作 $n+1\to n+n$
4. 汇点 $(n*2+1)$
弧：
1. 源点向工人连边，流量是 $1$ ，费用是 $0$ 。
2. 工作向汇点连边，流量是 $1$ ，费用是 $0$ 。
3. 求解最小费用的时候把工人向工作连边，流量是 $1$ ，费用是 $a[i][j]$ 。
4. 求解最大费用的时候把工人向工作连边，流量是 $1$ ，费用是 $-a[i][j]$ 。
费用流：
1. 最小费用就是最小总收益。
2. 最大费用就是工人费用取反后求解最小费用的负数。

void solve() {
    G1.init();
    n = read();
    rep(i, 1, n) {
        rep(j, 1, n) {
            a[i][j] = read();
        }
    }

    be = 0, ed = n * 2 + 1;
    rep(i, 1, n) {
        G1.add(be, i, 1, 0);
        G1.add(i + n, ed, 1, 0);
    }
    rep(i, 1, n) {
        rep(j, 1, n) {
            G1.add(i, j + n, 1, a[i][j]);
        }
    }
    mcmf();
    int mini = mincost;
    G1.init();
    rep(i, 1, n) {
        G1.add(be, i, 1, 0);
        G1.add(i + n, ed, 1, 0);
    }
    rep(i, 1, n) {
        rep(j, 1, n) {
            G1.add(i, j + n, 1, -a[i][j]);
        }
    }
    mcmf();
    int maxi = -mincost;
    printf("%d\n%d\n", mini, maxi);
}

11/24 太空飞行计划问题

一共有 $m$ 次实验， $n$ 中仪器，仪器可以重复使用，每次实验要进行的话需要准备一些仪器才行，实验顺利完成了你会的到一定分量的金币。购买仪器需要花费一些金币，你可以理解为先欠款，只问最终收益。

最大权闭合子图不懂的同学看这里，输出方案

用起始金币之和减去求解到的最小割，就是最大权闭合子图的权值。最小割=最大流。

点
1. 源点 $(0)$
2. 实验 $1\to m$
3. 仪器 $m+1\to m+n$
4. 汇点 $(n+m+1)$
弧：
1. 源点向实验连边，流量是该实验带来的收益。
2. 仪器向汇点连边，流量是仪器的价格。
3. 实验向仪器连边，流量是无穷大。

因为这题涉及输出最小割的方案，用 $dinic$ 比较方便，它最后一次 $bfs$ 留下的深度不为你给的初值的点构成的集合就是最小割的集合。这里告诉我们，两种做法都要会，不管是 $dinic$ 还是 $sap$ ，它们两者很接近，修改起来也就几行代码不同，希望读者自行体会。

const int N = 100 + 7;
const int M = 1e6 + 7;
int n, m, tot;/*改数组大小！！*/
int be, ed;

queue<int> q;
int dep[N];
ll maxflow;
bool bfs() {
    ms(dep, -1);
    dep[be] = 0;
    q.push(be);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v, flow = G1.edge[i].flow;
            if (dep[v] == -1 and flow) { // 这里要改
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[ed] != -1;
}

int dfs(int u, int flow) {
    if (u == ed) {
        maxflow += flow;
        return flow;
    }
    int used = 0;
    for (int i = G1.cur[u]; ~i; i = G1.edge[i].next) {
        G1.cur[u] = i;
        int v = G1.edge[i].v, w = G1.edge[i].flow;
        if (dep[v] == dep[u] + 1 and w > 0) { // 这里要改
            int d = dfs(v, min(flow - used, w));
            if (d > 0) {
                G1.edge[i].flow -= d;
                G1.edge[i ^ 1].flow += d;
                used += d;
            }
            if (used == flow)    return used;
        }
    }
    return used; // 这里去掉了gap
}

void dinic() {
    while (bfs()) { // 这里要改
        memcpy(G1.cur, G1.head, sizeof G1.head);
        dfs(be, INF);
    }
}

void solve() {
    G1.init();
    ll ans = 0;
    m = read(), n = read();
    be = 0, ed = n + m + 1;
    rep(i, 1, m) {
        int cost, id;
        cin >> cost;
        ans += cost;
        string s;
        getline(cin, s);
        stringstream get(s);
        G1.add(be, i, cost);
        while (get >> id)
            G1.add(i, id + m, INF);
    }
    rep(i, 1, n)    G1.add(i + m, ed, read());
    dinic();
    ans -= maxflow;
    rep(i, 1, m)    if (dep[i] != -1)    cout << i << " ";
    cout << endl;
    rep(i, 1, n) if (dep[i + m] != -1)    cout << i << " ";
    cout << endl;
    print(ans);
}

12/24 运输问题

有 $m$ 个存储 $a_i$ 个物品的仓库， $n$ 个需要 $b_i$ 件物品的商店，给出搬运之间的花费 $c_{ij}$ ，求最小的搬运费用和最大的搬运费用。

最小费用最大流+最大费用最大流。模板照着写就行了。

int a[N], b[N], c[N >> 1][N >> 1];
void solve() {
    G1.init();
    m = read(), n = read();
    rep(i, 1, m)    a[i] = read();
    rep(i, 1, n)    b[i] = read();
    rep(i, 1, m)
        rep(j, 1, n)    c[i][j] = read();
    be = 0, ed = n + m + 1;
    rep(i, 1, m)    G1.add(be, i, a[i], 0);
    rep(i, 1, n)    G1.add(i + m, ed, b[i], 0);
    rep(i, 1, m)
        rep(j, 1, n)
        G1.add(i, j + m, INF, c[i][j]);
    mcmf();
    int mini = mincost;
    G1.init();
    rep(i, 1, m)    G1.add(be, i, a[i], 0);
    rep(i, 1, n)    G1.add(i + m, ed, b[i], 0);
    rep(i, 1, m)
        rep(j, 1, n)
        G1.add(i, j + m, INF, -c[i][j]);
    mcmf();
    int maxi = -mincost;
    printf("%d\n%d\n", mini, maxi);
}

13/24 方格取数问题

给出 $n$ 行 $m$ 列的网格，注意它题目说的是 $m*n$ 我实在叫不习惯。你要从这些网格中选择一些点权值和最大。你选出的点都要满足一个性质，那就是不能存在相邻的边。

最小割模型：二分图最大权独立集

点：
1. 源点 $(n*m+1)$
2. 汇点 $(n*m+2)$
3. 网格中的点 $(i*m+j)$
弧：
1. 源点向偶数网格连边，流量是网格的权值。偶数网格就是 $(i+j)\mod2=0$ 。
2. 奇数网格向汇点连边，流量是网格的权值。
3. 图中全部的偶数网格向相邻的奇数网格连边，边权无穷大。
最小割：

网格中全部点的权值之和减掉最小割就是我们找到的答案。

inline int encode(int i, int j) {
    return i * m + j;
}

int a[101][101];
void solve() {
    G1.init();
    n = read(), m = read();
    be = n * m + 1, ed = n * m + 2;
    int sum = 0;
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            a[i][j] = read();
            sum += a[i][j];
            if ((i + j) & 1)    G1.add(encode(i, j), ed, a[i][j]);
            else G1.add(be, encode(i, j), a[i][j]);
        }
    }
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (!((i + j) & 1)) {
                rep(k, 0, 3) {
                    int dx = i + dir[k][0], dy = j + dir[k][1];
                    if (dx < 0 or dx >= n or dy < 0 or dy >= m)    continue;
                    G1.add(encode(i, j), encode(dx, dy), INF);
                }
            }
        }
    }
    tot = n * m + 2;
    sap();
    sum -= maxflow;
    print(sum);
}

14/24 最长不下降子序列问题

给你长度为 $n$ 的序列让你求 $LIS$ 的三个相关问题。

计算 $LIS$ 的长度 $s$ 。
每个数字只能用一次的前提下，最多能拿出几个长度为 $s$ 的子序列。
如果 $a_1$ 和 $a_n$ 可以多次使用的前提下，你又能拿出多少个长度为 $s$ 的子序列。

第一问直接使用 $n\log n$ 求解一下长度，每次记录 $f_i$ 表示 $1\to i$ 的最长不下降子序列长度是多少。

第二问第三问跑网络流模型。

第二问来说，源点向 $f_i=1$ 的位置连一条流量是 $1$ 的边。

$f_i=s$ 的位置向汇点连入一条流量是 $1$ 的边，注意这个应该和上面同级，否则当你的 $s=1$ 的时候没有任何一个点向汇点连边，这显然是错误的。

接下来就是对 $i$ 和 $i$ 的后继连边，流量为 $1$ 。什么可以被叫做 $i$ 的后继？

$j>i\\a_j\ge a_i\\f_j=f_i+1$

这样的 $j$ 我们叫做 $i$ 的一个后继，我们这里 $O(n^2)$ 跑一边，找出全部的后继，连上边即可。

直接跑出最大流就是第二问的解。

第三问，解除了 $a_1$ 和 $a_n$ 的限制，那么就考虑在从源点向 $1$ 连边连入流量为无穷大的一条边，判断下 $f_n=s$ 嘛，如果等于，把 $n$ 向汇点连入一条无穷大的边。注意这里特判掉 $n=1$ 的情况，不然你就会输出你的无穷大了。

int b[N], a[N], f[N], len;
void solve() {
    G1.init();
    n = read();
    if (n == 1) {
        printf("1\n1\n1\n");
        return;
    }
    be = 0, ed = n + 1;
    rep(i, 1, n)    a[i] = read();
    f[1] = 1;
    len = 1;
    b[1] = a[1];
    int s = 1;
    rep(i, 2, n) { // 复习一下
        if (a[i] >= b[len])    b[++len] = a[i], f[i] = len;
        else {
            int pos = upper_bound(b + 1, b + 1 + len, a[i]) - b;
            b[pos] = a[i];
            f[i] = pos;
        }
        s = max(s, len);
    }
    print(s);
    rep(i, 1, n) {
        if (f[i] == 1)    G1.add(be, i, 1);
        if (f[i] == s)    G1.add(i, ed, 1); // 注意这里不能写else if
    }
    rep(i, 1, n)
        rep(j, i + 1, n)
        if (a[j] >= a[i] and f[j] == f[i] + 1)
            G1.add(i, j, 1);
    tot = n + 2;
    sap();
    print(maxflow);
    G1.add(be, 1, INF);
    if (f[n] == s)    G1.add(n, ed, INF);
    sap();
    print(maxflow);
}

15/24 最长k可重区间集问题

给出 $n(1\le n\le 500)$ 条线段，你要保证线段中每个点最多只能被覆盖 $k(1\le k\le 3)$ 次。让你求出最长的线段和。

把给出的线段左右端点进行离散。

费用流模型：流量控制

点：
1. 源点 $(0)$
2. 汇点 $(n*2+1)$
3. 线段，我们离散左右端点，每个端点拿到一个 $get\_id(l_i),get\_id(r_i)$
弧：
1. 源点通过一路向汇点连边。流量是 $k$ ，费用是 $0$ 。
2. 线段的左端点编号向右端点编号连边，流量是 $1$ ，费用是该线段长度。
最大费用：

求解最大费用就是答案。

我们这样思考，对于原先的一条直线来说，我们从源点流出的流量一定是 $k$ ，费用都是 $0$ 。

我们每找到一条增广路，都会使得某个端点流入的流量减小，这样我们就可以满足每个线段中的点使用次数不超过 $k$ ，流出主干道流量 $-1$ ，流入主干道流入 $+1$ 。

其次我们求解了最大费用，满足了最优解的情况。

vector<int> p;
int l[N], r[N];
int get_id(int x) {
    return lower_bound(all(p), x) - p.begin() + 1;
}

void solve() {
    G1.init();
    n = read(), k = read();
    rep(i, 1, n) {
        l[i] = read(), r[i] = read();
        p.push_back(l[i]);
        p.push_back(r[i]);
    }
    sort(all(p));
    p.erase(unique(all(p)), p.end());
    be = 0, ed = p.size() + 1;
    rep(i, be, ed - 1)    G1.add(i, i + 1, k, 0);
    rep(i, 1, n) {
        int len = r[i] - l[i];
        G1.add(get_id(l[i]), get_id(r[i]), 1, -len);
    }
    mcmf();
    printf("%d\n", -mincost);
}

16/24 深海机器人问题

多源点多汇点，网格最大费用问题。

二维坐标点转一维建图，每个点可以走多次，但是只花一次费用，有一个标准的模型。

我们对于图中的相邻点建立如下的两条弧即可。

$a\to b$ 流量是 $1$ ，费用是给出的边权。

$a\to b$ 流量是无穷大，费用是 $0$ 。

接下来建立超级源点和超级汇点，跑一遍 $mcmf$ 即可求解。

inline int encode(int i, int j) {
    return (i - 1) * m + j;
}
void solve() {
    G1.init();
    a = read(), b = read();
    n = read() + 1, m = read() + 1; // 注意这个是网格
    be = n * m + 1, ed = n * m + 2;
    rep(i, 1, n) {
        rep(j, 1, m - 1) {
            int tmp = read();
            G1.add(encode(i, j), encode(i, j + 1), 1, -tmp);
            G1.add(encode(i, j), encode(i, j + 1), INF, 0);
        }
    }
    rep(j, 1, m) {
        rep(i, 1, n - 1) {
            int tmp = read();
            G1.add(encode(i, j), encode(i + 1, j), 1, -tmp);
            G1.add(encode(i, j), encode(i + 1, j), INF, 0);
        }
    }
    rep(i, 1, a) {
        int k = read(), x = read() + 1, y = read() + 1;
        G1.add(be, encode(x, y), k, 0);
    }
    rep(i, 1, b) {
        int k = read(), x = read() + 1, y = read() + 1;
        G1.add(encode(x, y), ed, k, 0);
    }
    mcmf();
    printf("%d\n", -mincost);
}

17/24 骑士共存问题

把国际象棋划分成奇数点和偶数点，这样你就会发现任何一个奇数点都不会和奇数点存在冲突，冲突的只会是偶数点，那么就转换成二分图的模型了。

最小割：二分图最大独立点集

点：
1. 源点 $(0)$
2. 汇点 $(n*n+1)$
3. 奇数点 $(i+j\mod=1)$
4. 偶数点 $(i+j\mod=0)$
弧：
1. 源点向偶数点连边，流量是 $1$ 。
2. 偶数点向日字格的奇数点连边，流量是 $1$ 。
3. 奇数点向汇点连边，流量是 $1$ 。
最大流：

答案就是合法的点数减掉最小割。

const int N = 200 * 200 + 7;
const int M = 1e6 + 7;
const int dir[][2] = { {1,-2},{1,2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1} };

bool vis[207][207];
inline int encode(int i, int j) { return (i - 1) * n + j; }
void solve() {
    G1.init();
    n = read(), m = read();
    be = 0, ed = n * n + 1;
    rep(i, 1, m) {
        int x = read(), y = read();
        vis[x][y] = 1;
    }
    rep(i, 1, n) {
        rep(j, 1, n) {
            if (vis[i][j])    continue;
            if ((i + j) & 1)    G1.add(encode(i, j), ed, 1);
            else {
                G1.add(be, encode(i, j), 1);
                rep(k, 0, 7) {
                    int dx = i + dir[k][0], dy = j + dir[k][1];
                    if (dx < 1 or dx > n or dy < 1 or dy > n or vis[dx][dy])    continue;
                    G1.add(encode(i, j), encode(dx, dy), 1);
                }
            }
        }
    }
    tot = n * n - m + 2;
    sap();
    print(n * n - m - maxflow);
}

18/24 最长k可重线段集问题

这题对 $15$ 题有一点点小的改动，就是把一维的区间改为了二维的空间。

我们不难发现，其实 $y$ 轴的坐标只是用来算下距离的，没什么用，如果我们按照 $15$ 题的思路，一路往下走，如果线段离散后左右端点 $(l_i,r_i)$ 都能保证不相等的话，我们就可以得到正确的解。但是如果存在垂直于 $x$ 轴的线段，那么线段的 $l_i=r_i$ ，那么我们就会跑到负环，显然使用普通的 $spfa$ 求不到最短路。那么我们就要想办法消除这个负环。

很显然负环带给我们的是同一个 $x$ 连到了同一个点上，那么我们把 $x$ 直接扩大两倍，那么对于 $l_i=r_i$ 的线段，我们连接 $(2l_i,2l_i+1)$ 是不是就消除了自环和负环问题。但是这样对于普通的 $l_i!=r_i$ 的线段来说，如果简单连接 $(2l_i,2r_i)$ 会带来新的问题。

我们的线段是开线段，那么 $(x,x),(x,y)$ 这两个区间本质上是不相交的，但是我们上面一处理，就变成 $(2x,2x+1),(2x,2y)$ ，就有了交集，这时候我们就把 $(2x,2y)$ 改成 $(2x+1,2y)$ 就行了，因为我们每个点都扩大了两倍，所以 $2x+1$ 其实原则上和 $2x$ 等价，但是这样就避免了区间相交问题。

#define tup tuple<int, int, int>
tup p[N];
inline int calc(ll x, ll y, ll xx, ll yy) { return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy)); }
vector<ll> b;
int get_id(ll x) {
    return lower_bound(all(b), x) - b.begin() + 1;
}

void solve() {
    G1.init();
    n = read(), k = read();
    rep(i, 1, n) {
        int x = read(), y = read(), xx = read(), yy = read();
        int len = calc(x, y, xx, yy);
        x <<= 1, xx <<= 1;
        if (x == xx)    xx |= 1;
        else x |= 1;
        p[i] = { x,xx,len };
        b.push_back(x);
        b.push_back(xx);
    }
    sort(all(b));
    b.erase(unique(all(b)), b.end());
    rep(i, 1, n) {
        get<0>(p[i]) = get_id(get<0>(p[i]));
        get<1>(p[i]) = get_id(get<1>(p[i]));
    }
    be = 0, ed = b.size() + 1;
    rep(i, 0, ed - 1)    G1.add(i, i + 1, k, 0);
    rep(i, 1, n)    G1.add(get<0>(p[i]), get<1>(p[i]), 1, -get<2>(p[i]));
    mcmf();
    printf("%d\n", -mincost);
}

19/24 餐巾计划问题

如果我们不考虑可以送去换洗店的问题，只考虑买入的话。那么这个建图将会很简单。

每天都向汇点连入一条流量为当天所需餐巾数，费用为 $0$ 的边。

源点向各个点流入流量为 $INF$ 费用为买入一条餐巾的价格 $p$ 的边。

这样跑出最大流就满足了每天的餐巾要求以及所需费用。

现在我们多了换洗操作，说明我们上方这样一天对应一个点无法搞定了，考虑拆点。

我们把每天拆成上午和下午。我们下午对应上方说的只考虑买入的部分点。

那么下午都向汇点连边，但是我们多了一种操作，我们就把上午对应成换洗店部分，做类似的寄存操作。

我们思考，在第 $1$ 天的时候换洗店只能收到第一天提供的脏餐巾，那么他可以给第 $i+n$ 和 $i+m$ 的下午分别提供流量为 $INF$ ，费用是 $s$ 和 $f$ 的边，（也就是方便那一天交差，我们定的交差的时间是在下午）。

同理第 $2$ 天，换洗店可以收到第二天提供的脏餐巾，当然他也可以收到第一天继承的脏餐巾，说明每一天之间上午都要互相连边。

整合思路就是如下：

点：
1. 源点 $0$
2. 汇点 $1$
3. 第 $i$ 天的上午和下午 $(2i,2i+1)$
弧：
1. 源点去上午，流量是当天的脏餐巾数量，费用是 $0$
2. 下午去汇点，流量是当天的脏餐巾数量，等价于那天所需的餐巾数，费用是 $0$
3. 源点去下午，流量是 $INF$ ，费用是 $p$ ，购买单价
4. 第 $i$ 天的上午去第 $i+m$ 天的下午，流量是 $INF$ ，费用是 $f$ ，快洗店
5. 第 $i$ 天的上午去第 $i+n$ 天的下午，流量是 $INF$ ，费用是 $s$ ，慢洗店
6. 第 $i$ 天的上午去第 $i+1$ 天的上午，流量是 $INF$ ，费用是 $0$ ，把脏毛巾留给第二天
最小费用就是最优解

void solve() {
    G1.init();
    n = read();
    be = 0, ed = 1;
    rep(i, 1, n) {
        int x = read();
        G1.add(be, i << 1, x, 0);
        G1.add(i << 1 | 1, ed, x, 0);
    }
    p = read(), m = read(), f = read(), n2 = read(), s = read();
    rep(i, 1, n) {
        G1.add(be, i << 1 | 1, INF, p);
        if (i + m <= n)    G1.add(i << 1, (i + m) << 1 | 1, INF, f);
        if (i + n2 <= n)    G1.add(i << 1, (i + n2) << 1 | 1, INF, s);
        if (i + 1 <= n)    G1.add(i << 1, (i + 1) << 1, INF, 0);
    }
    mcmf();
    printf("%lld\n", mincost);
}

20/24 数字梯形问题

费用流模型。首先对题目做出解释，每个点可以和下方的左右两个点连边。问在下面三种限制下的最大和分别是多少？

每个点可以经过一次，每条边只能经过一次。
每个点可以经过多次，每条边只能经过一次。
每个点可以经过多次，每条边可以经过多次。

首先每个点都有独立的价值，他又要和别人有边，有时候只能选择一次，说明一个点搞不定这个事情，我们就要拆点处理了。

对于每个点，我们拆分成入点和出点。

节点内部入点出点之间的边，我们叫做它内部边。那么还要流出到下方，把当前节点的出点连接到下方节点的入点，我们把这样的边叫做外部边。内部边产生费用，外部边不产生费用，只用来做引流操作。

这样我们就可以得出下面的建图思路。

对于问题 $1$ 来说
1. 源点向顶层节点的入点流入流量是 $1$ ，费用是 $0$ 的外部边。
2. 节点之间的内部边流量是 $1$ ，费用是 $-a[i][j]$ ，代表当前节点只能使用一次。
3. 节点的出点和它下方节点的入点之间连入外部边，流量是 $1$ ，费用是 $0$ 。
4. 最底层的出点连入汇点，流量是 $1$ ，费用是 $0$ 。
对于问题 $2$ 来说

只需要在问题 $1$ 的基础上，把每个节点只能使用一次的权限去掉，也就是节点的内部边我们把边权流量赋值为 $INF$ 。以及最底层节点它也可以被使用多次，把它和汇点之间的流量也改为 $INF$ 即可。
对于问题 $3$ 来说

在问题 $2$ 的基础上，把每条边只能使用一次的权限也给去掉。也就是每个点的出点和下一层节点的入点流量改为 $INF$ 。

这样依次求最大费用就是答案了。

int a[41][41];
inline int encode(int i, int j) { return (i - 1) * (m + n - 1) + j; }
inline int upp_encode(int i, int j) { return encode(i, j) << 1; }
inline int low_encode(int i, int j) { return encode(i, j) << 1 | 1; }

void solve() {
    m = read(); n = read();
    be = 0, ed = 1;
    rep(i, 1, n)
        rep(j, 1, m + i - 1)    a[i][j] = read();

    G1.init();
    rep(i, 1, n) {
        rep(j, 1, m + i - 1) {
            if (i == 1)    G1.add(be, upp_encode(i, j), 1, 0);
            G1.add(upp_encode(i, j), low_encode(i, j), 1, -a[i][j]);
            if (i == n)    G1.add(low_encode(i, j), ed, 1, 0);
            else {
                for (auto& dj : { j,j + 1 })
                    G1.add(low_encode(i, j), upp_encode(i + 1, dj), 1, 0);
            }
        }
    }
    mcmf();
    printf("%d\n", -mincost);

    G1.init();
    rep(i, 1, n) {
        rep(j, 1, m + i - 1) {
            if (i == 1)    G1.add(be, upp_encode(i, j), 1, 0);
            G1.add(upp_encode(i, j), low_encode(i, j), INF, -a[i][j]);
            if (i == n)    G1.add(low_encode(i, j), ed, INF, 0);
            else {
                for (auto& dj : { j,j + 1 })
                    G1.add(low_encode(i, j), upp_encode(i + 1, dj), 1, 0);
            }
        }
    }
    mcmf();
    printf("%d\n", -mincost);

    G1.init();
    rep(i, 1, n) {
        rep(j, 1, m + i - 1) {
            if (i == 1)    G1.add(be, upp_encode(i, j), 1, 0);
            G1.add(upp_encode(i, j), low_encode(i, j), INF, -a[i][j]);
            if (i == n)    G1.add(low_encode(i, j), ed, INF, 0);
            else {
                for (auto& dj : { j,j + 1 })
                    G1.add(low_encode(i, j), upp_encode(i + 1, dj), INF, 0);
            }
        }
    }
    mcmf();
    printf("%d\n", -mincost);
}

21/24 火星探险问题

有 $k$ 个机器人，机器人在 $n*m$ 的地图上行走，无法跨过障碍，平地和石头都可以无限制踏过，石头价值只能获取一次。每次只能往下和往右走，每个机器人都要从 $(1,1)$ 走到 $(n,m)$ ，输出找到最多石头的方案。

点：
1. 源点 $(0)$
2. 汇点 $(N-1)$
3. 每个地点分为入点出点 $(i,i+n*m)$
弧：
1. 源点向 $(1,1)$ 的入点连入流量是 $k$ 的边，费用是 $0$ 。
2. $(n,m)$ 的出点向汇点连入流量是 $k$ 的边，费用是 $0$ 。
3. 地图中除掉障碍以为的点，把入点和出点连边，流量是 $INF$ ，费用 $0$ 。
4. 地图中的石头，把它的入点和出点连边，流量是 $1$ ，费用是 $-1$ 。
5. 地图中的点把他们向右连边以及向下连边，流量是 $INF$ ，费用是 $0$ 。
最大费用

跑一遍最大费用最大流就可以找到答案。

至于输出方案，可以对最后留下的残量网络去 $dfs$ ，每走一次这条边，就把这条边的流量 $-1$ 。输出答案。

int a[37][37], level;
inline int encode(int i, int j) { return (i - 1) * m + j; }

void display(int id, int now) {
    for (int i = G1.head[now]; ~i; i = G1.edge[i].next) {
        int v = G1.edge[i].v, flow = G1.edge[i].flow;
        if (!flow)    continue;
        if (now + 1 == v)    printf("%d 1\n", id);
        else printf("%d 0\n", id);
        --G1.edge[i].flow;
        display(id, v);
        return;
    }
}

void solve() {
    G1.init();
    k = read();
    m = read(); n = read();
    level = n * m;
    be = 0, ed = N - 1;
    G1.add(be, encode(1, 1), k, 0);
    G1.add(encode(n, m) + level, ed, k, 0);
    rep(i, 1, n) {
        rep(j, 1, m) {
            a[i][j] = read();
            if (a[i][j] == 1)    continue;
            G1.add(encode(i, j), encode(i, j) + level, INF, 0);
            if (a[i][j] == 2)    G1.add(encode(i, j), encode(i, j) + level, 1, -1);
        }
    }
    rep(i, 1, n)
        rep(j, 2, m)    G1.add(encode(i, j - 1) + level, encode(i, j), INF, 0);
    rep(i, 2, n)
        rep(j, 1, m)    G1.add(encode(i - 1, j) + level, encode(i, j), INF, 0);
    mcmf();
    rep(u, level + 1, level * 2) {
        int x = (u - level - 1) / m + 1;
        int y = (u - level - 1) % m + 1;
        if (a[x][y] == 1)    continue;
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v, flow = G1.edge[i].flow;
            if (v + level == u or flow == INF)    continue;
            if (v == ed)    continue;
            G1.add(u + level, v + 2 * level, INF - flow, 0);
        }
    }
    rep(i, 1, k)    display(i, 1 + 2 * level);
}