经典的嵌套矩阵问题加路径输出 将矩阵间能否嵌套转化成一个DAG图上的最长路问题 对于最长路径的打印: 若只需要字典序最小很简单 对于打印所有,采用递归实现(有点类似全排列的实现)不知道正确性,有没有神犇说一下orz
Code:
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<cstdlib> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e3+10,M=1e6+10; int n; struct Matrix{ int x,y; Matrix(int x=0,int y=0):x(x),y(y){} }a[N]; int f[N],G[N][N]; int dp(int i){ if(f[i]) return f[i]; for(int j=1;j<=n;j++) if(G[i][j]) f[i]=max(f[i],dp(j)+1); return f[i]; } void print_ans(int id){ printf("%d ",id); for(int i=id;i<=n;i++) if(G[id][i]&&f[id]==f[i]+1){ print_ans(i); break; } } int r[N],ans; void print_ans2(int id,int len){ if(dp(id)==0){ if(len==ans+1) { fo(i,1,len) printf("%d ",r[i]); printf("\n"); } return ; } for(int i=id;i<=n;i++){ if(G[id][i]&&f[id]==f[i]+1){ r[len+1]=i; print_ans2(i,len+1); } } } int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); fo(i,1,n) scanf("%d%d",&a[i].x,&a[i].y); memset(G,0,sizeof(G)); fo(i,1,n) fo(j,1,n){ if(i==j) continue; if((a[i].x>a[j].x&&a[i].y>a[j].y)||(a[i].x>a[j].y&&a[i].y>a[j].x)) G[i][j]=1; } memset(f,0,sizeof(f)); ans=-1; int cur; fo(i,1,n) if(ans<dp(i)) ans=dp(i),cur=i; printf("%d\n",ans+1); print_ans(cur); printf("\n"); print_ans2(cur,1); } return 0; }