Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

模拟费用流

Posted on Edited on

这东西强，好用，就是难（其实是本人太菜了）。

简介

当一类问题被转化成费用流时，一般来讲时间复杂度的上限是 $O(n^2m)$ 只要出题人想卡，分分钟卡掉（前提是出题人能写出更优的算法，这种都不是人），在这类分支中就有一类优化：模拟费用流。

过于抽象，从模板题讲起走。

例题：

P5470 [NOI2019] 序列

不难想到这是费用流，但观察数据范围发现貌似并不可过。

image

由此建图可以跑满暴力分，高贵的 $dinic$ 连暴力分都没有跑满，在 $48$ 分在折戟沉沙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 5, M = 2e6 + 5;
const LL Inf = 0x3f3f3f3f;
int idx = 1;
int e[M], ne[M], h[N], w[M], cost[M];
void add(int x, int y, int z, int c)
{
	idx ++;
	e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z, cost[idx] = c;
}
void addage(int x, int y, int z, int c)
{
	add(x, y, z, c), add(y, x, 0, -c);
}
int n, m, S, T;
int dis[N], now[N];
int vis[N];
LL ret;
bool bfs()
{
	queue<int>q;
	memset(dis, 0x3f, sizeof(dis));
	memcpy(now, h, sizeof(now));
	memset(vis, 0, sizeof(vis));
	q.push(S);
	dis[S] = 1;
	dis[0] = 0;
	while(!q.empty())
	{
		int o = q.front();
		q.pop();
		vis[o] = 0;
		for(int i = h[o]; ~i;i = ne[i])
		{
			int j = e[i];
			if(w[i] && dis[j] > dis[o] + cost[i])
			{
				dis[j] = dis[o] + cost[i];
				if(!vis[j]) q.push(j), vis[j] = 1;
			}
		}
	}
	return dis[T] != Inf;
}
LL dfs(int x, LL last)
{
	if(x == T || !last) return last;
	LL rest = last, k;
	vis[x] = 1;
	for(int i = now[x]; ~i && rest; i = ne[i])
	{
		now[x] = i;
		int j = e[i];
		if(!vis[j] && w[i] && dis[j] == dis[x] + cost[i])
		{
			k = dfs(j, min((LL)w[i], rest));
			if(!k)
			{
				dis[j] = 0;
				continue;
			}
			rest -= k;
			w[i] -= k;
			w[i ^ 1] += k;
			ret += cost[i] * k;
		}
	}
	vis[x] = 0;
	return last - rest;
}
LL dinic()
{
	LL ans = 0, res = 0;
	while(bfs())
		while(res = dfs(S, Inf)) ans += res;
	return ans;
}
int k, l;
int a[N], b[N];
int main()
{
	scanf("%d", &m);
	while(m --)
	{
		ret = 0;
		idx = 1;
		memset(h, -1, sizeof(h));
		scanf("%d%d%d", &n, &k, &l);
		for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
		for(int i = 1;i <= n;i ++) scanf("%d", &b[i]);
		T = 2 * n + 4;
		addage(S, 2 * n + 1, k, 0);
		addage(2 * n + 2, 2 * n + 3, k - l, 0);
		for(int i = 1;i <= n;i ++)
		{
			addage(2 * n + 1, i, 1, -a[i]);
			addage(i, i + n, 1, 0);
			addage(i, n * 2 + 2, 1, 0);
			addage(2 * n + 3, i + n, 1, 0);
			addage(i + n, T, 1, -b[i]);
		}
		dinic();
		cout << -ret << endl;
	}
	return 0;
}

观察建图，不难发现有效流量都集中在左右两边，可以使用带悔贪心的思想找增广路。

可以发现每一条增广路的选择只可能有以下几种情况：

image

所以一共5种更新可能：

  • 选择$a_x+b_x$中最大的。

  • 选择$a_i + b_i$中最大的。

  • 选择$a$和$b$中最大的（$k > l$）。

  • 选择$a$中最大的和$b_x$中最大的。

  • 选择$a_x$中最大的和$b$中最大的。

其中$a_x$表示取了$b_x$但没有取$a_x$的$a_x$值（$b_x$同理）。

由上，维护4个堆即可。

  • 1：可取的$a$中的最大值。
  • 2：可取的$b$中的最大值。
  • 3：可取的$a_x$中的最大值。
  • 4：可取的$b_x$中的最大值。

每次更新答案即可：

  • $1 + 2$($k > l, k-(id_{a_{front}} != id_{b_{front}})$)
  • $2 + 3$($l > 0$)
  • $1 + 4$($l > 0$)
  • $3 + 4$($k ++$)

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define LL long long
#define PII pair<LL, int>
#define mp make_pair
#define x first
#define y second
using namespace std;
const int N = 1e6 + 5;
int T;
int n, k, l;
int a[N], b[N];
priority_queue<PII>q[5];
bool p[N], d[N];
LL ans;
void clear()
{
	ans = 0;
	for(int i = 0;i < 5;i ++) 
		while(!q[i].empty()) q[i].pop();
	for(int i = 0;i <= n;i ++)
		p[i] = d[i] = 0;
}
void check()
{
	while(!q[0].empty() && (p[q[0].top().y] || d[q[0].top().y])) q[0].pop();
	while(!q[1].empty() && p[q[1].top().y]) q[1].pop();
	while(!q[2].empty() && d[q[2].top().y]) q[2].pop();
	while(!q[3].empty() && (p[q[3].top().y] || !d[q[3].top().y])) q[3].pop();
	while(!q[4].empty() && (!p[q[4].top().y] || d[q[4].top().y])) q[4].pop();
}
void make_a(int x)
{
	if(d[x]) return ;
	q[4].push(mp(b[x], x));
}
void make_b(int x)
{
	if(p[x]) return ;
	q[3].push(mp(a[x], x));
}
int main()
{
	scanf("%d", &T);
	while(T --)
	{
		scanf("%d%d%d", &n, &k, &l);
		clear();
		for(int i = 1;i <= n;i ++) read(a[i]);
		for(int i = 1;i <= n;i ++) read(b[i]);
		for(int i = 1;i <= n;i ++)
		{
			q[0].push(mp(a[i] + b[i], i));
			q[1].push(mp(a[i], i));
			q[2].push(mp(b[i], i));
		}
		while(k --)
		{
			check();
			LL cnt = q[0].top().x, type = 0;
            LL o, u, e, m;
            if(!q[1].empty()) o = q[1].top().x;
			if(!q[2].empty()) u = q[2].top().x;
			if(!q[3].empty()) e = q[3].top().x;
			if(!q[4].empty()) m = q[4].top().x;
            if(!q[3].empty() && !q[4].empty() && e + m > cnt) cnt = e + m, type = 4;
			if(!q[1].empty() && !q[4].empty() && o + m > cnt) cnt = o + m, type = 2;
			if(!q[2].empty() && !q[3].empty() && u + e > cnt) cnt = u + e, type = 3;
            if(l <= k && !q[1].empty() && !q[2].empty() && o + u > cnt) cnt = o + u, type = 1;
			ans += cnt;
			if(type == 0) p[q[0].top().y] = d[q[0].top().y] = 1, l --;
			if(type == 1) p[q[1].top().y] = d[q[2].top().y] = 1, make_a(q[1].top().y), make_b(q[2].top().y);
			if(type == 2) p[q[1].top().y] = d[q[4].top().y] = 1, l --, make_a(q[1].top().y);
			if(type == 3) p[q[3].top().y] = d[q[2].top().y] = 1, l --, make_b(q[2].top().y);
			if(type == 4) p[q[3].top().y] = d[q[4].top().y] = 1, l -= 2;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

P6122 [NEERC2016]Mole Tunnels

费用流建图不难看出，$10^{5}$ 的数据范围是个人都不会写网络流。

再次分析费用流建图，将树的形态画出来的时候，手玩几组样例就可以发现，每个点可拓展的点十分的少（且已经给定），此时我们对于每一个新增只需跑一次树形dp即可，此时的时间复杂度已经降为$O(n^2)$了。

再次回顾我们树形dp干了啥，找离我们目前点的最近点，而我们的树是一颗完全二叉树，考虑动态维护子树中的有食物的点到根节点的最小距离，和这个点的编号，用flow数组表示我们选择从儿子流向父亲流了多少（从上往下，$flow>0$此边权值为-1，否则为1，反之同理）。所以每一次操作，我们顶多沿着链向上跳，一直跳到1号节点，就可以查询到离这个点最近的有食物的点，之后，对于修改我们顶多会修改两条链上的信息（其他链走都没走），所以时间复杂度降为鼹鼠数$\times$链长度，为$O(m \log n)$，可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') {if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARG>
inline void read(T &res, ARG &...com){read(res), read(com...);}
template <class T>
inline void write(T res)
{
    if(res >= 10) write(res / 10);
    putchar(res % 10 + '0');
}
const int N = 1e5 + 5, Inf = 0x3f3f3f3f;
int n, m;
int a[N], c[N], f[N], s[N], flow[N]; // flow: 从下面流上去时所加的反向边
inline void modify(int x)
{
    f[x] = Inf;
    if(a[x]) f[x] = 0, s[x] = x;
    if((x << 1) <= n && f[x << 1] + (flow[x << 1] < 0 ? -1 : 1) < f[x]) f[x] = f[x << 1] + (flow[x << 1] < 0 ? -1 : 1), s[x] = s[x << 1];
    if((x << 1 | 1) <= n && f[x << 1 | 1] + (flow[x << 1 | 1] < 0 ? -1 : 1) < f[x]) f[x] = f[x << 1 | 1] + (flow[x << 1 | 1] < 0 ? -1 : 1), s[x] = s[x << 1 | 1];
}
int ans;
int main()
{
    memset(f, 0x3f, sizeof(f));
    read(n), read(m);
    for(int i = 1;i <= n;i ++) read(a[i]);
    for(int i = n;i >= 1;i --) modify(i);
    int o, res, v, t, x, y;
    while(m --)
    {
        res = Inf, t = 0;
        read(o);
        x = o;
        while(o)
        {
            if(f[o] + t < res) res = f[o] + t, v = s[o], y = o;
            t += flow[o] > 0 ? -1 : 1;
            o >>= 1;
        }
        ans += res;
        write(ans), putchar(' ');
        while(x != y)
        {
            flow[x] --;
            x >>= 1;
            modify(x);
        }
        a[v] --;
        modify(v);
        while(v > y)
        {
            flow[v] ++;
            v >>= 1;
            modify(v);
        }
        while(v) modify(v), v >>= 1;
    }
    return 0;
}