598
技術社區[雲棲]
uva 103 - Stacking Boxes DAG最長路
圖很小，所以隨便亂搞就可以了，記憶化搜索
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
int n,k;
int node[31][11],d[31];
bool map[31][31];
bool ok(int a,int b) //can a in b
{
for(int i=0;i<k;i++)
if(node[a][i]>=node[b][i])return 0;
return 1;
}
int dp(int i)
{
int &ans=d[i];
if(ans>0)return ans;
ans=1;
for(int j=0;j<n;j++)
if(map[i][j])ans=max(ans,dp(j)+1);
return ans;
}
void print(int i)
{
printf("%d",i+1);
for(int j=0;j<n;j++)
if(map[i][j]&&d[i]==d[j]+1)
{
putchar(' ');
print(j);
break;
}
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
scanf("%d",&node[i][j]);
sort(node[i],node[i]+k);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
map[i][j]=ok(i,j);
memset(d,0,sizeof(d));
int Max=0,t;
for(i=0;i<n;i++)
if((t=dp(i))>Max)
Max=t,j=i;
dp(j);
printf("%d\n",Max);
print(j);
puts("");
}
}
最後更新：2017-04-03 16:48:43