一道有趣的网络流题目。

Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cf1430g/

题意

给定一个有向无环图，每条边都有 $w_i$ 的权重，给每个点分配权值 $a_i$，对于每条连接 $(u,v)$ 的边，定义其权值为 $b_i = a_u – a_v$，要求：

1. $b_i > 0$
2. $w_i \times b_i$ 最小

输出一种分配方案。

解法

听说方法多多，这里是一种网络流最小割的解法。
首先将边权贡献转化为点权贡献。

$\sum w_i \times (a_u – a_v)$

拆开后，将 $w_i$ 记到 $u$ 点权的权重，将 $-w_i$ 记到 $v$ 点权的权重。

现在只需要给点分配权值，就能计算出总贡献。

点权结论

有一个结论：所有点的权值都在 $[0,n – 1]$ 中。
要求 $b_i > 0$，就是要求 $a_u > a_v$，感性理解：按拓扑序来分配权值，最劣是一条链的情况，依次为 $n,n-1,\ldots,0$
还有 Codeforces 官方证明：
对于某一个值 $k$，如果存在 $a_i > k$ 而 $a_j < k$，且不存在 $a_g = k$，可以将 $> k$ 的权值都减小 $1$，而不会改变 $b$ 数组。
因此所有点的权值都是连续的，即不存在 $0,1,3,\ldots$ 这样的分配方式，否则一定可以将 $3,\ldots$ 整体减小 $1$.
那么最劣情况就是点权互不相同，值域为 $[0,n-1]$

建模

将点拆成一条链，每条边代表给该点选择一个权值，在链的一端连源点，另一端连汇点，边的容量为选择权值对应的贡献，跑最小割，割掉哪条边就选择了哪个权值。
接下来将原图中的边的限制加上。
只需要保证 $a_u > a_v$ 即可，就是要保证割了 $u$ 的权值为 $i$ 的边后，不能割 $v$ 的权值 $\ge i$ 的边。
那么在对应的权值点间连无穷边即可加上限制，方式多样，具体看图：

给边赋值容量为该点选择该权值获得的贡献，即转化后的点权乘上权值。
注意到转化后点权可能为负数，因此给容量整体加上一个较大值，平移为正数。

代码

最后求方案，可以在残量网络上从源点开始深搜，找到 $S$ 点集内的所有点。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
using namespace std;
const int bufSize = 1e6;
#define int long long
inline char nc()
{
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 510, maxm = 1e5;
struct node
{
    int to, next, cap;
} E[maxm];
int head[maxn], tot = 1;
inline void add(int x, int y, int cap)
{
    E[++tot].next = head[x], head[x] = tot, E[tot].to = y, E[tot].cap = cap;
    E[++tot].next = head[y], head[y] = tot, E[tot].to = x, E[tot].cap = 0;
}
int n, m, w[maxn], in[maxn];
int s, t, id[maxn][maxn], cnt, dep[maxn], cur[maxn];
int q[maxn], qt, qh;
bool bfs()
{
    for (int i = 1; i <= cnt; ++i) dep[i] = 0, cur[i] = head[i];
    qh = 1, q[qt = 1] = s, dep[s] = 1;
    while (qt >= qh)
    {
        int u = q[qh++];
        if (u == t) return 1;
        for (int p = head[u], v; p; p = E[p].next) 
            if (!dep[v = E[p].to] && E[p].cap) dep[v] = dep[u] + 1, q[++qt] = v;
    }
    return 0;
}
int dfs(int u, int flow)
{
    if (u == t || !flow) return flow;
    int sumflow = 0;
    for (int &p = cur[u], v, vflow; p; p = E[p].next)
        if (dep[v = E[p].to] == dep[u] + 1 && E[p].cap && (vflow = dfs(v, min(E[p].cap, flow))))
        {
            E[p].cap -= vflow, E[p ^ 1].cap += vflow, sumflow += vflow, flow -= vflow;
            if (flow == 0) break;
        }
    return sumflow;
}
const int inf = 1ll << 60;
const int big = 1ll << 10;
bool vis[maxn];
void dfs2(int u)
{
    vis[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (!vis[v] && E[p].cap > 0) dfs2(v);
    }
}
signed main()
{
    read(n), read(m);
    s = ++cnt, t = ++cnt;
    for (int i = 1; i <= n; ++i) for (int j = 0; j <= n; ++j) id[i][j] = ++cnt;
    for (int i = 1, a, b, c; i <= m; ++i)
    {
        read(a), read(b), read(c), in[b]++, w[a] += c, w[b] -= c;
        for (int j = 0; j < n; ++j) add(id[b][j], id[a][j + 1], inf);
    }
    for (int i = 1; i <= n; ++i)
    {
        add(s, id[i][0], inf), add(id[i][n], t, inf);
        for (int j = 0; j < n; ++j) add(id[i][j], id[i][j + 1], w[i] * j + big);
    }
    while (bfs()) dfs(s, inf);
    dfs2(s);
    for (int i = 1; i <= n; ++i)
    {
        int ans = 0;
        for (int j = 0; j <= n; ++j) if (vis[id[i][j]]) ans = j;
        printf("%lld ", ans);
    }
    return 0;
}