3月8日 概念专题
A - 边覆盖
Problem Description
对一个给定的无向图G(V,E)，边集E'是E的子集。如果V中的所有顶点都在E'中出现过，那么称边集E'是图G的一个边覆盖（Edge Cover）。
（以上定义引自https://en.wikipedia.org/wiki/Edge_cover）
根据上面的定义，请判断一些给定的边集是否是给定的无向图的边覆盖。
Input
每个输入文件一组数据。
第一行为两个整数N、M（1<=N<=500, 1<=M<=N*(N-1)/2），分别表示无向图的顶点数和边数。假设图上的顶点编号为从1到N。
接下来M行，每行两个正整数u、v（1<=u,v<=N, u!=v），分别表示一条无向边的两个端点。数据保证没有重边。
接着一个正整数K（K<=10），表示查询的个数。
然后是K个查询，每个查询第一行为一个正整数L（L<=M），表示欲查询边集E'中的边数；接下来L行，每行两个整数，表示边集E'中的一条边。数据保证E'一定是E的子集。
Output
每个查询一行，如果欲查询边集E'不是图G的边覆盖，那么输出No；否则输出Yes。
Sample Input
6 7
1 2
1 3
2 3
2 4
3 5
4 5
4 6
3
3
1 2
3 5
4 6
4
1 2
2 3
4 5
4 6
3
1 2
2 3
4 6
Sample Output
Yes
Yes
No
分析：先判断E‘是否是E'的子集，再判断E'有没有覆盖全部顶点
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<unordered_map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<limits>
using namespace std;
const int nmax = 510;
struct node{
int u, v;
};
unordered_map<int, bool>mp;
bool vis[nmax] = {false};
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n, m, K, L;
cin>>n>>m;
for(int i = 0; i < m; ++i){
int u, v;
cin>>u>>v;
mp[u * nmax + v] = mp[v * nmax + u] = true;
}
cin>>K;
for(int i = 0; i < K; ++i){
fill(vis, vis + nmax, false);
bool flag = true;
cin>>L;
for(int j = 0; j < L; ++j){
int u, v;
cin>>u>>v;
vis[u] = vis[v] = true;
if(mp[u * nmax + v] == false)flag = false;
}
if(flag == true){
for(int j = 1; j <= n; ++j){
if(vis[j] == false){
flag = false;
break;
}
}
}
printf("%s
", flag == true ? "Yes" : "No");
}
return 0;
}
B - 极大独立集
Problem Description
对一个给定的无向图G(V,E)，点集V'是V的子集。如果V'中的任意两个顶点之间都没有边，就称点集V'是图G的独立集（Independent Set）。在此基础上，如果往V'中添加任何一个在V中但不在V'中的顶点，都会使V'变成非独立集，那么就称V'是图G的极大独立集（Maximal Independent Set）。
（以上定义引自https://en.wikipedia.org/wiki/Independentset(graph_theory)）
根据上面的定义，请判断一些给定的点集是否是给定的无向图的极大独立集。
Input
每个输入文件一组数据。
第一行为两个整数N、M（1<=N<=500, 1<=M<=N*(N-1)/2），分别表示无向图的顶点数和边数。假设图上的顶点编号为从1到N。
接下来M行，每行两个正整数u、v（1<=u,v<=N, u!=v），分别表示一条无向边的两个端点。数据保证没有重边。
接着一个正整数K（K<=10），表示查询的个数。
然后是K个查询，每个查询第一行为一个正整数L（L<=N），表示欲查询点集V'的顶点个数；第二行为用空格隔开的L个正整数，表示V'中的顶点编号。数据保证V'一定是V的子集。
Output
每个查询一行，如果欲查询的点集不是图G的独立集，那么输出Not an Independent Set；如果欲查询的点集是图G的独立集但不是极大独立集，那么输出Not Maximal；如果欲查询的点集是图G的极大独立集，输出Yes。
Sample Input
6 5
1 2
2 3
2 4
4 5
4 6
3
2
1 4
3
1 3 4
3
1 2 4
Sample Output
Not Maximal
Yes
Not an Independent Set
分析：先判断集合V'是不是独立集，然后枚举V-V’中的顶点，判断是不是最大独立集，注意枚举时根据是否将V‘中的点全部枚举作为判断是不是最大独立集的条件
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<unordered_map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<limits>
using namespace std;
const int nmax = 510;
unordered_map<int, bool>mp;
bool vis[nmax] = {false};
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n, m, K, L;
cin>>n>>m;
for(int i = 0; i < m; ++i){
int u, v;
cin>>u>>v;
mp[u * nmax + v] = mp[v * nmax + u] = true;
}
cin>>K;
for(int i = 0; i < K; ++i){
fill(vis, vis + nmax, false);
cin>>L;
vector<int>v(L);
for(int j = 0; j < L; ++j){
cin>>v[j];
vis[v[j]] = true;
}
bool flag1 = true;
for(int j = 0; j < L; ++j){
for(int k = j + 1; k < L; ++k){
if(mp[v[j] * nmax + v[k]] == true){
flag1 = false;
break;
}
}
if(flag1 == false)break;
}
if(flag1 == false){
printf("Not an Independent Set
");
}else{
bool flag2 = true;
for(int j = 1; j <= n; ++j){
if(vis[j] == false){
int k;
for(k = 0; k < L; ++k){
if(mp[j * nmax + v[k]] == true)break;
}
//注意根据k的终值判断
if(k == L){
flag2 = false;
break;
}
}
}
printf("%s
", flag2 == true ? "Yes" : "Not Maximal");
}
}
return 0;
}
C - 稳定婚姻问题
Problem Description
有两个点集V1和V2，点集中的顶点个数均为N。现在对V1和V2中的点建立一对一映射关系，也就是说，V1中的每个点对且只对V2中的一个点建立连接关系，V2中的每个点也对且只对V1中的一个点建立连接关系。这样这两个点集间就有N个连接。
已知点集V1中的每个点都对V2中的所有点有一个优先顺序，点集V2中的每个点也对V1中的所有点有一个优先顺序。例如V1中有两个点a1、a2，V2中有两个点b1、b2，那么a1会希望V2中与它连接的点的优先顺序是比如b2 > b1，a2会希望V2中与它相连接的点的优先顺序是比如b1 > b2，b1会希望V1中与它连接的点的优先顺序是比如a1 > a2，b2会希望V1中与它相连接的点的优先顺序是比如a1 > a2。
对给定的一对一映射关系来说，如果存在V1和V2中没有连接关系的一对点(ai, bj)，满足（1）对ai来说，bj的优先顺序高于ai当前的连接对象（2）对bj来说，ai的优先顺序也高于bj当前的连接对象，那么我们称这组映射关系是不稳定的；而如果V1和V2中没有连接关系的任意点对(ai, bj)都不满足上面的条件，则称这组映射关系是稳定的。
（以上定义总结自https://en.wikipedia.org/wiki/Stable_marriage_problem）
现在给出所有点希望对方点集的点的优先顺序，判断一些映射关系是否是稳定的。
Input
每个输入文件一组数据。
第一行为一个正整数N（N <= 500），表示每个点集中都有N个点。假设每个点集中的点的编号都是从1到N。
接下来N行，每行N个整数，表示点集V1中的点希望V2中与它连接的点的优先顺序。其中第2行为编号为1的点希望V2中与它连接的点的优先顺序，第3行为编号为2的点希望V2中与它连接的点的优先顺序……第N+1行为编号为N的点希望V2中与它连接的点的优先顺序。每行均按优先级从高到低的顺序给出V2中的点的编号。
再接下来N行，每行N个整数，表示点集V2中的点希望V1中与它连接的点的优先顺序。其中第N+2行为编号为1的点希望V1中与它连接的点的优先顺序，第N+3行为编号为2的点希望V1中与它连接的点的优先顺序……第2N+1行为编号为N的点希望V1中与它连接的点的优先顺序。每行均按优先级从高到低的顺序给出V1中的点的编号。
然后是一个一个正整数K（K<=10），表示查询个数。
每个查询为一组映射关系，共N行，每行两个整数i和j，表示V1中编号为i的点与V2中编号为j的点互为连接对象。数据保证给出的映射关系一定是一对一的。
Output
每行输出一个查询的结果，如果当前查询的映射关系是稳定的，那么输出Stable，否则输出Not Stable。
Sample Input
2
2 1
1 2
1 2
1 2
2
1 1
2 2
1 2
2 1
Sample Output
Not Stable
Stable
分析：
1. 题目中需要用到每个点的couple，因此用两个map分别存储，而不选用邻接矩阵
2. 需要查询选择优先级，因此将节点编号作为优先级数组下标，实现对优先级的直接存取
3. 注意题目中的稳定与不稳定是针对每一组映射而言，因此需要枚举点对判断
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<unordered_map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<limits>
using namespace std;
const int nmax = 510;
int p1[nmax][nmax], p2[nmax][nmax];
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
int N, K, temp;
cin>>N;
for(int i = 1; i <= N; ++i){
for(int j = 1; j <= N; ++j){
cin>>temp;
p1[i][temp] = j;
}
}
for(int i = 1; i <= N; ++i){
for(int j = 1; j <= N; ++j){
cin>>temp;
p2[i][temp] = j;
}
}
cin>>K;
for(int i = 0; i < K; ++i){
unordered_map<int, int>mp1, mp2;
for(int j = 0; j < N; ++j){
int u, v;
cin>>u>>v;
mp1[u] = v;
mp2[v] = u;
}
bool flag = true;
for(int j = 1; j <= N; ++j){
for(int k = 1; k <= N; ++k){
if(mp1[j] != k && mp2[k] != j){
int cp1 = mp1[j], cp2 = mp2[k];
bool flag1 = p1[j][k] < p1[j][cp1];
bool flag2 = p2[k][j] < p2[k][cp2];
if((flag1 & flag2) == true){
flag = false;
break;
}
}
}
}
printf("%s
", flag == true ? "Stable" : "Not Stable");
}
return 0;
}
D - 笛卡尔树
Problem Description
对一棵二叉树来说，如果树上的每个结点有两个值K、V，满足
（1）以K为视角时这棵二叉树满足二叉查找树的性质，即对每个结点，左子树所有结点的K值小于该结点的K值小于右子树所有结点的K值；
（2）以V为视角时这棵二叉树满足堆的性质，即每个结点的V值都大于子树所有结点的V值（或都小于子树所有结点的V值）。
那么就称这棵二叉树是笛卡尔树。
（以上定义引自https://en.wikipedia.org/wiki/Cartesian_tree）
现在给定一棵二叉树，请判断其是否是笛卡尔树。
注意，笛卡尔树只是满足堆的性质，不代表一定是完全二叉树。
Input
每个输入文件一组数据。
第一行为一个正整数N（2<=N<=1024），表示二叉树上的结点数目。假设结点编号为从1到N。
第二行为N个正整数，表示1到N号结点的K值。数据保证每个值唯一，且不超过10000。
第三行为N个正整数，表示1到N号结点的V值。数据保证每个值唯一，且不超过10000。
接下来N行，按编号从1号到N号的顺序给出每个结点的子结点信息。每行两个整数，分别表示当前结点的左结点编号和右结点编号。如果左结点或右结点为空，则记为-1。
Output
如果该二叉树是笛卡尔树，那么输出第一行YES，然后在第二行输出MIN HEAP或者MAX HEAP，分别表示该笛卡尔树的V值满足小顶堆或大顶堆的性质。
如果该二叉树不是笛卡尔树，那么输出第一行NO，然后在第二行输出错误信息，即如果K值不满足二叉查找树的性质，那么输出NOT BST；如果V值不满足堆的性质，那么输出NOT HEAP；如果K值和V值都不满足，那么输出NOT BST AND NOT HEAP。
Sample Input 1
5
6 3 8 1 4
2 5 3 9 8
2 3
4 5
-1 -1
-1 -1
-1 -1
Sample Output 1
YES
MIN HEAP
Sample Input 2
5
6 7 8 1 4
2 5 3 9 8
2 3
4 5
-1 -1
-1 -1
-1 -1
Sample Output 2
NO
NOT BST
Sample Input 3
5
6 3 8 1 4
6 5 3 9 8
2 3
4 5
-1 -1
-1 -1
-1 -1
Sample Output 3
NO
NOT HEAP
Sample Input 4
5
6 7 8 1 4
6 5 3 9 8
2 3
4 5
-1 -1
-1 -1
-1 -1
Sample Output 4
NO
NOT BST AND NOT HEAP
分析：树的递归操作
更正：判断是否为bst时不能根据子树都是bst并且子树根节点和原树根节点满足大小关系判断，因为bst的根节点不是该树中值最大的节点
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<unordered_map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<limits>
using namespace std;
const int nmax = 1100;
struct node{
int lchild, rchild;
};
node tree[nmax];
int kval[nmax], vval[nmax];
bool vis[nmax] = {false};
//bst
vector<int>inpath;
void inOrder(int root){
if(root == -1)return;
inOrder(tree[root].lchild);
inpath.push_back(kval[root]);
inOrder(tree[root].rchild);
}
bool isbst(int root){
if(root == -1)return true;
inOrder(root);
bool flag = true;
for(int i = 1; i < inpath.size(); ++i){
if(inpath[i] <= inpath[i - 1]){
flag = false;
break;
}
}
return flag;
}
//bool isbst(int root){
// if(root == -1)return true;
// int l = tree[root].lchild, r = tree[root].rchild;
// if(l == -1 && r == -1)return true;
// if(l != -1 && r == -1 && kval[l] < kval[root])return true;
// if(l == -1 && r != -1 && kval[root] < kval[r])return true;
// if(kval[l] >= kval[root] || kval[root] >= kval[r])return false;
// return isbst(l) && isbst(r);
//
//}
bool isminheap(int root){
if(root == -1)return true;
int l = tree[root].lchild, r = tree[root].rchild;
if(l == -1 && r == -1)return true;
if(l != -1 && vval[root] >= vval[l])return false;
if(r != -1 && vval[root] >= vval[r])return false;
return isminheap(l) && isminheap(r);
}
bool ismaxheap(int root){
if(root == -1)return true;
int l = tree[root].lchild, r = tree[root].rchild;
if(l == -1 && r == -1)return true;
if(l != -1 && vval[root] <= vval[l])return false;
if(r != -1 && vval[root] <= vval[r])return false;
return ismaxheap(l) && ismaxheap(r);
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n;
cin>>n;
for(int i = 1; i <= n; ++i)cin>>kval[i];
for(int i = 1; i <= n; ++i)cin>>vval[i];
for(int i = 1; i <= n; ++i){
int u, v;
cin>>u>>v;
tree[i].lchild = u;
tree[i].rchild = v;
if(u != -1)vis[u] = true;
if(v != -1)vis[v] = true;
}
int root = 1;
for(int i = 1; i <= n; ++i){
if(vis[i] == false){
root = i;
break;
}
}
bool flag1 = isbst(root);
bool flag2 = ismaxheap(root);
bool flag3 = isminheap(root);
if(flag1 & (flag2 | flag3)){
printf("YES
");
if(flag2)printf("MAX HEAP
");
else printf("MIN HEAP
");
}else{
printf("NO
");
if((flag2 | flag3) == true)printf("NOT BST
");
else if(flag1 == true)printf("NOT HEAP
");
else printf("NOT BST AND NOT HEAP
");
}
return 0;
}