网络流应用专题lyh's blog

有必要整理一下网络流模型了，本文长期更新。以下题目许多出自网络流24题专题，点击标题可跳转。前缀知识：网络流。

负载平衡问题

        网络流只要建出图来就好说。本题中可以这样建图：设出源点和汇点，从源点开始向每一个点引一条边，容量限制为对应点的初始值，每一个再向汇点引一条边，容量限制为所有点权之和除以点数（就是最后平衡时的点权）。这些边的费用均为0。
        之后再考虑点之间的转化。对于相邻的点，向这两个点引两条边，容量限制无穷大，费用为1（就是流量代价）。在这个图上跑费用流即可，答案就是最小费用。
        这个网络流模型可以这样理解：源点对点进行初始化，汇点限制末状态，中间边代表转移，费用代表代价。

//SPFA+EK算法费用流
#include<bits/stdc++.h>

using namespace std;
struct Edge {
    int next, to, v, price;
} edge[20005];
int head[205], cnt, op[105], n, sum, vis[105], ans, pre[105], flow[105], dict[105];

inline void add(int x, int y, int v, int p) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].price = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].price = -p, head[y] = cnt++;
}

queue<int> que;

inline int SPFA() {
    for (int i = 0; i <= n + 1; i++)dict[i] = 0x7fffffff, vis[0] = 0, pre[i] = -1;
    while (!que.empty())que.pop();
    que.push(0), vis[0] = 1, dict[0] = 0, flow[0] = 0x7fffffff;
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dict[edge[i].to] > dict[f] + edge[i].price) {
                dict[edge[i].to] = dict[f] + edge[i].price, pre[edge[i].to] = i;
                flow[edge[i].to] = min(flow[f], edge[i].v);
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[n + 1] == -1 ? -1 : flow[n + 1];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i], head[i] = -1;
        sum += op[i];
    }
    head[0] = head[n + 1] = -1;
    for (int i = 1; i <= n; i++)add(0, i, op[i], 0), add(i, n + 1, sum / n, 0);
    for (int i = 1; i <= n; i++) {//建图过程
        if (i == 1)add(1, 2, 1 << 30, 1), add(1, n, 1 << 30, 1);
        else if (i == n)add(n, n - 1, 1 << 30, 1), add(n, 1, 1 << 30, 1);
        else add(i, i - 1, 1 << 30, 1), add(i, i + 1, 1 << 30, 1);
    }
    int increase;
    while ((increase = SPFA()) != -1) {//费用流算法
        int p = n + 1;
        while (p != 0)edge[pre[p]].v -= increase, edge[pre[p] ^ 1].v += increase, p = edge[pre[p] ^ 1].to;
        ans += increase * dict[n + 1];
    }
    cout << ans;
    return 0;
}

最小路径覆盖问题（模板）

这是一个重要模型。
对于DAG上的最小路径覆盖，我们可以这样理解：起初，可以将所有的点视为一个个独立的集合，这样集合数量为n（n为点数），这个值很可能不是最小的；这时注意到两个路径之间可以合并，且对于每一个点只能合并一次，每合并一个就意味着答案减去1。这样建图方法就可以推知了。首先将每一个点分为$x$,$y$，从源点开始向每一个点的$x$点引一条边，容量为1，再从每一个点的$y$开始，向汇点引一条边，容量为1。对于原DAG上的每一条边$(a,b)$，在网络流上建立边$(x_a,y_b)$，容量为1。这样做可以使每一个点仅能使用一次，最后的流量就是合并的次数。在图上跑最大流算法，求出最大流$flow$，答案就是$n-flow$。

//Dinic算法
#include<bits/stdc++.h>

using namespace std;
struct Edge {
    int to, next, v;
} edge[20005];
int head[500], cnt, n, m, d[500], cur[500], vis[500];

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

queue<int> que;

int DFS(int x, int limit) {
    if (x == (n << 1 | 1) || limit == 0)return limit;
    int f, flow = 0;
    for (int i = cur[x]; ~i; i = edge[i].next) {
        cur[x] = i;//当前弧优化
        if (d[edge[i].to] == d[x] + 1 && (f = DFS(edge[i].to, min(edge[i].v, limit)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0)break;
        }
    }
    return flow;
}

inline int BFS() {
    for (int i = 0; i <= (n << 1 | 1); i++)d[i] = 0x7fffffff, cur[i] = head[i];
    while (!que.empty())que.pop();
    d[0] = 0, que.push(0);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == (n << 1 | 1))return 1;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (d[edge[i].to] == 0x7fffffff && edge[i].v > 0)d[edge[i].to] = d[f] + 1, que.push(edge[i].to);
        }
    }
    return 0;
}

void solve(int x) {//递归找答案
    vis[x] = 1;
    cout << x << " ";
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (edge[i].to > n && edge[i].to <= (n << 1) && edge[i].v == 0) {//流出点为邻接点
            solve(edge[i].to - n);
            return;
        }
    }
}

int main() {
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y + n, 1);
    }
    for (int i = 1; i <= n; i++)add(0, i, 1), add(i + n, n << 1 | 1, 1);
    int ans = 0;
    while (BFS())ans += DFS(0, 0x7fffffff);
    ans = n - ans;
    for (int i = 1; i <= ans; i++) {
        for (int j = 1; j <= n; j++) {
            if (vis[j])continue;
            for (int e = head[j + n]; ~e; e = edge[e].next) {
                if (edge[e].to == (n << 1 | 1) && edge[e].v == 1) {//没有流，说明是起点
                    solve(j);
                    cout << endl;
                    break;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

对于有环的有向图，可以先tarjan缩点，再跑网络流。

魔术球问题

这个在上面模板的基础上就很好理解。
注意到每一个柱子上的数必然是递增的，并且每一个柱子都可以看成是一个路径（结合模板）。可以从小到大枚举答案，建图跑最大流，然后更新答案。这里根据答案单调性，可以用二分优化。下面代码是朴素的方法。

#include<bits/stdc++.h>

#define N 2000
using namespace std;
struct Edge {
    int to, next, v;
} edge[200005];
int head[5005], cnt, sp, d[5005], cur[5005], vis[5005], ans;

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

queue<int> que;

int DFS(int x, int limit) {
    if (x == (N << 1 | 1) || limit == 0)return limit;
    int f, flow = 0;
    for (int i = cur[x]; ~i; i = edge[i].next) {
        cur[x] = i;//当前弧优化
        if (d[edge[i].to] == d[x] + 1 && (f = DFS(edge[i].to, min(edge[i].v, limit)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0)break;
        }
    }
    return flow;
}

inline int BFS() {
    for (int i = 0; i <= (N << 1 | 1); i++)d[i] = 0x7fffffff, cur[i] = head[i];
    while (!que.empty())que.pop();
    d[0] = 0, que.push(0);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == (N << 1 | 1))return 1;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (d[edge[i].to] == 0x7fffffff && edge[i].v > 0)d[edge[i].to] = d[f] + 1, que.push(edge[i].to);
        }
    }
    return 0;
}

void solve(int x) {
    vis[x] = 1;
    cout << x << " ";
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (edge[i].to > N && edge[i].to <= N + ans && edge[i].v == 0) {
            solve(edge[i].to - N);
            return;
        }
    }
}

int main() {
    int flow = 0;
    cin >> sp;
    memset(head, -1, sizeof(head));
    add(0, 1, 1), add(1 + N, N << 1 | 1, 1), add(0, 2, 1), add(2 + N, N << 1 | 1, 1);//先加入1和2这两个数
    for (int now = 3; now <= N; now++) {
        add(0, now, 1), add(now + N, N << 1 | 1, 1);//加入新边
        for (int i = 1; i < now; i++) {
            int sp = (int) sqrt(i + now);
            if (sp * sp == i + now)add(i, now + N, 1);//加入新边
        }
        while (BFS())flow += DFS(0, 0x7fffffff);//跑Dinic最大流，这里不用清图，在上一个的基础上跑算法即可
        if (now - flow <= sp)ans = now;
        if (now - flow > sp)break;//提前结束，相当于剪枝
    }
    cout << ans << endl;
    for (int i = 1; i <= sp; i++) {//这里和模板的处理方式基本相同
        for (int j = 1; j <= ans; j++) {
            if (vis[j])continue;
            for (int e = head[j + N]; ~e; e = edge[e].next) {
                if (edge[e].to == (N << 1 | 1) && edge[e].v == 1) {
                    solve(j);
                    cout << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

试题库问题

本题比较简单。考虑到每一个题只能用一次，而且它只能对一个类型做出贡献。建立源点到每一个点的边，容量为1，然后对于一个题目的类型，从该点出发向类型建立边，容量为1，最后从每个类型开始，向汇点建立边，容量为规定的题目数量。在这个图上跑最大流即可。如果最大流不足m，则无解。

#include<bits/stdc++.h>

using namespace std;
struct Edge {
    int next, to, v;
} edge[50000];
int head[5000], cnt, k, n, kp[25], d[5000], cur[5005], sum;

inline void add(int x, int y, int v) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

queue<int> que;

int DFS(int x, int limit) {
    if (x == (n << 1 | 1) || limit == 0)return limit;
    int f = 0, flow = 0;
    for (int i = cur[x]; ~i; i = edge[i].next) {
        cur[x] = i;
        if (d[edge[i].to] == d[x] + 1 && (f = DFS(edge[i].to, min(edge[i].v, limit)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0)break;
        }
    }
    return flow;
}

inline int BFS() {
    for (int i = 0; i <= (n << 1 | 1); i++)d[i] = 0x7fffffff, cur[i] = head[i];
    while (!que.empty())que.pop();
    d[0] = 0, que.push(0);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == (n << 1 | 1))return 1;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (d[edge[i].to] == 0x7fffffff && edge[i].v > 0)d[edge[i].to] = d[f] + 1, que.push(edge[i].to);
        }
    }
    return 0;
}

int main() {
    cin >> k >> n;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= k; i++) {
        cin >> kp[i];
        add(i + n, n << 1 | 1, kp[i]), sum += kp[i];
    }
    for (int i = 1; i <= n; i++) {
        add(0, i, 1);
        int p;
        cin >> p;
        while (p--) {
            int x;
            cin >> x;
            add(i, x + n, 1);
        }
    }
    int ans = 0;
    while (BFS())ans += DFS(0, 0x7fffffff);
    if (ans != sum)cout << "No Solution!";
    else {
        for (int i = 1; i <= k; i++) {
            cout << i << ": ";
            for (int e = head[i + n]; ~e; e = edge[e].next) {
                if (edge[e].to >= 1 && edge[e].to <= n && edge[e].v == 1)cout << edge[e].to << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

方格取数问题

对棋盘上的点进行黑白染色，可以得到一个二分图。现在需要在上面选几个点，使得它们两两不相邻，可以这样建图：从源点引边指向黑点，容量限制为黑点的值，从白点引边指向汇点，容量限制为白点的值；对于相邻的黑点和白点，从黑点开始引边指向相应的白点，容量限制为无穷大。建完图之后，在这个图上求最小割。可以这样理解：对网络流的割就是断开某些边使源点汇点不连通且边权最小，由于黑白点之间边权为无穷大，故它们必然不会被割，这样只能割与源点和汇点相连的边，一条边被割便意味着与之对应的点不选。对于一个合理的选点情况，将它们放到图中，源点和汇点应该是不连通的。我们在图上求最小割，本质上是删点的过程，它使得源点汇点不连通，这样剩下的点就是我们需要选的点，并保证了被删去的点点权尽可能小，从而得到最大的答案。
于是答案就是所有数的和与最小割的差。由于某种原因，本题代码用python给出：

from queue import Queue


def ID(x, y):
    global n, m
    return m * x + y


class Edge:
    next = 0
    v = 0
    to = 0


def addEdge(x, y, zt):
    global cnt, edge, head
    edge.append(Edge())
    edge.append(Edge())
    edge[cnt].to = y
    edge[cnt].next = head[x]
    edge[cnt].v = zt
    head[x] = cnt
    cnt = cnt + 1
    edge[cnt].to = x  # 反边
    edge[cnt].next = head[y]
    edge[cnt].v = 0
    head[y] = cnt
    cnt = cnt + 1


def DFS(x, limit):
    global n, m, head, edge
    if x == n * m + 1 or limit == 0:
        return limit
    e = int(head[x])
    flow = 0
    while e != -1:
        if d[edge[e].to] == d[x] + 1:
            f = DFS(edge[e].to, min(edge[e].v, limit))
            if f > 0:
                edge[e].v -= f
                edge[e ^ 1].v += f
                flow += f
                limit -= f
                if limit == 0:
                    break
        e = edge[e].next
    return int(flow)


def BFS():
    global n, m, inf, head, edge
    que = Queue(0)
    for it in range(0, n * m + 2):
        d[it] = inf
    d[n * m] = 0
    que.put(n * m)
    while not que.empty():
        f = que.get()
        e = head[f]
        if f == n * m + 1:
            return True
        while e != -1:
            if edge[e].v > 0 and d[edge[e].to] == inf:
                d[edge[e].to] = d[f] + 1
                que.put(edge[e].to)
            e = edge[e].next
    return False


lss = input().split()
n = int(lss[0])
m = int(lss[1])
d = []
sum = 0
head = []
cnt = 0
inf = 1 << 30
edge = []
op = []
X = [-1, 0, 1, 0]
Y = [0, 1, 0, -1]
for i in range(0, n):
    lss = input().split()
    for j in range(0, m):
        op.append(int(lss[j]))
        sum += int(lss[j])
        head.append(-1)
        d.append(0)
head.append(-1)
d.append(0)  # 源点：nm
head.append(-1)
d.append(0)  # 汇点：nm+1
for i in range(0, n):
    for j in range(0, m):
        if (i + j) % 2 == 1:
            addEdge(n * m, ID(i, j), op[ID(i, j)])
            for z in range(0, 4):  # 四个方向
                xx = i + X[z]
                yy = j + Y[z]
                if 0 <= xx < n and 0 <= yy < m:
                    addEdge(ID(i, j), ID(xx, yy), inf)
        else:
            addEdge(ID(i, j), n * m + 1, op[ID(i, j)])
ans = 0
while BFS():
    ans += DFS(n * m, inf)
print(sum - ans)

最长不下降子序列问题

        看着像一个智障的问题，其实它需要网络流解决。
        第一问用dp搞出来，这里定义$dp[i]$为以i结尾的最长序列长度。对于第二问，可以这样建图：将所有点拆成两个部分$x$和$y$，并建边$(x_i,y_i)$，对于$dp[i]=1$的点，从源点开始向$x_i$引一条边，容量为1，对于$dp[a]+1=dp[b]$且满足不下降条件的$a$和$b(a < b)$，引边$(y_a,x_b)$，容量为1，对于$dp[i]=s$（s为第一问答案）的点i，从$y_i$开始建边指向汇点，容量为1。容量为1保证了每一个点只能选一次，该图的最大流就是第二问答案。
        第三问对于$dp[a]+1=dp[b]$且满足不下降条件的$a$和$b(a < b)$之间的边$(y_a,x_b)$，容量仍然为1，其余均置为无穷大。这些边没有容量限制意味着起点和终点可以有多个去向（来源），从而达到复用起点终点的目的。
        注意这种方法需要特判第一问答案为1的情况。

#include<bits/stdc++.h>

#define inf (1<<30)
using namespace std;
int dp[505], op[505], n, s = 1, s2, s3;
struct Edge {
    int to, next, v;
} edge[60000];
int head[1005], cnt, d[1005], cur[1005];

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

queue<int> que;

int DFS(int x, int limit) {
    if (x == (n << 1 | 1) || limit == 0)return limit;
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        cur[x] = i;
        if (d[edge[i].to] == d[x] + 1 && (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, limit -= f, flow += f;
            if (limit == 0)break;
        }
    }
    return flow;
}

inline int BFS() {
    for (int i = 0; i <= (n << 1 | 1); i++)d[i] = inf, cur[i] = head[i];
    while (!que.empty())que.pop();
    d[0] = 0, que.push(0);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == (n << 1 | 1))return 1;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && d[edge[i].to] == inf)d[edge[i].to] = d[f] + 1, que.push(edge[i].to);
        }
    }
    return 0;
}

int main() {
    cin >> n, memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++)cin >> op[i];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++)if (op[i] >= op[j])dp[i] = max(dp[i], dp[j] + 1);
        s = max(s, dp[i]);
    }
    for (int i = 1; i <= n; i++) {
        add(i, i + n, 1);
        if (dp[i] == 1)add(0, i, 1);
        else if (dp[i] == s)add(i + n, n << 1 | 1, 1);
        for (int j = i + 1; j <= n; j++)if (op[j] >= op[i] && dp[j] == dp[i] + 1)add(i + n, j, 1);
    }
    cout << s << endl;
    if (s == 1) {
        cout << n << endl << n;
        return 0;
    }
    while (BFS())s2 += DFS(0, inf);
    cout << s2 << endl;
    cnt = 0, memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {
        add(i, i + n, 100000);
        if (dp[i] == 1)add(0, i, 10000);
        else if (dp[i] == s)add(i + n, n << 1 | 1, 100000);
        for (int j = i + 1; j <= n; j++)if (op[j] >= op[i] && dp[j] == dp[i] + 1)add(i + n, j, 1);
    }
    while (BFS())s3 += DFS(0, inf);
    cout << s3 << endl;
    return 0;
}

[NOI2009]植物大战僵尸（模板）

        可以作为最大权闭合子图的模板题。
        将每一个格子抽象为点，它们的顺序抽象为边可以建出一个图，具体做法：从某一个植物开始，向它保护的格子连有向边，同时对于每一行，右边的格子向左边相邻的格子连有向边。容易发现，有向边规定了攻击的顺序，只有将某一个格子的前驱结点全部攻击之后，才可以攻击这个格子。这里可以按照拓扑排序的方法来理解。
        对于这个有向图，如果其中存在环，那么这个环一定是不可破的，它之后的所有点都同时不可破。因此在建完图之后需要来一次tarjan算法进行缩点，对于那些成环的点，将其缩成一点并打上标记，同时进行DFS对其之后的所有点也打上标记。
        抽离所有被打上标记的点，可以得到一个新图，现在问题转化为：在这个图上选取一些点，满足拓扑排序规则，使其权值之和最大。
        这样其实不好处理，可以将图反建，此时注意到要选取一个点，必须将其之后的点（就是原图中的前驱点）全部选上，本质上选了一个闭合子图，那么问题转化成求一个有向图的最大权闭合子图，可以用最小割来解决。
        接下来建网络流图。对于求最大权闭合子图的网络流建模，可采用这样的方法：对于点权非负的点，从源点开始向其引一条边，容量限制为点权；对于权值为负的点，从其开始向汇点引一条边，容量限制为点权的相反数；对于原图中的边，将其直接搬到网络流图中，容量限制为无穷大。在这个图上求最小割，答案就是点权非负的权值之和与最小割的差。

#include <bits/stdc++.h>

#define ID(x, y) (x)*m+(y)
#define N 100000
#define S (n*m+1)
#define T (n*m+2)
#define INF (1<<28)
using namespace std;
struct Edge {
    int next, to, v, from;
} edge[3][N * 10];
int head[3][N], cnt[3], n, m, op[N], num[N], DFN[N], LOW[N], vis[N], DFNCNT, op2[N];
int cor[N], corID = 1, d[N], ans;
stack<int> sta;
queue<int> que;

inline void add(int p, int x, int y, int z = 0) {
    edge[p][cnt[p]].to = y, edge[p][cnt[p]].v = z, edge[p][cnt[p]].next = head[p][x], edge[p][cnt[p]].from = x;
    head[p][x] = cnt[p]++;
}


void tarjan(int x) {//tarjan缩点染色
    if (DFN[x])return;
    DFN[x] = LOW[x] = ++DFNCNT, sta.push(x), vis[x] = 1;
    for (int i = head[0][x]; ~i; i = edge[0][i].next) {
        if (DFN[edge[0][i].to] == 0)tarjan(edge[0][i].to), LOW[x] = min(LOW[edge[0][i].to], LOW[x]);
        else if (vis[edge[0][i].to])LOW[x] = min(DFN[edge[0][i].to], LOW[x]);
    }
    if (LOW[x] == DFN[x]) {
        int p;
        do vis[p = sta.top()] = 0, cor[p] = corID, sta.pop(), ++num[cor[p]];
        while (p != x);
        if (num[cor[p]] == 1)num[cor[p]] = 0, op2[cor[p]] = op[x];//表示这个点可破
        ++corID;
    }
}

void DFS(int x) {
    for (int i = head[1][x]; ~i; i = edge[1][i].next) {
        if (!vis[edge[1][i].to])vis[edge[1][i].to] = 1, DFS(edge[1][i].to);
    }
}

int DFS(int x, int limit) {
    if (x == T || limit == 0)return limit;
    int f, flow = 0;
    for (int i = head[2][x]; ~i; i = edge[2][i].next) {
        if (d[edge[2][i].to] == d[x] + 1 && (f = DFS(edge[2][i].to, min(edge[2][i].v, limit)))) {
            edge[2][i].v -= f, edge[2][i ^ 1].v += f, flow += f, limit -= f;
            if (limit == 0)break;
        }
    }
    return flow;
}

int BFS() {
    while (!que.empty())que.pop();
    for (int i = 1; i < corID; i++)d[i] = INF;
    d[S] = 0, d[T] = INF, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == T)return 1;
        for (int i = head[2][f]; ~i; i = edge[2][i].next) {
            if (edge[2][i].v > 0 && d[edge[2][i].to] == INF)d[edge[2][i].to] = d[f] + 1, que.push(edge[2][i].to);
        }
    }
    return 0;
}

int main() {
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j)add(0, ID(i, j), ID(i, j - 1));//攻击顺序自右向左
            int x, y, w;
            cin >> op[ID(i, j)] >> w;
            for (int z = 0; z < w; z++) {
                cin >> x >> y;
                add(0, ID(i, j), ID(x, y));//保护顺序
            }
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)tarjan(ID(i, j));//缩点
    for (int i = 0; i < cnt[0]; i++) {
        if (cor[edge[0][i].from] != cor[edge[0][i].to])add(1, cor[edge[0][i].from], cor[edge[0][i].to]);
    }
    for (int i = 1; i < corID; i++)if (num[i] && !vis[i])vis[i] = 1, DFS(i);//vis=1表示不可破
    for (int i = 1; i < corID; i++) {//建网络流图,S源点,T汇点
        if (!vis[i]) {
            if (op2[i] >= 0)ans += op2[i], add(2, S, i, op2[i]), add(2, i, S, 0);
            else add(2, i, T, -op2[i]), add(2, T, i, 0);
        }
    }
    for (int i = 0; i < cnt[1]; i++) {
        if (!vis[edge[1][i].from] && !vis[edge[1][i].to]) {
            add(2, edge[1][i].to, edge[1][i].from, INF), add(2, edge[1][i].from, edge[1][i].to, 0);
        }
    }
    while (BFS())ans -= DFS(S, INF << 2);
    cout << max(ans, 0);//注意和0取最大值
    return 0;
}

[SDOI2009]晨跑

        应该是比较裸的费用流。
        由于每条边只能走一次，故将容量限制设为1，又由于每一点只能走一次，可以将一个点一分为二，中间加一条容量限制为1的有向边。对于所有的原边，其费用就是距离，而对于我们加入的新边，其费用都为0。注意源点与汇点拆点时容量限制应为无穷大。
        最终答案就是最大流和最小费用。

#include <bits/stdc++.h>

#define inf (1<<29)
using namespace std;
struct Edge {
    int next, to, v, p;
} edge[80000];
int cnt, head[1000], n, m, S, T, dict[8000], pre[8000], flow[8000], vis[8000];
queue<int> que;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void add(int x, int y, int v, int p) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

inline int SPFA() {
    while (!que.empty())que.pop();
    for (int i = S; i <= T; i++)vis[i] = 0, pre[i] = -1, flow[i] = dict[i] = inf;
    vis[S] = 1, dict[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dict[edge[i].to] > dict[f] + edge[i].p) {
                dict[edge[i].to] = dict[f] + edge[i].p, pre[edge[i].to] = i, flow[edge[i].to] = min(flow[f], edge[i].v);
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[T] == -1 ? -1 : flow[T];
}

int main() {
    n = read(), m = read(), memset(head, -1, sizeof(head));
    for (int i = 2; i < n; i++)add(i, i + n, 1, 0);
    add(1, 1 + n, inf, 0), add(n, n << 1, inf, 0), S = 1, T = n << 1;
    for (int i = 0, x, y, z; i < m; i++)x = read(), y = read(), z = read(), add(x + n, y, 1, z);
    int increase, ans = 0, minCost = 0;
    while ((increase = SPFA()) != -1) {
        int now = T;
        while (now != S)edge[pre[now]].v -= increase, edge[pre[now] ^ 1].v += increase, now = edge[pre[now] ^ 1].to;
        ans += increase, minCost += dict[T] * increase;
    }
    cout << ans << " " << minCost;
    return 0;
}

[SCOI2007]修车

仍然是费用流，不过不是那么容易建图。
考虑一个师傅修若干辆车的总等待时间。如果修了$s$辆车，修车时间分别为$W_1,W_2,\cdots,W_s$，按照这个修车顺序，总时间为：

$T=sW_1+(s-1)W_2+\cdots+W_s$

        显然，越先修车的对时间造成代价最大，并且可以发现，在修车的师傅固定时，每一个车对总代价的贡献只与它的顺序有关。如果这辆车是倒数第t个，那么它对总时间的贡献为$tW$。
        于是，可以建立车与修车师傅以及顺序之间的关系。将$M$个修车师傅看成$M$个点，再将它们分为$N$个点，表示N个顺序，其中第$i$个点表示倒数第$i$个修。这样可以建立车（$N$个点）到修车师傅以及顺序（$MN$个点）的完全二分图，权值为$iW$（与上文理解相同）。
        建完图之后，问题转化为求这个二分图上的最小权值完美匹配（只需要N个车完全匹配）。这样做的可行性在于，对于每一个师傅，他修车的顺序可以保证是连续的。证明：假设匹配时车$m$与第$i$位师傅的第$j$个点匹配（表示倒数第j个修），却没有车与第$j+1$个点匹配，又同时有车$n$与第$j+p(p>1)$匹配。这时由于车$n$与第$j+1$个点匹配的权值更小，不满足最优性，故在保证最小权值的前提下这种不连续的情况不可能发生。
        带权二分图匹配可以用网络流解决，这个方面的说明在网络流最后，文章链接见本文最开始部分。注意这里是求最小权值，故费用不用取相反数。

#include <bits/stdc++.h>

#define inf (1<<29)
using namespace std;
struct Edge {
    int next, to, v, p;
} edge[80000];
int cnt, head[1000], n, m, S, T, dict[8000], pre[8000], flow[8000], vis[8000];
queue<int> que;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void add(int x, int y, int v, int p) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

inline int SPFA() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n + n * m + 2; i++)vis[i] = 0, pre[i] = -1, flow[i] = dict[i] = inf;
    vis[S] = 1, dict[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dict[edge[i].to] > dict[f] + edge[i].p) {
                dict[edge[i].to] = dict[f] + edge[i].p, pre[edge[i].to] = i, flow[edge[i].to] = min(flow[f], edge[i].v);
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[T] == -1 ? -1 : flow[T];
}

int main() {
    m = read(), n = read(), S = n + n * m + 1, T = n + n * m + 2, memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int z = read();
            for (int ss = 1; ss <= n; ss++)add(i, n + (j - 1) * n + ss, 1, z * ss);
        }
    }
    for (int i = 1; i <= n; i++)add(S, i, 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++)add(n + (i - 1) * n + j, T, 1, 0);
    }
    int increase, ans = 0, minCost = 0;
    while ((increase = SPFA()) != -1) {
        int now = T;
        while (now != S)edge[pre[now]].v -= increase, edge[pre[now] ^ 1].v += increase, now = edge[pre[now] ^ 1].to;
        ans += increase, minCost += dict[T] * increase;
    }
    printf("%.2f", minCost / (double) n);
    return 0;
}

[ZJOI2010]网络扩容

        简单的费用流。
        第一问就是一个纯裸的网络最大流，直接求即可。再来看第二问，我们直接在图上的原边位置都分别加上一条与之相同的边，只不过将费用设置成相应的值，并将容量限制设置为无穷大，这样就可以使网络沿我们新加的边流，达到扩容的目的。根据最小费用的最优性，只有原边在满流时才可能沿费用不为0的新边，这个条件保证了答案正确性。
        但是，这样加边无法限制最终流量，因此需要再引入一个新点，将原有汇点引一条边指向该点，并使容量限制为对应值，费用为0，这样就可以限制整体的流量。
        最后在这个网络流图上跑一遍费用流即可。

#include <bits/stdc++.h>

#define inf (1<<29)
#define ID(x, y) ((x-1)*m+y)
using namespace std;
struct Edge {
    int next, to, v, p;
} edge[80000], edge2[80000];
int cnt, head[8000], head2[8000], n, m, S, T, dict[8000], pre[8000], flow[8000], vis[8000], k, cnt2;
queue<int> que;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void add(int x, int y, int v, int p) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

inline void add2(int x, int y, int v, int p) {
    edge2[cnt2].to = y, edge2[cnt2].next = head2[x], edge2[cnt2].v = v, edge2[cnt2].p = p, head2[x] = cnt2++;
    edge2[cnt2].to = x, edge2[cnt2].next = head2[y], edge2[cnt2].v = 0, edge2[cnt2].p = -p, head2[y] = cnt2++;
}

inline int SPFA() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n; i++)vis[i] = 0, pre[i] = -1, flow[i] = dict[i] = inf;
    vis[S] = 1, dict[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dict[edge[i].to] > dict[f] + edge[i].p) {
                dict[edge[i].to] = dict[f] + edge[i].p, pre[edge[i].to] = i, flow[edge[i].to] = min(flow[f], edge[i].v);
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[T] == -1 ? -1 : flow[T];
}

inline int SPFA2() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n + 1; i++)vis[i] = 0, pre[i] = -1, flow[i] = dict[i] = inf;
    vis[S] = 1, dict[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head2[f]; ~i; i = edge2[i].next) {
            if (edge2[i].v > 0 && dict[edge2[i].to] > dict[f] + edge2[i].p) {
                dict[edge2[i].to] = dict[f] + edge2[i].p, pre[edge2[i].to] = i;
                flow[edge2[i].to] = min(flow[f], edge2[i].v);
                if (!vis[edge2[i].to])que.push(edge2[i].to), vis[edge2[i].to] = 1;
            }
        }
    }
    return pre[T] == -1 ? -1 : flow[T];
}


int main() {
    n = read(), m = read(), k = read(), memset(head, -1, sizeof(head)), S = 1, memset(head2, -1, sizeof(head2)), T = n;
    for (int i = 0, x, y, z, p; i < m; i++)
        x = read(), y = read(), z = read(), p = read(), add(x, y, z, 0), add2(x, y, z, 0), add2(x, y, inf, p);
    int increase, ans = 0, minCost = 0;
    while ((increase = SPFA()) != -1) {
        int now = T;
        while (now != S)edge[pre[now]].v -= increase, edge[pre[now] ^ 1].v += increase, now = edge[pre[now] ^ 1].to;
        ans += increase, minCost += dict[T] * increase;
    }
    cout << ans << " ", k += ans, T = n + 1, add2(n, T, k, 0), ans = 0;
    while ((increase = SPFA2()) != -1) {
        int now = T;
        while (now != S)edge2[pre[now]].v -= increase, edge2[pre[now] ^ 1].v += increase, now = edge2[pre[now] ^ 1].to;
        ans += increase, minCost += dict[T] * increase;
    }
    cout << minCost;
    return 0;
}

[NOI2012]美食节

        这个题与上面“修车”这道题很像，推荐先做上面那一道再做本题。
        基本思路与修车相同。将厨师按照时间戳拆点，然后连边形成完全二分图，再跑网络流即可。但是本题数据量比较大，直接就会导致TLE，因此需要加一些优化。
        考虑到每一次增广必定先连接某个厨师的倒数第一个时间戳位置，因此一开始我们先只连接所有厨师的倒数第一个时间戳位置，当一次增广完成后，再动态加边，这样可以有效地降低时间复杂度。

#include <bits/stdc++.h>

#define inf (1<<29)
#define ID(x, y) (x-1)*p+y+n
#define N 80100
using namespace std;
struct Edge {
    int next, to, v, p;
} edge[2000000];
int cnt, head[80100], n, m, S, T, p, dict[80100], pre[80100], flow[80100], vis[80100], op[50];
int sp[45][101], que[N], f, b;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

inline void add(int x, int y, int v, int p) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

inline int SPFA() {
    f = b = 0;
    for (register int i = 1; i <= p * m + n + 2; i++)vis[i] = 0, pre[i] = -1, flow[i] = dict[i] = inf;
    vis[S] = 1, dict[S] = 0, que[b] = S, b = (b + 1) % N;
    while (f != b) {
        register int fbd = que[f];
        f = (f + 1) % N, vis[fbd] = 0;
        for (register int i = head[fbd]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dict[edge[i].to] > dict[fbd] + edge[i].p) {
                dict[edge[i].to] = dict[fbd] + edge[i].p, pre[edge[i].to] = i, flow[edge[i].to] = min(flow[fbd],
                                                                                                      edge[i].v);
                if (!vis[edge[i].to])que[b] = edge[i].to, b = (b + 1) % N, vis[edge[i].to] = 1;
            }
        }
    }
    return pre[T] == -1 ? -1 : flow[T];
}


int main() {
    n = read(), m = read(), memset(head, -1, sizeof(head));
    for (register int i = 1; i <= n; i++)op[i] = read(), p += op[i];
    S = m * p + n + 1, T = m * p + n + 2;
    for (register int i = 1; i <= n; i++)add(S, i, op[i], 0);
    for (register int i = 1; i <= n; i++) {
        for (register int j = 1; j <= m; j++)sp[i][j] = read(), add(i, ID(j, 1), 1, sp[i][j]);//只连接一个
    }
    for (register int i = 1; i <= m; i++) {
        for (register int ps = 1; ps <= p; ps++)add(ID(i, ps), T, 1, 0);
    }
    register int increase, ans = 0, minCost = 0;
    while ((increase = SPFA()) != -1) {
        register int now = T, to = edge[pre[T] ^ 1].to - n - 1, x = to / p + 1, y = to % p + 1;
        if (y < p)for (register int i = 1; i <= n; i++)add(i, ID(x, y + 1), 1, (y + 1) * sp[i][x]);//加边
        while (now != S)edge[pre[now]].v -= increase, edge[pre[now] ^ 1].v += increase, now = edge[pre[now] ^ 1].to;
        ans += increase, minCost += dict[T] * increase;
    }
    printf("%d", minCost);
    return 0;
}

餐巾计划问题

        特别好的一道网络流，建图方式不那么容易想到。
        首先认清一个事实：每天早上都会通过一些方式（新购买或者经过清洗）得到该天需要的餐巾，晚上会得到同等数量的脏餐巾，根据这个事实就可以完成建图。
        将每一天对应的点拆为早上（设为$D(x)$）和晚上（设为$D’(x)$）两个，早上表示新餐巾的流入，晚上表示脏餐巾的流出。建图方式如下：

每天都可以购入新餐巾，加边$S->D(x)$，流量无穷大，费用为$p$。
每天都需要一定数量的餐巾（设为$c_i$），加边$D(x)->T$，流量$c_i$，费用0。
每天产生$c_i$数量的脏餐巾，加边$S->D’(x)$，流量$c_i$，费用0。
脏餐巾可以经过清洗，加边$D’(x)->D(x+m)$，流量无穷大，费用$f$，当然还要连接$D’(x)->D(x+n)$，费用就是$s$。
脏餐巾可以延期清洗，加边$D’(x)->D’(x+1)$，表示当天的脏餐巾可以流入下一天晚上，流量无穷大，费用0。

跑费用流即可。这里需要注意的一点是，在建图时可能会想到直接将早上对应的点连向当天晚上，来达到将早上餐巾用脏后流入晚上处理的效果，这样做并不正确，因为这些经过清洗的餐巾它们经过了多次利用，却用了同一个流，会导致总体流量减小，跑最小费用最大流时就不会再考虑这些重复利用的流，答案自然就不正确。
我们这里的做法是给这些脏餐巾分配新的流，就可以保证正确性了。

#include <bits/stdc++.h>

using namespace std;
#define S ((N<<1)+1)
#define T ((N<<1)+2)
#define ID(x, y) ((x-1)*2+y)
#define inf (1<<29)
struct Edge {
    int next, to, v, p;
} edge[8000000];
int head[4500], N, p, m, f, n, s, vis[4500], flow[4500], pre[4500], dis[4500];
long long ff, minCost;
queue<int> que;

inline void add(int x, int y, int v, int p) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

int SPFA() {
    for (int i = 1; i <= T; i++)vis[i] = 0, pre[i] = -1, dis[i] = inf;
    dis[S] = 0, que.push(S), vis[S] = 1, flow[S] = inf;
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dis[edge[i].to] > dis[f] + edge[i].p) {
                dis[edge[i].to] = dis[f] + edge[i].p, pre[edge[i].to] = i, flow[edge[i].to] = min(edge[i].v, flow[f]);
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[T] != -1;
}

int main() {
    N = read(), memset(head, -1, sizeof(head));
    for (int i = 1, x; i <= N; i++)add(ID(i, 2), T, x = read(), 0), add(S, ID(i, 1), x, 0);
    p = read(), m = read(), f = read(), n = read(), s = read();
    for (int i = 1; i <= N; i++)add(S, ID(i, 2), inf, p);
    for (int i = 1; i < N; i++)add(ID(i, 1), ID(i + 1, 1), inf, 0);
    for (int i = 1; i <= N; i++) {
        if (i + m <= N)add(ID(i, 1), ID(i + m, 2), inf, f);
        if (i + n <= N)add(ID(i, 1), ID(i + n, 2), inf, s);
    }
    while (SPFA()) {
        int ss = T;
        while (ss != S)edge[pre[ss]].v -= flow[T], edge[pre[ss] ^ 1].v += flow[T], ss = edge[pre[ss] ^ 1].to;
        ff += flow[T], minCost += flow[T] * dis[T];
    }
    cout << minCost;
    return 0;
}

[CTSC1999]家园

需要技巧的网络流，还需要并查集以及枚举相关的知识。
考虑到结点的转移与时间有关，那么按时间拆点是必要的：规定$D(x,t)$为$x$在时间$t$时的对应点（$x$为0或-1时为地球和月球）。建图方式如下：

当某一时间$t$有太空船到达地球时，连接$S->D(0,t)$，容量为太空船的容量。
对于一个时刻$t$的太空站$x$，连接$D(x,t)->D(x’,t+1)$，这里$x’$根据太空船航线确定，容量为太空船容量。
对于所有时刻$t$，连接$D(-1,t)->T$，容量限制为无穷大。
对于所有太空站$x$，由于其中的人可以停留一站，故连接$D(x,t)->D(x,t+1)$，容量无穷大。

枚举时间$t$，动态加边，当最大流达到$k$时，此时的$t$就是答案。
由于可能有无解的情况，需要先进行一步有解性判断。考虑到所有太空船的航线都相当于一个强连通分量，可以直接用并查集将它们合并起来，如果最后月球与地球是连通的，则有解，否则没有。

#include <bits/stdc++.h>

#define merge_ID(x) (x==0?n+1:(x==-1?n+2:x))
#define ID(x, t) ((t)*(n+2)+merge_ID(x)+2)
#define S 1
#define T 2
#define inf (1<<28)
using namespace std;
int fa[50], h[50], n, m, k, head[500000], ans, deep[500000];
vector<int> vec[50];
queue<int> que;
struct Edge {
    int next, to, v;
} edge[500000];

int findF(int x) {
    return fa[x] == x ? x : fa[x] = findF(fa[x]);
}

inline void merge(int x, int y) {
    int f1 = findF(x), f2 = findF(y);
    if (f1 != f2)fa[f1] = f2;
}

inline void add(int x, int y, int v) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

int DFS(int x, int limit) {
    if (limit == 0 || x == T)return limit;
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (deep[edge[i].to] == deep[x] + 1 &&
            (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, flow += f, limit -= f;
            if (!limit)break;
        }
    }
    return flow;
}

inline bool BFS() {
    while (!que.empty())que.pop();
    memset(deep, 127, sizeof(deep)), deep[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && deep[edge[i].to] > inf) {
                deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
                if (edge[i].to == T)return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> k, memset(head, -1, sizeof(head));
    for (int i = 1; i <= n + 2; i++)fa[i] = i;
    for (int i = 1, x; i <= m; i++) {
        cin >> h[i] >> x;
        for (int j = 1, y; j <= x; j++) {
            cin >> y;
            vec[i].push_back(y);
        }
        for (int j = 0; j < vec[i].size() - 1; j++) merge(merge_ID(vec[i][j]), merge_ID(vec[i][j + 1]));
        merge(merge_ID(vec[i][vec[i].size() - 1]), merge_ID(vec[i][0]));
    }
    if (findF(merge_ID(0)) != findF(merge_ID(-1))) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i <= m; i++)if (vec[i][0] == 0)add(S, ID(0, 0), h[i]);
    for (int t = 1;; t++) {
        for (int i = 1; i <= m; i++) {
            if (vec[i][t % vec[i].size()] != 0 && vec[i][(t - 1) % vec[i].size()] != -1)
                add(ID(vec[i][(t - 1) % vec[i].size()], t - 1), ID(vec[i][t % vec[i].size()], t), h[i]);
            else if (vec[i][t % vec[i].size()] == 0)add(S, ID(0, t), h[i]);
        }
        for (int i = 1; i <= n; i++)add(ID(i, t - 1), ID(i, t), inf);
        add(ID(-1, t), T, inf);
        while (BFS())ans += DFS(S, inf);
        if (ans >= k) {
            cout << t;
            return 0;
        }
    }
}

太空飞行计划问题

        最大权闭合子图问题，可参考上面的植物大战僵尸一题。本题更常规。
        先建一个二分图，将实验连向对应的仪器。实验点权值就是其对应的赞助费用，仪器权值就是它们的价格。在这个图上跑一遍最大权闭合子图的网络流即可。
        现在的问题就是如何求一种方案。如果实验对应的边被割，说明这个实验不再选用，如果仪器被割，说明购买这个仪器。是否被割可以通过权值是否为0来判断，这样就可以找出一种方案。

#include <bits/stdc++.h>

#define ID(x, t) ((1-(t))*m+x+2) //t:是不是实验
#define S 1
#define T 2
#define inf (1<<28)
using namespace std;
int pay[50], n, m, head[500000], ans, deep[500000], vis[500];
vector<int> vec[50], vvp;
queue<int> que;
struct Edge {
    int next, to, v;
} edge[800000];

inline void add(int x, int y, int v) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

int DFS(int x, int limit) {
    if (limit == 0 || x == T)return limit;
    int f, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (deep[edge[i].to] == deep[x] + 1 &&
            (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= f, edge[i ^ 1].v += f, flow += f, limit -= f;
            if (!limit)break;
        }
    }
    return flow;
}

bool BFS() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= n + m + 2; i++)deep[i] = inf;
    deep[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && deep[edge[i].to] == inf) {
                deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
                if (edge[i].to == T)return true;
            }
        }
    }
    return deep[T] != inf;
}

void DFS(int x) {
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (edge[i].v > 0 && !vis[edge[i].to])vis[edge[i].to] = 1, vvp.push_back(edge[i].to), DFS(edge[i].to);
    }
}

int main() {
    cin >> m >> n, memset(head, -1, sizeof(head)), getchar();
    for (int i = 1; i <= m; i++) {
        char ss[10000];
        memset(ss, 0, sizeof(ss)), cin.getline(ss, 1000), sscanf(ss, "%d", pay + i);
        int ulen = 0, tool;
        while (sscanf(ss + ulen, "%d", &tool) == 1) {
            if (ulen == 0)pay[i] = tool, add(S, ID(i, 1), pay[i]), ans += pay[i];
            else add(ID(i, 1), ID(tool, 0), inf);
            if (tool == 0)ulen++;
            else while (tool)tool /= 10, ulen++;
            ulen++;
        }
    }
    for (int i = 1, x; i <= n; i++)scanf("%d", &x), add(ID(i, 0), T, x);
    while (BFS())ans -= DFS(S, inf);
    vis[S] = 1, DFS(S);
    for (int i = 0; i < vvp.size(); i++)if (vvp[i] - 2 <= m)cout << vvp[i] - 2 << " ";
    cout << endl;
    for (int i = 0; i < vvp.size(); i++)if (vvp[i] - 2 > m)cout << vvp[i] - 2 - m << " ";
    cout << endl << ans;
    return 0;
}

航空路线问题

        简单的费用流。
        既然每一个地点只能走一次，那么就拆点，并在两个点之间连一条容量为1的边。从终点到起点的路可以看成从起点到终点的反向路，这样问题等价于找从起点到终点的两条路，使途经点数最多。
        可以认为起点就是源点，终点为汇点。将汇点的入边边权设置为2，可以保证两条路径。
        给边加上费用的限制（设置为-1），跑一遍费用流就可以了。
        注意本题需要特判起点终点直接相连的情况。

#include <bits/stdc++.h>

#define inf (1<<28)
#define ID(x, y) ((x-1)*2+y)
using namespace std;
struct Edge {
    int next, to, v, p;
} edge[100000];
int head[150], n, v, dis[150], flow[150], pre[150], vis[150], ans, minCost;
string name[150];
map<string, int> mmp;
queue<int> que;
vector<int> vvp;

inline void add(int x, int y, int v, int p) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

int SPFA() {
    for (int i = 1; i <= 2 * n; i++)dis[i] = inf, pre[i] = -1, vis[i] = 0;
    dis[1] = 0, que.push(1), vis[1] = 1, flow[1] = inf;
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dis[edge[i].to] > dis[f] + edge[i].p) {
                dis[edge[i].to] = dis[f] + edge[i].p, pre[edge[i].to] = i, flow[edge[i].to] = min(flow[f], edge[i].v);
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[2 * n] != -1;
}


void DFS(int x) {
    if (x % 2)vvp.push_back(x);
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (edge[i].v == 0 && !vis[edge[i].to] && edge[i].to > x) {
            vis[edge[i].to] = 1, DFS(edge[i].to);
            break;
        }
    }
}

int main() {
    cin >> n >> v, memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++) {
        cin >> name[i];
        mmp[name[i]] = i, add(ID(i, 1), ID(i, 2), i == 1 ? inf : (i == n ? 2 : 1), 0);
    }
    for (int i = 1; i <= v; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        if (mmp[s1] > mmp[s2])swap(s1, s2);
        add(ID(mmp[s1], 2), ID(mmp[s2], 1), 1, -1);
    }
    while (SPFA()) {
        int t = 2 * n;
        while (t != 1)edge[pre[t]].v -= flow[2 * n], edge[pre[t] ^ 1].v += flow[2 * n], t = edge[pre[t] ^ 1].to;
        ans += flow[2 * n], minCost += flow[2 * n] * dis[2 * n];
    }
    if (ans < 2) {
        for (int i = head[2]; ~i; i = edge[i].next) {
            if (edge[i].to == 2 * n - 1) {
                cout << 2 << endl << name[1] << endl << name[n] << endl << name[1];
                return 0;
            }
        }
        cout << "No Solution!";
        return 0;
    } else {
        cout << -minCost << endl, memset(vis, 0, sizeof(vis)), DFS(2);
        cout << name[1] << endl;
        for (int i = 0; i < vvp.size(); i++)cout << name[vvp[i] / 2 + 1] << endl;
        vvp.clear(), DFS(2);
        for (int i = vvp.size() - 1; i >= 0; i--)cout << name[vvp[i] / 2 + 1] << endl;
        cout << name[1] << endl;
    }
    return 0;
}

圆桌问题

可以说是很简单的最大流了。将每一个单位和圆桌看成点，从源点开始向所有单位连边，容量限制为每个单位的人数；从圆桌开始向汇点连边，容量限制为圆桌上最大的人数。然后每一个单位向所有圆桌分别连边，容量限制为1，表示最多只能去一人。建好图之后跑一遍最大流，如果最大流不足总人数则无解。
对于方案的输出根据原边的流量来判别。

#include <bits/stdc++.h>

#define ID(x, y) ((y)*m+x)
#define S (m+n+1)
#define T (m+n+2)
#define inf (1<<28)
using namespace std;
struct Edge {
    int next, to, v;
} edge[150 * 270 * 2 + 10000];
int head[150 + 270 + 10000], deep[150 + 270 + 10000], ans, sum, cur[150 + 270 + 10000];
int n, m;
queue<int> que;

void add(int x, int y, int v) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, head[y] = cnt++;
}

int DFS(int x, int limit) {
    if (x == T || limit == 0)return limit;
    int p, flow = 0;
    for (int i = head[x]; ~i; i = edge[i].next) {
        cur[x] = i;
        if (deep[edge[i].to] == deep[x] + 1 && (p = DFS(edge[i].to, min(limit, edge[i].v)))) {
            edge[i].v -= p, edge[i ^ 1].v += p, limit -= p, flow += p;
            if (!limit)break;
        }
    }
    return flow;
}

int BFS() {
    while (!que.empty())que.pop();
    for (int i = 1; i <= T; i++)deep[i] = inf, cur[i] = head[i];
    deep[S] = 0, que.push(S);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == T)return 1;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && deep[edge[i].to] == inf)deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
        }
    }
    return 0;
}

int main() {
    cin >> m >> n, memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)add(ID(i, 0), ID(j, 1), 1);
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        add(S, ID(i, 0), x), sum += x;
    }
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        add(ID(i, 1), T, x);
    }
    while (BFS())ans += DFS(S, inf);
    if (ans == sum)cout << 1 << endl;
    else {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = head[ID(i, 0)]; ~j; j = edge[j].next)
            if (edge[j].v == 0 && edge[j].to < S)
                cout << edge[j].to - m << " ";
        cout << endl;
    }
    return 0;
}

骑士共存问题

将格子看成点，骑士可以跳跃的两个点之间关系看成边，可以得到一个二分图，问题即为求这个二分图上的最大独立集。
答案就是点数与最大匹配的差，拿匈牙利算法就可以解决（~~诶，好像与网络流没多大关系~~）。

#include <bits/stdc++.h>

#define ID(x, y) ((x-1)*n+y)
using namespace std;
struct Edge {
    int to, next;
} edge[40000 * 16 + 100];
int n, m, head[40005], vis2[40005], be[40005], vis[40005], tim = 1, ans;
bool ss[40005];
const int X[] = {1, 2, 2, 1};
const int Y[] = {2, 1, -1, -2};

inline void add(int x, int y) {
    static int cnt = 0;
    if (ss[x] || ss[y])return;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

void DFS(int x, int y) {
    for (int i = head[ID(x, y)]; ~i; i = edge[i].next) {
        if (vis2[edge[i].to] == -1) {
            vis2[edge[i].to] = vis2[ID(x, y)] ^ 1;
            DFS((edge[i].to - 1) / n + 1, (edge[i].to - 1) % n + 1);
        }
    }
}

int f(int x) {
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (vis[edge[i].to] != tim) {
            vis[edge[i].to] = tim;
            if (be[edge[i].to] == 0 || f(be[edge[i].to])) {
                be[edge[i].to] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    cin >> n >> m, memset(vis2, -1, sizeof(vis2)), memset(head, -1, sizeof(head));
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        ss[ID(x, y)] = true;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int z = 0, xx, yy; z < 4; z++) {
                xx = i + X[z], yy = j + Y[z];
                if (xx >= 1 && xx <= n && yy >= 1 && yy <= n)add(ID(i, j), ID(xx, yy)), add(ID(xx, yy), ID(i, j));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)if (!ss[ID(i, j)] && vis2[ID(i, j)] == -1)vis2[ID(i, j)] = 0, DFS(i, j);
    for (int i = 1; i <= n * n; i++)if (vis2[i] == 1)ans += f(i), ++tim;
    cout << n * n - m - ans;
    return 0;
}

火星探险问题

很有意思的一题，比较肝的费用流。
考虑将所有点拆成三个。对于标记为1的点，这三个点都不使用；对于标记为0的点，只使用第一个分点；对于标记为2的点，这三个分点的用途如下：

第一个分点：用于接受流。
第二个分点：表明这个点已经过采集
第三个分点：表明这个点不再采集

从第一个分点向第二个分点连边，容量为1，费用为-1，同时向第三个分点连边，容量为无穷大，费用为0。对于地图上可以走的一条路径（向南或者向北）从出点出发（对于标记为2的点，其出点就是第2、3个分点，其余都是第1个分点）向入点连接（都是第1个分点），容量限制为无穷大，费用为0。设置一个源点，连接源点与坐标(1,1)的入点，容量限制为探测车数量，再连接右下角坐标点的出点与汇点，容量限制无穷大。建好图之后在上面跑最小费用最大流即可。
关于方案的输出，在跑完费用流后来一遍DFS即可。这里一个错误是根据每一次增广的路径来得到方案，这样做并不对，是因为反边的存在导致增广可能经过反边。

#include <bits/stdc++.h>

#define ID(x, y, z) ((x-1)*3*m+3*(y-1)+z)
#define S 3*m*n+1
#define T (S+1)
#define inf (1<<28)
#define X(x)  ((x - 1) / 3 / m + 1)
#define Y(y) ((y - 1) / 3 % m + 1)

using namespace std;
struct Edge {
    int to, next, v, p;
} edge[5000000];
int head[50000], n, m, p, op[50][50], pre[50000], flow[50000], vis[50000], dist[50000], t;
queue<int> que;
vector<int> vvp;

inline void add(int x, int y, int v, int p) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

inline int BFS() {
    for (int i = 1; i <= T; i++)pre[i] = -1, dist[i] = inf, vis[i] = 0;
    dist[S] = 0, que.push(S), vis[S] = 1, flow[S] = inf;
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dist[edge[i].to] > dist[f] + edge[i].p) {
                dist[edge[i].to] = dist[f] + edge[i].p, flow[edge[i].to] = min(flow[f], edge[i].v), pre[edge[i].to] = i;
                if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
            }
        }
    }
    return pre[T] != -1;
}

void DFS(int x, int rk) {
    if (X(x) == n && Y(x) == m)return;
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (i % 2)continue;
        if (op[X(x)][Y(x)] == 0 || x % 3 != 1) {
            if (edge[i].v < inf && (X(edge[i].to) - X(x) == 1 || Y(edge[i].to) - Y(x) == 1)) {
                if (X(edge[i].to) - X(x) == 1)cout << rk << " 0" << endl, DFS(edge[i].to, rk);
                else cout << rk << " 1" << endl, DFS(edge[i].to, rk);
                ++edge[i].v;
                return;
            }
        } else {
            if (edge[i].to == ID(X(x), Y(x), 2) && edge[i].v == 0) {
                DFS(edge[i].to, rk), ++edge[i].v;
                return;
            } else if (edge[i].to == ID(X(x), Y(x), 3) && edge[i].v < inf) {
                DFS(edge[i].to, rk), ++edge[i].v;
                return;
            }
        }
    }
}

int main() {
    cin >> p >> m >> n, memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> op[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (op[i][j] == 1)continue;
            if (op[i][j] == 2)add(ID(i, j, 1), ID(i, j, 2), 1, -1), add(ID(i, j, 1), ID(i, j, 3), inf, 0);
            if (i - 1 >= 1) {
                if (op[i - 1][j] == 0)add(ID(i - 1, j, 1), ID(i, j, 1), inf, 0);
                else if (op[i - 1][j] == 2)
                    add(ID(i - 1, j, 2), ID(i, j, 1), inf, 0), add(ID(i - 1, j, 3), ID(i, j, 1), inf, 0);
            }
            if (j - 1 >= 1) {
                if (op[i][j - 1] == 0)add(ID(i, j - 1, 1), ID(i, j, 1), inf, 0);
                else if (op[i][j - 1] == 2)
                    add(ID(i, j - 1, 2), ID(i, j, 1), inf, 0), add(ID(i, j - 1, 3), ID(i, j, 1), inf, 0);
            }
        }
    }
    if (op[n][m] == 2)add(ID(n, m, 2), T, inf, 0), add(ID(n, m, 3), T, inf, 0);
    else add(ID(n, m, 1), T, inf, 0);
    add(S, ID(1, 1, 1), p, 0);
    while (BFS()) {
        t = T;
        while (t != S)
            vvp.push_back(t), edge[pre[t]].v -= flow[T], edge[pre[t] ^ 1].v += flow[T], t = edge[pre[t] ^ 1].to;
    }
    for (int i = 1; i <= p; i++)DFS(ID(1, 1, 1), i);
    return 0;
}

最长k可重区间集问题（模板）

        一个重要的模板。
        首先对坐标点进行离散化。具体方法是将所有点排序，然后重新标号，容易知道离散化后的区间序列与原先等价，但坐标可以压缩至$[1,2n]$这个区间内。
        建图方式如下：

$S->1$，源点连接一号点（将2n个坐标看成点），容量限制为$k$，费用为0。
对于每一个点，向后继点连接一条边，容量限制无穷大，费用0。
对于每一个区间，连接$l->r$，容量为1，费用为其长度的相反数。
$2n->T$，表示接受流，容量限制无穷大，费用0。

        对图的理解：区间加边可以支走一部分流量，由于一开始流量为$k$的限制，一旦某一部分已经将流量全部支配走，就不能再支配新的流量。这个条件便可以满足k重的约束。
        在这个图上跑一遍最小费用最大流即可，答案就是最小费用的相反数。
        注意：当某一个区间左右端点相同时，由于这是开区间，忽略掉这个区间即可。

#include<bits/stdc++.h>

#define S 0
#define T (n<<1|1)
#define inf (1<<28)
using namespace std;
struct Node {
    int l, r, k;
} node[505];
struct Edge {
    int to, next, v, p;
} edge[15000];
set<int> ssp;
map<int, int> mmp;
int ID = 1, n, k, head[1500], flow[1500], pre[1500], dis[1500], vis[1500];
queue<int> que;

inline int BFS() {
    for (int i = S; i <= T; i++)pre[i] = -1, dis[i] = inf, vis[i] = 0;
    dis[S] = 0, que.push(S), vis[S] = 1, flow[S] = inf;
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dis[edge[i].to] > dis[f] + edge[i].p) {
                dis[edge[i].to] = dis[f] + edge[i].p, flow[edge[i].to] = min(flow[f], edge[i].v), pre[edge[i].to] = i;
                if (!vis[edge[i].to])vis[edge[i].to] = 1, que.push(edge[i].to);
            }
        }
    }
    return pre[T] != -1;
}

inline void add(int x, int y, int v, int p) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

int main() {
    cin >> n >> k, memset(head, -1, sizeof(head));
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;
        if (x > y)swap(x, y);
        node[i].l = x, node[i].r = y, ssp.insert(x), ssp.insert(y), node[i].k = y - x;
    }
    for (int x:ssp)mmp[x] = ID++;
    for (int i = 1; i <= n; i++)node[i].l = mmp[node[i].l], node[i].r = mmp[node[i].r];
    for (int i = 1; i < (n << 1); i++)add(i, i + 1, inf, 0);
    add(S, 1, k, 0), add(n << 1, T, inf, 0);
    for (int i = 1; i <= n; i++)add(node[i].l, node[i].r, 1, -node[i].k);
    int ans = 0, minCost = 0;
    while (BFS()) {
        int to = T;
        while (to != S)edge[pre[to]].v -= flow[T], edge[pre[to] ^ 1].v += flow[T], to = edge[pre[to] ^ 1].to;
        ans += flow[T], minCost += flow[T] * dis[T];
    }
    cout << -minCost;
    return 0;
}

最长k可重线段集问题（模板）

和上一题类似，思路大致相同，这里只不过将费用换为长度的相反数来求，求长度要用到勾股定理。
另外一个区别是，在本题中，如果两个端点的横坐标相同，这个坐标点仍然是被覆盖的，不能忽略。但是如果将它加入到图中，会出现负环，导致SPFA过程不断进行，然后死循环卡T。这里的解决方法是将点拆分为2，分为入点和出点，对于这种端点横坐标相同的线段，直接从该点对应入点出发向出点连边即可，这样可以有效避免上面的问题。

#include<bits/stdc++.h>

#define S 0
#define inf (1<<28)
#define ID(x, y) ((((x)-1)<<1)+y)
#define T (ID(n<<1,2)+1)
using namespace std;
struct Node {
    int l, r, k;
} node[505];
struct Edge {
    int to, next, v, p;
} edge[15000];
set<int> ssp;
map<int, int> mmp;
int ID = 1, n, k, head[3000], flow[3000], pre[3000], dis[3000], vis[3000];
queue<int> que;

inline int BFS() {
    for (int i = S; i <= T; i++)pre[i] = -1, dis[i] = inf, vis[i] = 0;
    dis[S] = 0, que.push(S), vis[S] = 1, flow[S] = inf;
    while (!que.empty()) {
        int f = que.front();
        que.pop(), vis[f] = 0;
        for (int i = head[f]; ~i; i = edge[i].next) {
            if (edge[i].v > 0 && dis[edge[i].to] > dis[f] + edge[i].p) {
                dis[edge[i].to] = dis[f] + edge[i].p, flow[edge[i].to] = min(flow[f], edge[i].v), pre[edge[i].to] = i;
                if (!vis[edge[i].to])vis[edge[i].to] = 1, que.push(edge[i].to);
            }
        }
    }
    return pre[T] != -1;
}

inline void add(int x, int y, int v, int p) {
    static int cnt = 0;
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, edge[cnt].p = p, head[x] = cnt++;
    edge[cnt].to = x, edge[cnt].next = head[y], edge[cnt].v = 0, edge[cnt].p = -p, head[y] = cnt++;
}

int main() {
    cin >> n >> k, memset(head, -1, sizeof(head));
    for (int i = 1, a, b, c, d; i <= n; i++) {
        cin >> a >> b >> c >> d;
        node[i].k = (int) (sqrt((1ll * c - a) * (1ll * c - a) + (1ll * d - b) * (1ll * d - b)));
        if (a > c)swap(a, c);
        node[i].l = a, node[i].r = c, ssp.insert(a), ssp.insert(c);
    }
    for (int x:ssp)mmp[x] = ID++;
    for (int i = 1; i <= n; i++)node[i].l = mmp[node[i].l], node[i].r = mmp[node[i].r];
    for (int i = 1; i < (n << 1); i++)add(ID(i, 2), ID(i + 1, 1), inf, 0), add(ID(i, 1), ID(i, 2), inf, 0);
    add(S, ID(1, 1), k, 0), add(ID(n << 1, 2), T, inf, 0), add(ID(n << 1, 1), ID(n << 1, 2), inf, 0);
    for (int i = 1; i <= n; i++) {
        if (node[i].l != node[i].r)add(ID(node[i].l, 2), ID(node[i].r, 1), 1, -node[i].k);
        else add(ID(node[i].l, 1), ID(node[i].r, 2), 1, -node[i].k);
    }
    long long ans = 0, minCost = 0;
    while (BFS()) {
        int to = T;
        while (to != S)edge[pre[to]].v -= flow[T], edge[pre[to] ^ 1].v += flow[T], to = edge[pre[to] ^ 1].to;
        ans += flow[T], minCost += flow[T] * dis[T];
    }
    cout << -minCost;
    return 0;
}