Backward Induction 相关总结

First Post:

Last Update:

Backward Induction ，译为逆向归纳法，常用于在有向图上做带环的 DP 与博弈，是一个很有用的技巧。

这种方法常用于，你要对每个点维护一个状态 ，而 由后继 推得的时候。

直接考虑环并不好做，我们先从简单的情况开始归纳，即 没有出边的情况，这一般很简单。

然后对反图做类似拓扑排序 / dijkstra 的 DP，让 一步一步更新 ，在队列/堆中存储已经确定的 。

有向图博弈

有向图博弈，有环，那么就肯定存在平局。

要让博弈进行下去，肯定是有一方希望平局，另一方不希望平局。

先 DP 出每个状态是否为平局，再导出每个点的胜负状态即可。

DP 平局较为容易，没有出边肯定不是平局，对于希望平局的一方，后继有平则平，对于不希望平局的一方，后继有不平则不平，记录每个点在原图上的出度 ，在原图上做拓扑排序式的 DP 即可。

怎么导出胜负状态呢？

我们一般会记录 ，表示 为起点， 先手，能到达多少个非平局后继。这样我们就可以在 DP 过程中判别， 的非平局后继是否都已经被确定。

如果 的非平局后继都已经被确定，将其加入队列 / 堆等数据结构，更新其它点即可。

第一道例题

洛谷 P6970

Alice : 先平再赢后输

Bob : 先赢再输后平

我们先 DP 出 表示以 为起点， 先手，是否为平局。

讲一下 DP 过程中的细节：

我们一开始将无出度节点的 置为 ，其余点的 均置为 。

维护一个队列 ，里面只会存放非平局的状态。

取出队头 ，取出 的前驱 。

如果 ，那么对应的， 那里是 Bob 先手，既然 Bob 不喜欢平局， 肯定为 ，更新并入队即可。

如果 ，那么对应的， 那里是 Alice 先手，那得 的所有后继均为非平局， 才是非平局，所以碰到 ，就把 ，什么时候减到 了，就更新并入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 1;i <= n;i++)
{
	deg[i] = out[i];
	if(!deg[i]) Q.emplace(i,0),Q.emplace(i,1);
	else drw[i][0] = drw[i][1] = 1;
}
while(!Q.empty())
{
	int x = Q.front().FI,tp = Q.front().SE; // 队列里只放非平局状态
	Q.pop();
	for(auto y : Gr[x])
        if((tp == 0 && drw[y][1]) || (tp == 1 && !--deg[y]))
	 		drw[y][tp ^ 1] = 0,Q.emplace(y,tp ^ 1);
}

然后对非平局状态 DP 出胜负即可，这个比较容易。

这题还有一个特殊情况，就是对于一些非平局状态，其在上一轮的 DP 中并没有确定胜负态。

对于 Bob 来说，这体现为该点在某个环上，后继有 Alice 的必胜与平局，在所有已经确定的状态都转移完之后，这些状态没有被转移到（因为在环上有相邻的点是非平局，导致无法进入这个环，因为相邻点的状态始终无法确定）。

那么这些点在环上，但为什么不是平局呢？

只有可能是 Bob 没法赢，但由不想平局，所以选择了输，特判这些点为 Alice 胜 Bob 败即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for(int i = 1;i <= n;i++)
	{
		deg[i] = out[i];
		if(!deg[i]) Q.emplace(i,0),Q.emplace(i,1);
		else F[i][0] = F[i][1] = -1;
		for(auto v : G[i])
			D[i][0] += !drw[v][1],D[i][1] += !drw[v][0];
	}
	while(!Q.empty())
	{
		int x = Q.front().FI,tp = Q.front().SE;Q.pop(); // 做出非平局状态的输赢
		for(auto y : Gr[x]) 
			if(!drw[y][tp ^ 1]) // 目标状态非平局
			{
				if(F[x][tp]) { if(!--D[y][tp ^ 1]) Q.emplace(y,tp ^ 1),F[y][tp ^ 1] = 0;}
				else {if(F[y][tp ^ 1] == -1) Q.emplace(y,tp ^ 1),F[y][tp ^ 1] = 1;}
			} 
	}
	for(int i = 1;i <= n;i++) // 特判上述情况
	{
		if(F[i][0] == -1) F[i][0] = 1;
		if(F[i][1] == -1) F[i][1] = 0;
	}

有向图 DP

与有向图博弈的流程大同小异，先考虑没有出度的点，再使用类似 Dijkstra 的方式维护转移即可。

第一道例题

AtCoder Beginning Contest 261 H

这道题是个博弈与 DP 结合的题，放在这里比较合适。

容易发现，Aoki 当然会尽量促成 "INFINITY"。

设 表示以 为起点，Takahashi/Aoki 先手的最终得分，初始时 。

对于没有出度的点，，将其加入堆。

有转移： 事实上，我们可以直接把平局的情况并入上述的转移。

如果有一个 有值，那么 就肯定有值。

如果所有的 有值，那么 才会有值。

上述的有值就是不为 的情况。

以上述规则转移即可。

在这里，我们维护可用状态用的是小根堆，这与 dijkstra 是本质相同的，我们只会从小的 DP 值转移到大的 DP 值，什么时候一个状态从堆中被弹出了，那它就已经确定了，因为比它小的 DP 值已经都被弹出，所有能更新它的转移都已经做完了。

如果还使用队列的话，那么这就与 SPFA 本质相同，你就无法在每个状态第一次出队时确定它，而是需要若干次松弛，直到状态收敛，这样就无法保证复杂度了。

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
#include <bits/stdc++.h>
#define FI first
#define SE second
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n,m,s;
vector<pair<int,int> > G[N],Gr[N];
ll f[N][2];
int out[N][2];
struct node{
	int x,tp;
	ll val;
	node(){}
	node(const int _x,const int _tp,const ll _val):
		x(_x),tp(_tp),val(_val){}
	bool operator < (const node &rhs) const { return val > rhs.val;}
};
priority_queue<node> Q;
int deg[N][2];
int vst[N][2];
inline void Dijk()
{
	while(!Q.empty())
	{
		int x = Q.top().x,tp = Q.top().tp;
		// if(Q.top().val != f[x][tp]) { Q.pop();continue;}
		Q.pop();
		if(vst[x][tp]) continue;
		vst[x][tp] = true;
		for(auto it : Gr[x])
		{
			int y = it.FI,w = it.SE;
			if(tp == 0) f[y][1] = max(f[y][1],f[x][0] + w);
			if(tp == 1) f[y][0] = min(f[y][0],f[x][1] + w);
			deg[y][tp ^ 1]--;
			if(!deg[y][tp ^ 1]) Q.push(node(y,tp ^ 1,f[y][tp ^ 1]));
			else if(tp == 1) Q.push(node(y,0,f[y][0])); // 对于先手而言，只要一个转移边有值就可以更新
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	for(int i = 1;i <= m;i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		Gr[b].emplace_back(a,c);
		++deg[a][0];++deg[a][1];
	}
	for(int i = 1;i <= n;i++)
		f[i][0] = 9e18;
	for(int i = 1;i <= n;i++)
		if(!deg[i][0])
		{
			Q.push(node(i,0,f[i][0] = 0));
			Q.push(node(i,1,f[i][1] = 0));
		}
	Dijk();
	if(!vst[s][0]) puts("INFINITY");
	else cout << f[s][0] << endl;
	return 0;
}

当然，也是可以先按照上文的方法 DP 出每个状态是否平局，然后用优先队列转移非平局状态。

第二道例题

洛谷 P4042

这题，令 表示消灭 号怪兽的最小代价，那么有 因为这题每个状态都最终会有个确定的值，并不需要像上一题一样加入特殊的转移规则，转移比较普通。

也是因此，我们可以等到每个点的后继均被确定，再将其入队，事实上，这样每个点只会被入队一次。

因为不确定要让哪些点的 DP 值取到 ，我们一开始将所有 入队即可。

每个点算上最开始的一次入堆，最多被入堆两次，时间复杂度为 。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,M = 1e6 + 5;
typedef long long ll;
int n,R[N];
ll S[N],K[N];
vector<int> G[N];
ll dp[N];
struct node{
	int id;ll val;
	node(){}
	node(const int _id,const ll _val):id(_id),val(_val){}
	bool operator < (const node &rhs) const { return val > rhs.val;}
};
priority_queue<node> Q;
int vst[N];
ll ans[N];
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> S[i] >> K[i];
		int k;
		cin >> k;R[i] = k;
		for(int j = 1,x;j <= k;j++)
			cin >> x,G[x].push_back(i);
	}
	for(int i = 1;i <= n;i++)
	{
		dp[i] = S[i]; // 维护 S[i] + \sum dp_j
		Q.push(node(i,K[i]));
	}
	while(!Q.empty())
	{
		int x = Q.top().id;
		ll val = Q.top().val;
		Q.pop();
		if(vst[x]) continue;
		vst[x] = true;ans[x] = val;
		for(auto y : G[x])
		{
			if(vst[y] || dp[y] > K[y]) continue;
			R[y]--;dp[y] += val;
			if(!R[y]) Q.push(node(y,dp[y]));
		}
	}
	cout << ans[1] << endl;
	return 0;
}

这种在有向图上的 DP 有一个共性：由小的 DP 值转移到大的 DP 值，所以用小根堆维护当前可用的状态即可。

这与 dijkstra 的正确性是本质相同的，事实上，最短路问题也可以看作在有环图上的最优化 DP。

第三道例题

[CCO2021] Travelling Merchant

设 表示从 出发，至少需要多少资产可以一直走下去，可以写一个转移： 。

还是考虑没有出度的点，显然 为 ，答案为 。

如果不断删去出度为 的点，最后剩下的点一定是有答案的（即在环上的点）

读者从前面的题可以发现，对于这种有环的 DP,我们可以考察答案的界，来看看答案会收敛成什么样子。

我们考虑这些点的答案上界。

显然，取出当前最大的 ，那么如果你初始有 的资产，那就可以通行全图，因为资产不会减少。

取出这条边的起点 ，并将 对 取 ，再删掉这条边。

如果删完之后这条边已经没有出边了，说明 已经确定，可以拿来更新其它的点，将其放入一个队列。

跑类似上文的 DP 即可，一边松弛答案，一边观察目标点的后继是否全被删空，要注意，给每条边打个标记，使得每条边只被删一次。

在寻常的 Backward DP 中，打标记并不是必要的，一来每个状态入队不一定只有一次（比如上一道题），二来不打标记也只会对常数造成影响。

但是这道题中，我们要一边找当前 最大的边，一边去做 Backward DP 来更新 数组，为了让这两个过程不重复统计，我们对每条边打了个删除标记。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n,m;
struct Edge{
	int a,b,r,p;
	Edge(){}
	Edge(const int _a,const int _b,const int _r,const int _p):
		a(_a),b(_b),r(_r),p(_p){}
	bool operator < (const Edge &rhs) const { return r > rhs.r;}
};
Edge p[N];
vector<int> G[N];
queue<int> Q;
bool vst[N];
int out[N];
int ans[N];
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
		cin >> p[i].a >> p[i].b >> p[i].r >> p[i].p;
	sort(p + 1,p + m + 1);
	for(int i = 1;i <= m;i++)
		G[p[i].b].push_back(i);
	for(int i = 1;i <= m;i++)
		++out[p[i].a];
	for(int i = 1;i <= n;i++)
		ans[i] = 2e9;
	for(int i = 1;i <= n;i++)
		if(!out[i]) Q.push(i);
	for(int i = 1;i <= m;i++)
	{
		while(!Q.empty())
		{
			int x = Q.front();Q.pop();
			for(auto id : G[x])
			{
				if(vst[id]) continue;
				int y = p[id].a;
				vst[id] = true;
				--out[y];
				if(ans[x] < 2e9) ans[y] = min(ans[y],max(p[id].r,ans[x] - p[id].p));
				if(!out[y])	
					Q.push(y);
				
			}
		}
		if(vst[i]) continue;
		ans[p[i].a] = min(ans[p[i].a],p[i].r);
		vst[i] = true;
		--out[p[i].a];
		if(!out[p[i].a]) Q.push(p[i].a);
	}
	for(int i = 1;i <= n;i++)
		if(ans[i] >= 2e9) printf("-1 ");
		else printf("%d ",ans[i]);
	printf("\n");
	return 0;
}
≡