通化网站建设,wordpress query vars,.net 网站开发视频教程,厦门人才网唯一官网1 /*2 题意#xff1a;求出多个全排列的lcs#xff01;3 思路#xff1a;因为是全排列#xff0c;所以每一行的每一个数字都不会重复#xff0c;所以如果有每一个全排列的数字 i 都在数字 j的前面#xff0c;那么i#xff0c; j建立一条有向边#xff01;4 … 1 /*2 题意求出多个全排列的lcs3 思路因为是全排列所以每一行的每一个数字都不会重复所以如果有每一个全排列的数字 i 都在数字 j的前面那么i j建立一条有向边4 最后用bfs遍历整个图求出源点到每一个点的距离其中最大的距离就是最长的公共子序列的长度5 */6 #includeiostream7 #includecstdio8 #includecstring9 #includealgorithm
10 #includequeue
11 #includevector
12 #define N 1005
13
14 using namespace std;
15 vectorintg[N];
16 queueintq;
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 i1; ik; 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 ans0;
33 vis[0]1;
34 while(!q.empty()){
35 int uq.front();
36 q.pop();
37 vis[u]0;
38 ansmax(ans, d[u]);
39 int leng[u].size();
40 for(int i0; ilen; i){
41 int vg[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 i1; ik; i)
56 for(int j1; jn; j){
57 int x;
58 scanf(%d, x);
59 pos[i][x]j;
60 }
61 for(int i1; in; i){
62 d[i]0;//初始化所有点到源点的距离都为最小因为是求最大距离不是最短距离
63 vis[i]0;
64 g[0].push_back(i);
65 for(int ji1; jn; 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 i0; in; i)//不要忘记将vector清空
74 g[i].clear();
75 }
76 return 0;
77 } 转载于:https://www.cnblogs.com/hujunzheng/p/3947392.html
