DAG

EG.01

来源

给你n种方块块，每种方块块的长、宽、高已知，且每种方块块有无数个。现在要把这些方块块垒成一座塔，要求每个方块块的底面长宽分别严格小于它下方的。

每种方块块有3种摆放方法。所以我们可以先将这些摆法全部拆解出来，然后开始以下处理：

对于两种摆法a,b：

若a可以放到b上面，则将a与b用一条有向边连接，其权值为a摆法的高度。

做完以上处理后，我们再设置一个点c，表示放这座塔的地面。

显然，每个方块块的任意一种摆法都可以放到地面，所以我们将每一种摆法与c连边，权值为该种摆法的高度。

接下来，只需要找到从一个节点到c的最长路径就行了。由于一个方块块的摆法不能重复使用（否则这样的塔一定不符合要求），所以这幅图中没有环。换句话说，这就是一个DAG。

设f[i]为从i出发的最长路长度，则：f[i] = max(f[j] + w[i][j])，其中i到j有边连接。

答案为所有f[i]中的最大值。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 105

struct node
{
	int x, y, z; //长,宽,高
} c[N];

int g[N][N], f[N], n;

int dp(int i) {
	if(f[i]) return f[i];
	f[i] = 0;
	for(int j = 1; j <= n; j++)
		if(g[i][j])
			f[i] = max(f[i], dp(j) + g[i][j]);
	return f[i];
}

int main() {
	int i, j;
	while(scanf("%d", &n) && n) {
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		n *= 3;
		for(i = 1; i <= n; i += 3) { //对于x,y,z的组合，分别以xy,yz,zx为底面
			scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].z);
			c[i + 1].x = c[i].y, c[i + 1].y = c[i].z, c[i + 1].z = c[i].x;
			c[i + 2].x = c[i].z, c[i + 1].y = c[i].x, c[i + 1].z = c[i].y;
		}
		for(i = 1; i <= n; i++) //定义长和宽中较长的一边为长，高不做要求，因为摆放时对高没有限制
			if(c[i].x > c[i].y)
				swap(c[i].x, c[i].y);
		for(i = 1; i <= n; i++)
			for(j = 1; j <= n; j++)
				if(c[i].x < c[j].x && c[i].y < c[j].y) //满足摆放条件
					g[i][j] = c[i].z; //i到j的高度
		n++;
		for(i = 1; i < n; i++)
			g[i][n] = c[i].z;
		int ans = 0;
		for(i = 1; i < n; i++)
			ans = max(ans, dp(i));
		printf("%d\n", ans);
	}
	return 0;
}

EG.02

Generating a random DAG

https://blog.csdn.net/qq_40147863/article/details/93376991

EG.03

HDU 1350

https://www.bilibili.com/video/BV1EA411q7cx