题目链接：HDU 6598

在一个军队里有 $n$ 名士兵。每名士兵需要分配一个任务：Mage 或 Warrior。这些士兵中有 $m$ 对士兵有良好的凝聚力。如果这两名士兵都参加 Warrior 任务，军队的效率会增加 $a$；如果这两名士兵都参加 Mage 任务，军队的效率会增加 $c$；否则军队的效率会增加 $b = \frac{a}{4} + \frac{c}{3}$（保证 $4 \mid a, 3 \mid c$）。

你需要求出军队效率的最大值。

本题有多组数据。

数据范围：$1 \le n \le 500$，$0 \le m \le 10 ^ 4$，$1 \le a, b \le 4 \times 10 ^ 6$，$\sum n \le 5 \times 10 ^ 3$，$\sum m \le 5 \times 10 ^ 4$。

Solution

考虑「网络流」。

我们对于点 $u, v$ 建立如下网络图（我才不会告诉你们图片是从官方题解搬来的）：

设三种贡献分别为 $A, B, C$，通过最小割的实际意义，我们建立方程：

$$ \begin{cases} a + b = A + B \\ c + d = C + B \\ a + d + e = A + C \\ b + c + e = A + C \end{cases} $$

解得一组解为：

$$ \begin{cases} a = b = \frac{A + B}{2} \\ c = d = \frac{C + B}{2} \\ e = \frac{A + C - 2B}{2} \end{cases} $$

直接跑最小割即可。

时间复杂度：$\mathcal O(n ^ {2} m)$。

Code

#include <cstdio>
#include <algorithm>
#include <queue>

const int N = 5e2 + 5, M = 1e4 + 5;
const int INF = 0x7f7f7f7f;

int n, m, vs[N], vt[N];

template <class Tp, int N, int M, bool opt>
struct Network {
    static const int INF = 0x7f7f7f7f;

    int n, tot = 1, lnk[N], cur[N], ter[M], nxt[M], dis[N];
    Tp cap[M], flow[M];

    void clear() {
        std::fill(lnk + 1, lnk + n + 1, 0);
        n = 0, tot = 1;
    }
    void addEdge(int u, int v, Tp w) {
        ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
        cap[tot] = w, flow[tot] = 0;
    }
    void addArc(int u, int v, Tp w) {
        addEdge(u, v, w), addEdge(v, u, 0);
    }
    #if opt
    Tp dif[N];
    void addArc(int u, int v, Tp l, Tp r) {
        dif[u] -= l, dif[v] += l, addArc(u, v, r - l);
    }
    #endif
    bool bfs(int s, int t) {
        std::queue<int> q;
        std::fill(dis + 1, dis + n + 1, INF);
        std::copy(lnk + 1, lnk + n + 1, cur + 1);
        dis[s] = 0, q.push(s);
        for (; !q.empty(); ) {
            int u = q.front();
            q.pop();
            for (int i = lnk[u]; i; i = nxt[i]) {
                int v = ter[i];
                if (cap[i] > flow[i] && dis[v] == INF) {
                    dis[v] = dis[u] + 1, q.push(v);
                }
            }
        }
        return dis[t] < INF;
    }
    Tp dfs(int u, int t, Tp f) {
        if (u == t) return f;
        Tp ans = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] > flow[i] && dis[v] == dis[u] + 1) {
                Tp x = dfs(v, t, std::min(f, cap[i] - flow[i]));
                flow[i] += x, flow[i ^ 1] -= x, f -= x, ans += x;
                if (f == 0) break;
            }
        }
        return ans;
    }
    Tp dinic(int s, int t) {
        Tp ans = 0;
        for (; bfs(s, t); ) {
            for (Tp x; (x = dfs(s, t, INF)); ans += x);
        }
        return ans;
    }
};

Network<long long, N, 4 * N + 4 * M, false> F;

int main() {
    for (; scanf("%d%d", &n, &m) == 2; ) {
        F.clear();
        int s = n + 1, t = F.n = n + 2;
        std::fill(vs + 1, vs + n + 1, 0);
        std::fill(vt + 1, vt + n + 1, 0);
        long long ans = 0;
        for (int i = 1, u, v, a, b, c; i <= m; i++) {
            scanf("%d%d%d%d%d", &u, &v, &a, &b, &c);
            vs[u] += a + b, vs[v] += a + b;
            vt[u] += b + c, vt[v] += b + c;
            F.addArc(u, v, a + c - b - b);
            F.addArc(v, u, a + c - b - b);
            ans += a + b + c;
        }
        for (int i = 1; i <= n; i++) {
            F.addArc(s, i, vs[i]);
            F.addArc(i, t, vt[i]);
        }
        printf("%lld\n", ans - F.dinic(s, t) / 2);
    }
    return 0;
}