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 }
?
