UVa 103 : Stacking Boxes

問題リンク：Stacking Boxes

問題概要：
n個のk次元の箱がある
以下の条件を満たす時、箱aを箱bに入れることができる
・箱aの各辺の長さが箱bの対応する辺の長さ未満であるような順列が存在する
（例: 5次元とする
箱 a : 5 1 3 7 6
箱 b : 4 2 7 8 6

分かりにくいのでソートすると、
箱 a : 1 3 5 6 7
箱 b : 2 4 6 7 8
この時、箱aの各辺は全て箱bの対応する辺未満なので箱bに箱aを入れることができる

箱 a : 1 2 3 4 5
箱 b : 1 1 2 3 4
この時は、箱aの辺をどのように入れ替えても箱bの対応する各辺未満にできないので箱bに箱aを入れることはできない
逆に箱aに箱bは入れる亊ができる

）
最大何個の箱を入れる亊ができるか？
その時の箱の入れ方も順番通りに出力せよ（複数ある場合はどれでも良い）

解法：
トポロジカルソートしてDP
入力をとった後に、箱の各辺の長さは全て小さい順でソートしておく
あとは二重ループである箱の中に入れる亊ができる箱全てに対してコスト１の辺をはる
そうしてできたグラフをトポロジカルソートし、あとはDPで最大の数を数える
経路も記録しておき、最後に復元する

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<26)
#define MAX 400
using namespace std;

struct P
{
  int to,cost;
  P(int to=inf,int cost=inf):to(to),cost(cost){}
};

//トポロジカルソート

int n,k;
int dp[MAX],maxpath[MAX];

bool check(vector<int> &a,vector<int> &b)
{
  rep(i,k)
    if(a[i] >= b[i])return false;
  return true;
}

int main()
{
  while(scanf("%d %d",&n,&k) != EOF)
    {

      vector<vector<P> > G(n);
      vector<int> vec[n];
      rep(i,n)
	{
	  vec[i].resize(k);
	  rep(j,k)scanf("%d",&vec[i][j]);
	  sort(vec[i].begin(),vec[i].end());
	}

      rep(from,n)
	{
	  rep(to,n)
	    {
	      if(check(vec[from],vec[to]))
		{
		  G[from].push_back(P(to,1));
		}
	    }
	}

      vector<int> order;
      topologicalSort(G,order);

      rep(i,n)dp[i] = 1,maxpath[i] = inf;

      int maxcost = 1;
      int maxpos = order[0];


      rep(i,n)
	{
	  int cur = order[i];
	  rep(j,G[cur].size())
	    {
	      int next = G[cur][j].to;
	      if(dp[next] < dp[cur]+1)
		{
		  dp[next] = dp[cur] + 1;
		  maxpath[next] = cur;
		  if(maxcost < dp[next])
		    {
		      maxcost = dp[next];
		      maxpos = next;
		    }
		}
	    }
	}
      
      cout << maxcost << endl;
      vector<int> path;
      for(;;)
	{
	  path.push_back(maxpos);
	  maxpos = maxpath[maxpos];
	  if(maxpos == inf)break;
	}
      reverse(path.begin(),path.end());
      rep(i,path.size())
	{
	  cout << path[i]+1;
	  if(i != path.size()-1)cout << " ";
	  else                  cout << endl;
	}      

    }
  return 0;
}