题解 SS230928C【构造】

https://notes.sshwy.name/Math/Linear-Algbra/LP-and-its-Dual/

线性规划好题

problem

有一个 \(n\) 个点 \(m\) 条边的有向图，你需要给每个点赋一个整数权 \(val_i \in [1, n + 1)\)，并且使得每条边 \((u \rightarrow v)\) 都有 \(val_u < val_v\)。

我们希望这张图的 \(\sum_{(u \rightarrow v)} val_v - val_u\) 最小。输出这个最小值和构造方案。若无解，输出 \(NIE\)。\(n\leq 300,m\leq 1500\)。

solution 0 \(O(3^n)\)

考虑 DP，\(f(S)\) 表示现在已经填完 \(S\) 中点的 \(val\)，然后枚举一个子集 \(T\)，使得这个子集填上同一个数，而且不能存在 \(T\) 到 \(S\setminus T\) 的边。在计算贡献的时候，不如提前将后面的贡献算了，然后也不用记下当前填的是什么数字，才能通过 \(n\leq 16\)。

solution 1 (part 1)

线性规划：

\[\begin{aligned} &\text{minimize}&\sum_{i=1}^n(inn_i-out_i)val_i,\\ &\text{s.t.}&\forall(u\to v),val_u<val_v\implies val_v-val_u\geq 1\\ &&val_i\geq 1 \end{aligned} \]

不妨写的更加线性规划一点，设：（记 \(\mathbf A\) 为向量，\(\mathbf A^T\) 是 \(\mathbf A\) 的转置）

\(\mathbf x\) 是一个 \(n\times 1\) 的列向量，\(\mathbf x_i=val_i-1\)。
\(\mathbf c\) 是一个 \(n\times 1\) 的列向量，\(\mathbf c_i=inn_i-out_i\)。
\(A\) 是一个 \(m\times n\) 的矩阵，满足对于第 \(1\leq j\leq m\) 条边 \((u,v)\) 有 \(A_{ju}=-1, A_{jv}=1\)。
\(\mathbf b\) 是一个 \(m\times 1\) 的列向量，\(\mathbf b_j=1\)。

则原问题为：

\[\begin{aligned} &\text{minimize}& \mathbf c^T\mathbf x\\ &\text{s.t.}& A\mathbf x\geq \mathbf b,\mathbf x\geq 0 \end{aligned} \]

其中 \(\mathbf x\geq 0\) 表示 \(\forall x_i\geq 0\)。

这个问题的对偶问题是：

\[\begin{aligned} &\text{maximize}& \mathbf b^T\mathbf y\\ &\text{s.t.}& A^T\mathbf y\leq \mathbf c^T,\mathbf y\geq 0 \end{aligned} \]

其中 \(\mathbf y\) 是我们新加的 \(m\times 1\) 的未知列向量。

（如果你无法理解，就尝试用矩阵的维数乘一下看看乘出来是什么。\(\mathbf c^T\mathbf x\) 实际上是向量 \(\mathbf c,\mathbf x\) 内积。）

弱对偶定理：\(\mathbf c^T\mathbf x\) 的任意一组解 \(\geq \mathbf b^T\mathbf y\)。

强对偶定理：\(\min \mathbf c^T\mathbf x=\max \mathbf b^T\mathbf y\)。

（注意这个题和平时见到的线性规划的不等号方向是全部反的，不过还是 \(\min\) 配 \(\geq\)，\(\max\) 配 \(\leq\)）

solution 1 (part 2)

\[\begin{aligned} &\text{maximize}& \mathbf b^T\mathbf y\\ &\text{s.t.}& A^T\mathbf y\leq \mathbf c^T,\mathbf y\geq 0 \end{aligned} \]

这是什么？

不妨将 \(\mathbf y\) 看作是关于边的什么东西，它的要求是：

最大化 \(\sum \mathbf y_i\)。
观察 \(A^T\mathbf y\)，它是 \(1\times n\) 向量，\((A^T\mathbf y)_i=\sum_{j}A_{ji}\mathbf y_j\)。，即对于每个点 \(i\)，它的出边的 \(\mathbf y_j\) 的和减去入边的 \(\mathbf y_j\) 的和需要 \(\leq inn_i-out_i\)。
\(\mathbf y_j\geq 0\)。

这很像网络流啊，很像啊！！！这是最大流！！！因为还有个最大化在，我们跑最大流；因为第二条，我们想通过源汇使得每个点流量平衡，然后要把第一条换成费用。

具体来说，对于原图的边，连一条流量无穷费用为一的边；然后，我们需要让每个点保有至多 \(inn_i-out_i\) 的流量，为了流量平衡，如果 \(inn_i>out_i\) 我们就向汇点连 \(inn_i-out_i\) 的流量，费用为零的边；如果 \(inn_i<out_i\) 我们就从源点向这个点连 \(out_i-inn_i\) 的边。然后跑最大费用最大流。这样每个点多余的流量就不能超过 \(inn_i-out_i\)，网络流模型正确，对偶模型可以求解，原问题得解。

关于方案：

std 做法：对于所有流过流量的边都有两端 \(val\) 差值为 \(1\) 从而可以跑差分约束。
发现对 dijkstra 实现的原始对偶费用流，直接取最终的势能就是解，需要小小特判一下 \(\infty\) 问题（看作 \(0\)）

code

solution 0

#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int getBit(int k) { return 1 << k; }
bool conBit(int x, int k) { return x & getBit(k); }
bool checkIn(int x, int y) { return (x & y) == x; }
int n, m, K[310], U, s[1 << 16];
int g[310];
int f[1 << 16], pre[1 << 16];
int plan[310];
int dfs(int S) {
    if (S == U) return 0;
    if (~f[S]) return f[S];
    int ans = 1e9;
    int E = 0;
    for (int j = 0; j < n; j++) if (!conBit(S, j) && checkIn(g[j], S)) E |= getBit(j);
    for (int T = E; T; T = (T - 1) & E) {
        int ret = dfs(S | T) + s[U ^ S];
        if (ret < ans) ans = ret, pre[S] = T;
    }
    if (ans == 1e9) ans = 2e9;
    return f[S] = ans;
}
int mian() {
    scanf("%d%d", &n, &m), U = (1 << n) - 1;
    memset(K, 0, sizeof K);
    memset(g, 0, sizeof g);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v), u--, v--;
        g[v] |= getBit(u);
        K[u] -= 1, K[v] += 1;
    }
    s[0] = 0;
    for (int i = 0; i < n; i++) s[1 << i] = K[i];
    auto lowbit = [](int x) { return x & -x; };
    for (int i = 1; i < 1 << n; i++) s[i] = s[lowbit(i)] + s[i ^ lowbit(i)];
    memset(f, -1, sizeof f);
    memset(plan, 0, sizeof plan);
    int ret = dfs(0);
    if (ret == 2e9) return puts("NIE"), 0;
    printf("%d\n", ret);
    for (int S = 0, i = 0; i <= n; S |= pre[S], i++) {
        for (int j = 0; j < n; j++) if (conBit(S, j) && !plan[j]) plan[j] = i;
    }
    for (int i = 0; i < n; i++) printf("%d%c", plan[i], " \n"[i == n - 1]);
    return 0;
}
int main() {
    int T;
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
    scanf("%d", &T);
    while (T--) mian();
    return 0;
}

solution 1 差分约束得解

#include <queue>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
#include <functional>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <int N, int M, class Type>
struct graph {
    int head[N + 10], nxt[M << 1], cnt;
    struct edge { int u, v; Type w; } e[M << 1];
    graph() { clear(); }
    void clear() { cnt = 0, memset(head, 0, sizeof head); }
    edge& operator[](int i) { return e[i]; }
    void add(int u, int v, Type w) { e[++cnt] = {u, v, w}, nxt[cnt] = head[u], head[u] = cnt; }
    void link(int u, int v, Type w) { add(u, v, w), add(v, u, w); }
};
template <int N, int M, class Cap, class Cost>
struct mincostflow {
    graph<N, M, pair<Cap, Cost>> g;
    mincostflow() { clear(); }
    void clear() { g.clear(), g.cnt += 1; }
    void add(int u, int v, Cap cap, Cost cost) {
        g.add(u, v, {cap, cost});
        g.add(v, u, {0, -cost});
    }
    int pre[N + 10];
    Cost dis[N + 10];
    void spfa(int s) {
        static bool vis[N + 10];
        queue<int> q;
        memset(dis, 0x3f, sizeof dis);
        memset(vis, 0, sizeof vis);
        for (q.push(s), dis[s] = pre[s] = 0; !q.empty(); ) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i = g.head[u]; i; i = g.nxt[i]) {
                int v = g[i].v;
                if (g[i].w.first && dis[v] > dis[u] + g[i].w.second) {
                    dis[v] = dis[u] + g[i].w.second;
                    pre[v] = i;
                    if (!vis[v]) vis[v] = 1, q.push(v);
                }
            }
        }
    }
    pair<Cap, Cost> mcmf(int s, int t, Cap flow) {
        pair<Cap, Cost> res = {0, 0};
        while (spfa(s), dis[t] < dis[0] && flow) {
            Cap run = flow;
            for (int i = pre[t]; i; i = pre[g[i].u])
                run = min(run, g[i].w.first);
            for (int i = pre[t]; i; i = pre[g[i].u])
                g[i].w.first -= run, g[i ^ 1].w.first += run;
            res.first += run, res.second += run * dis[t];
        }
        return res;
    }
};
int n, m;
int inn[400], out[400];
mincostflow<400, 2000, int, int> F;
graph<400, 2000, int> g, t;
bool toposort() {
    static int inn[400];
    queue<int> q;
    memset(inn, 0, sizeof inn);
    for (int i = 1; i <= g.cnt; i++) inn[g[i].v] += 1;
    for (int i = 1; i <= n; i++) if (!inn[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = g.head[u]; i; i = g.nxt[i]) {
            int v = g[i].v;
            if (--inn[v] == 0) q.push(v);
        }
    }
    return all_of(inn + 1, inn + n + 1, [](int x) { return x == 0; });
}
int dis[400];
void spfa(int s) {
    static bool vis[400];
    queue<int> q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    for (q.push(s), dis[s] = 0; !q.empty(); ) {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for (int i = t.head[u]; i; i = t.nxt[i]) {
            int v = t[i].v;
            if (dis[v] > dis[u] + t[i].w) {
                dis[v] = dis[u] + t[i].w;
                if (!vis[v]) vis[v] = 1, q.push(v);
            }
        }
    }
}
int mian() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        inn[v] += 1, out[u] += 1;
        F.add(u, v, 1e9, -1);
        g.add(u, v, 0);
        t.add(v, u, -1);//dis[u] + 1 <= dis[v]
    }
    if (!toposort()) return puts("NIE"), 0;
    int S = n + 1, T = n + 2;
    for (int i = 1; i <= n; i++) {
        int del = inn[i] - out[i];
        if (del > 0) F.add(i, T, del, 0);
        else F.add(S, i, -del, 0);
    }
    printf("%d\n", -F.mcmf(S, T, 1e9).second);
    for (int i = 3; i <= F.g.cnt; i += 2) {
        if (F.g[i].w.first) t.add(F.g[i].v, F.g[i].u, 1);
    }
    for (int i = 1; i <= n; i++) t.add(n + 1, i, 0);
    spfa(n + 1);
    int mind = *min_element(dis + 1, dis + n + 1);
    for (int i = 1; i <= n; i++) printf("%d%c", dis[i] - mind + 1, " \n"[i == n]);
    return 0;
}
void reset() {
    F.clear(), g.clear(), t.clear();
    memset(inn, 0, sizeof inn);
    memset(out, 0, sizeof out);
}
int main() {
#ifndef LOCAL
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while (T--) reset(), mian();
    return 0;
}

solution 1 势能

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <class T>
using pqueue = priority_queue<T, vector<T>, greater<T>>;
template <int N, int M, class Type>
struct graph {
    int head[N + 10], nxt[M << 1], cnt;
    struct edge {
        int u, v;
        Type w;
    } e[M << 1];
    graph() { clear(); }
    void clear() { cnt = 0, memset(head, 0, sizeof head); }
    edge& operator[](int i) { return e[i]; }
    void add(int u, int v, Type w) {
        e[++cnt] = {u, v, w}, nxt[cnt] = head[u], head[u] = cnt;
    }
    void link(int u, int v, Type w) { add(u, v, w), add(v, u, w); }
};
template <int N, int M, class Cap, class Cost>
struct mincostflow {
    graph<N, M, pair<Cap, Cost>> g;
    int pre[N + 10], tot;
    Cost h[N + 10], dis[N + 10];
    bool vis[N + 10];
    mincostflow() { clear(); }
    void clear(int n = 0) { g.clear(), g.cnt += 1, tot = n; }
    void add(int u, int v, Cap cap, Cost cost) {
        g.add(u, v, {cap, cost});
        g.add(v, u, {0, -cost});
    }
    bool spfa(int s, int t) {
        static int app[N + 10];
        queue<int> q;
        memset(h, 0x3f, sizeof h);
        memset(vis, 0, sizeof vis);
        memset(app, 0, sizeof app);
        for (q.push(s), h[s] = 0; !q.empty();) {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (int i = g.head[u]; i; i = g.nxt[i]) {
                int v = g[i].v;
                if (g[i].w.first && h[v] > h[u] + g[i].w.second) {
                    h[v] = h[u] + g[i].w.second;
                    if (!vis[v]) {
                        if (++app[v] >= tot) return 0;
                        vis[v] = 1, q.push(v);
                    }
                }
            }
        }
        return h[t] < h[0];
    }
    bool dijkstra(int s, int t) {
        pqueue<pair<Cost, int>> q;
        memset(dis, 0x3f, sizeof dis);
        memset(vis, 0, sizeof vis);
        for (q.push({dis[s] = 0, s}); !q.empty();) {
            int u = q.top().second;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = g.head[u]; i; i = g.nxt[i]) {
                int v = g[i].v;
                Cost w = g[i].w.second + h[u] - h[v];
                if (g[i].w.first && dis[v] > dis[u] + w) {
                    pre[v] = i;
                    q.push({dis[v] = dis[u] + w, v});
                }
            }
        }
        return vis[t];
    }
    pair<Cap, Cost> mcmf(int s, int t, Cap flow) {
        pair<Cap, Cost> res = {0, 0};
        if (!spfa(s, t)) throw "The min-cost-flow problem can't be solved.";
        for (int i = 1; i <= tot; i++) if (h[i] == h[0]) h[i] = 0;
        while (flow && dijkstra(s, t)) {
            for (int i = 1; i <= tot; i++) debug("%d%c", h[i], " \n"[i == tot]);
            for (int i = 1; i <= tot; i++) if (dis[i] < dis[0]) h[i] += dis[i];
            Cap run = flow;
            for (int i = pre[t]; i; i = pre[g[i].u])
                run = min(run, g[i].w.first);
            for (int i = pre[t]; i; i = pre[g[i].u])
                g[i].w.first -= run, g[i ^ 1].w.first += run;
            res.first += run, res.second += run * h[t];
        }
        return res;
    }
};
int n, m;
int inn[400], out[400];
mincostflow<400, 2000, int, int> F;
graph<400, 2000, int> g, t;
bool toposort() {
    static int inn[400];
    queue<int> q;
    memset(inn, 0, sizeof inn);
    for (int i = 1; i <= g.cnt; i++) inn[g[i].v] += 1;
    for (int i = 1; i <= n; i++)
        if (!inn[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = g.head[u]; i; i = g.nxt[i]) {
            int v = g[i].v;
            if (--inn[v] == 0) q.push(v);
        }
    }
    return all_of(inn + 1, inn + n + 1, [](int x) { return x == 0; });
}
int mian() {
    scanf("%d%d", &n, &m);
    F.tot = n;
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        inn[v] += 1, out[u] += 1;
        F.add(u, v, 1e9, -1);
        g.add(u, v, 0);
    }
    if (!toposort()) return puts("NIE"), 0;
    int S = ++F.tot, T = ++F.tot;
    for (int i = 1; i <= n; i++) {
        int del = inn[i] - out[i];
        if (del > 0)
            F.add(i, T, del, 0);
        else
            F.add(S, i, -del, 0);
    }
    F.tot = n + 2;
    printf("%d\n", -F.mcmf(S, T, 1e9).second);
    for (int i = 1; i <= n; i++) debug("%d%c", F.h[i], " \n"[i == n]);
    debug("=====================================================\n");
    for (int i = 1; i <= n; i++) F.h[i] *= -1;
    int mind = *min_element(F.h + 1, F.h + n + 1);
    for (int i = 1; i <= n; i++)
        printf("%d%c", F.h[i] - mind + 1, " \n"[i == n]);
    return 0;
}
void reset() {
    F.clear(), g.clear(), t.clear();
    memset(inn, 0, sizeof inn);
    memset(out, 0, sizeof out);
}
int main() {
#ifndef LOCAL_NOFILE
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while (T--) reset(), mian();
    return 0;
}