[Codeforces]CF1430G题解
本文最后更新于 103 天前,其中的信息可能已经有所发展或是发生改变。

一道有趣的网络流题目。

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$ 的边。
那么在对应的权值点间连无穷边即可加上限制,方式多样,具体看图:

buildgraph

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

代码

最后求方案,可以在残量网络上从源点开始深搜,找到 $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;
}
本文标题:[Codeforces]CF1430G题解
本文作者:Clouder
本文链接: https://www.codein.icu/cf1430g/
转载请标明。

评论

  1. 3月前
    2020-10-13 3:08:40

    tql 您都会网络流啦

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇