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 }









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3947392.html,如需转载请自行联系原作者
目录
相关文章
|
7月前
Leetcode 368. Largest Divisible Subset思路及详解
这里有个很简单的数学性质,就是整除的传递性,如果a%b==0 且 b%c == 0,那么a%c == 0,说白了如果c是b的因子,b又是a的因子,那么c肯定是a的因子。这样我们就可以在数组中找出很多整除链(a->b->c->d,其中b是a的因子,c是b的因子,d是c的因子),这样的链条就满足两两整除的条件,题目就变成了求最长的链条。 先上代码,然后我再解释下我的代码。
27 0
|
8月前
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
|
10月前
UVa872 - Ordering(拓扑排序)
UVa872 - Ordering(拓扑排序)
50 0
|
8月前
|
人工智能
poj 2299 Ultra-QuickSort 求逆序数 树状数组解法
所谓离散化,我们的了解就是对原数组排序,然后用所在位置的下标代替原数,这样我们就可以把数据范围缩小到1-500000,这个数组是开的下的。
25 0
|
8月前
|
开发框架 .NET
poj 3468 A Simple Problem with Integers线段树区间修改
题目意思很简单,有N个数,Q个操作, Q l r 表示查询从l到r 的和,C l r v 表示将从l到r 的值加上v,明显的线段树,不知道线段树的人肯定暴力,肯定超时,哈哈!!
22 0
|
9月前
|
算法
The kth great number(小根堆思想,模板题)
The kth great number(小根堆思想,模板题)
29 0
The kth great number(小根堆思想,模板题)
|
10月前
|
人工智能
POJ 2299 Ultra-QuickSort(树状数组+离散化+求逆序数)
POJ 2299 Ultra-QuickSort(树状数组+离散化+求逆序数)
codeforces1253——D. Harmonious Graph(并查集)
codeforces1253——D. Harmonious Graph(并查集)
74 0
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
123 0
AtCoder Beginner Contest 223 D - Restricted Permutation(建图 思维 构造 拓扑排序)
AtCoder Beginner Contest 223 D - Restricted Permutation(建图 思维 构造 拓扑排序)
94 0