codeforces Gargari and Permutations(DAG+BFS)

1 /*
 2      题意：求出多个全排列的lcs！
 3      思路：因为是全排列，所以每一行的每一个数字都不会重复，所以如果有每一个全排列的数字 i 都在数字 j的前面，那么i， j建立一条有向边！
 4       最后用bfs遍历整个图，求出源点到每一个点的距离，其中最大的距离就是最长的公共子序列的长度！
 5 */
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<queue>
11 #include<vector>
12 #define N 1005
13 
14 using namespace std;
15 vector<int>g[N];
16 queue<int>q;
17 int pos[6][N];
18 int d[N];
19 int vis[N];
20 int n, k;
21 int ans;
22 
23 bool judge(int a, int b){//保证数字a 在数字 b的前边
24     for(int i=1;  i<=k; ++i)
25         if(pos[i][a] > pos[i][b])
26             return false;
27     return true;
28 }
29 
30 void bfs(int x){
31     q.push(x);
32     ans=0;
33     vis[0]=1;
34     while(!q.empty()){
35         int u=q.front();
36         q.pop();    
37         vis[u]=0;
38         ans=max(ans, d[u]);
39         int len=g[u].size();
40         for(int i=0; i<len; ++i){
41             int v=g[u][i];
42             if(d[v]<d[u]+1){
43                 d[v]=d[u]+1;
44                 if(!vis[v]){
45                     q.push(v);
46                     vis[v]=1;
47                 }
48             }
49         }
50     }
51 }
52 
53 int main(){
54     while(scanf("%d%d", &n, &k)!=EOF){
55         for(int i=1; i<=k; ++i)
56             for(int j=1; j<=n; ++j){
57                 int x;
58                 scanf("%d", &x);
59                 pos[i][x]=j;
60             }
61         for(int i=1; i<=n; ++i){
62             d[i]=0;//初始化所有点到源点的距离都为最小（因为是求最大距离，不是最短距离）
63             vis[i]=0;
64             g[0].push_back(i);
65             for(int j=i+1; j<=n; ++j)
66                 if(judge(i, j))
67                    g[i].push_back(j);
68                 else if(judge(j, i))
69                    g[j].push_back(i);
70         }
71         bfs(0);
72         printf("%d\n", ans);
73         for(int i=0; i<=n; ++i)//不要忘记将vector清空
74             g[i].clear();
75     }
76     return 0;
77 }