DAG镶嵌模型+原始路径打印

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define doumax(a,b) (a>b?a:b)
 4 const int maxn=100;
 5 int mat[maxn][maxn],dp[maxn],n;
 6 struct node{
 7     int a;
 8     int b;
 9     void dousort(void)
10     {
11         if(a<b){
12             int temp=a;
13             a=b;
14             b=temp;
15         }
16     }
17     bool operator<(const node & t)
18     {
19         return t.a>a && t.b>b;
20     }
21     void operator=(const node & t)
22     {
23         a=t.a;b=t.b;
24     }
25 }rect[maxn],rectinit[maxn];
26 int dpmodel(int i);
27 void print_road(int i);
28 int main()
29 {
30     while(scanf("%d",&n)==1){
31         for(int i=1;i<=n;i++){
32             scanf("%d%d",&rect[i].a,&rect[i].b);
33             rectinit[i]=rect[i];
34             rect[i].dousort();
35         }
36         memset(mat,0,sizeof(mat));
37         memset(dp,0,sizeof(dp));
38         for(int i=1;i<=n;i++)
39             for(int j=i+1;j<=n;j++){
40                 if(rect[i]<rect[j])
41                     mat[i][j]=1;
42                 else if(rect[j]<rect[i])
43                     mat[j][i]=1;
44             }
45         int maxroad=0,maxi;
46         for(int i=1;i<=n;i++){
47             if(maxroad<dpmodel(i)){
48                  maxroad=dpmodel(i);
49                  maxi=i;
50             }
51         }
52         printf("%d\n",maxroad);
53         print_road(maxi);
54     }
55     return 0;
56 }
57 int dpmodel(int i)
58 {
59     if(dp[i]>0)
60         return dp[i];
61     dp[i]=1;
62     for(int j=1;j<=n;j++)
63         if(mat[i][j])
64         dp[i]=doumax(dp[i],dpmodel(j)+1);
65     return dp[i];
66 }
67 void print_road(int i)
68 {
69     printf("(%d,%d)\n",rectinit[i].a,rectinit[i].b);
70     if(dp[i]==1)
71         return;
72     for(int j=1;j<=n;j++)
73     if(mat[i][j] && dp[i]==dp[j]+1){
74         print_road(j);
75         return;
76     }
77 }