uva 103 Stacking Boxes（DAG）

题目连接：103 - Stacking Boxes

题目大意：有n个w维立体， 输出立体互相嵌套的层数的最大值， 并输出嵌套方式， 可嵌套的要求是外层立体的w条边可以分别对应大于内层立体。

解题思路：可以将每个立体的w边安照从小到大排序， 比较的时候逐一比较就可以判断出可否嵌套， 然后就是纯DAG问题了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 50;

int n, w, dp[N], vis[N], seq[N][N];

void Init() {
    memset(dp, 0, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    memset(seq, 0, sizeof(seq));
}

void read() {
    for (int i = 0; i < n; i++) {
	for (int j = 0; j < w; j++)
	    scanf("%d", &seq[i][j]);
	sort(seq[i], seq[i] + w);
    }
}

bool judge(int a, int b) {
    for (int i = 0; i < w; i++)
	if(seq[a][i] <= seq[b][i])  return false;
    return true;
}

int find(int d) {
    if (dp[d])	return dp[d];

    for (int i = 0; i < n; i++) {
	if (judge(i, d)) {
	    int a = find(i);
	    if (a > dp[d]) {
		dp[d] = a;
		vis[d] = i;
	    }
	}
    }
    return ++ dp[d];
}

void solve() {
    int Max = 0, id, a;
    for (int i = 0; i < n; i++) {
	a = find(i);
	if (a > Max) {
	    Max = a;
	    id = i;
	}
    }
    printf("%d
", Max);
    for (int i = 1; i < Max; i++) {
	printf("%d ", id + 1);
	id = vis[id];
    }
    printf("%d
", id + 1);
}


int main() {
    while (scanf("%d%d", &n, &w) == 2) {
	Init();
	read();
	solve();
    }
    return 0;
}