目录

  1. 第一题
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析
  2. 第二题
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析
    5. 补充知识点
      1. 二分图
      2. 匹配
      3. 匈牙利算法（Hungarian Algorithm）
      4. Konig定理

第一题

题目描述

合唱队的N名学生站成一排，且从左到右编号为1到N，其中编号为i的学生身高为Hi。现在将这些学生分成若干组（同一组的学生编号连续），并让每组学生从左到右按身高从低到高进行排列，使得最后所有学生同样满足从左到右身高从低到高（中间位置可以等高），那么最多能将这些学生分成多少组？

输入描述

第一行包含一个整数N，1<=N<=105。
第二行包含N个空格隔开的整数H1到HN，1<=Hi<=109。

输出描述

输出能分组的最多组数

分析

  • 思路：先整体排序，然后再用滑动窗口对遍历排好序的序列和原始序列，对二者窗口内的集合进行比较，若两集合数据一样，则计数加1；否则窗口继续扩大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int getMaxTeams(const vector<int>& H) {
    vector<int> sortedH;
    sortedH.assign(H.begin(), H.end());
    sort(sortedH.begin(), sortedH.end());
    
    int cnt = 0;
    unoreder_map<int, int> map;
    for (int i = 0; i < H.size(); ++i) {
        int a = H[i];
        int b = sortedH[i];
        
        if (map.find(a) != map.end())
            ++map[a];
        else
            map[a] = 1;
        
        if (map.find(b) != map.end())
            --map[b];
        else
            map[b] = -1;
            
        if (map.find(a) != map.end() && map[a] == 0)
            map.erase(a);
        if (map.find(b) != map.end() && map[b] == 0)
            map.erase(b);
        
        if (map.size() == 0)
            ++cnt;
    }
    return cnt;
}

int main() {
    int N;
    while (cin >> N) {
        vector<int> H(N);
        for (int i = 0; i < N; ++i)
            cin >> H[i];
        
        cout << getMaxTeams(H) << endl;
    }
}

第二题

题目描述

某校在积极推行无人监考制度，但是总有学生是不自觉的，如果将两个很熟的异性朋友放在同一个考场里，他们就会交流甚至作弊。因此一个考场中不能允许两个很熟的异性朋友存在，学校希望通过搬出一部分学生的方法来改善这一问题。但是又因为教室数量有限，因此希望一个教室中容下的学生尽可能多，即需要搬出教室的学生数量尽可能少。请你输出搬出教室人数最少、且字典序最小的方案。

输入描述

输出第一行有两个整数n和m，分别表示有n个男生和n个女生，有m个朋友关系。（1<=n<=500，1<=m<=100000）接下来m行，每行有两个整数，x和y，表示第x号男生和第y号女生是朋友。男生的编号均为[1,n]，女生的编号为[n+1,2n]。

输出描述

输出第一行包含一个整数a，表示最少需要搬出教室的人数。
输出第二行有a个整数，即a个需要搬出教室的人的编号，要求人数最少，且字典序最小。

分析

  • 思路：本质是二分图最小顶点覆盖问题（即最大匹配问题，Konig定理）。详见【补充知识点】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

// 判断二分图中x和y是否有连接
bool isConnected(const multimap<int, int>& edge, int x, int y) {
    auto beg = edge.lower_bound(x);
    auto end = edge.upper_bound(x);
    for (auto it = beg; it != end; ++it) {
        if (it->second == y)
            return true;
    }
    return false;
}

int augmentPath(const int& n, const multimap<int, int>& edge, unordered_map<int, int>& Mx, unordered_map<int, int>& My, int IDx, set<int>& visited) {
    // 考虑Y中所有顶点
    for (int IDy = n + 1; IDy <= 2 * n; ++IDy) {
        // 如果Y中顶点IDy与X中顶点IDx有连接，且没有访问过
        if (isConnected(edge, IDx, IDy) && visited.find(IDy) == visited.end()) {
            // 记录下该点已经被访问过了
            visited.emplace(IDy);
            // 条件1：如果IDy没有匹配，则直接将IDy匹配给IDx；
            // 条件2：如果IDy匹配过了，则从IDy之前匹配过的IDx出发，找到一条增广路，但是这里已经记录IDy被访问过了。
            // 如果第一个条件成立，则不会发生递归调用
            if (My.find(IDy) == My.end() || augmentPath(n, edge, Mx, My, My[IDy], visited)) {
                Mx[IDx] = IDy;
                My[IDy] = IDx;
                return 1;
            }
        }
    }

    return 0;
}

int maxMatching(const int& n, const multimap<int, int>& edge, unordered_map<int, int>& Mx, unordered_map<int, int>& My) {
    set<int> visited;
    int res = 0;
    // 考虑X中所有顶点
    for (int IDx = 1; IDx <= n; ++IDx) {
        // 从X中没有匹配的点出发寻找增广路
        if (Mx.find(IDx) == Mx.end()) {
            // visited记录DFS算法中顶点是否访问过
            res += augmentPath(n, edge, Mx, My, IDx, visited);
        }
    }

    return res;
}


// 由最大匹配问题转化成最小顶点覆盖问题，利用konig定理
set<int> getMinVertexCover(const int& n, const multimap<int, int>& edge, unordered_map<int, int>& Mx, unordered_map<int, int>& My) {
    stack<int> nonMatchedX; // 保存X中未匹配的点
    set<int> visited; 
    set<int> ret;

    for (int IDx = 1; IDx <= n; ++IDx) {
        ret.emplace(IDx);
        if (Mx.find(IDx) == Mx.end())
            nonMatchedX.push(IDx);
    }

    while (!nonMatchedX.empty()) {
        int x = nonMatchedX.top();
        nonMatchedX.pop();

        visited.emplace(x);
        ret.erase(x);

        // 遍历Y中的顶点IDy
        for (int IDy = n + 1; IDy <= 2 * n; ++IDy) {
            // 如果x和IDy有连接，且IDy没有被访问过，则导入
            if (isConnected(edge, x, IDy) && visited.find(IDy) == visited.end()) {
                visited.emplace(IDy);
                ret.emplace(IDy);
                if (visited.find(My[IDy]) == visited.end())
                    nonMatchedX.push(My[IDy]);
            }
        }
    }

    return ret;
}



int main() {
    int n, m;
    while (cin >> n >> m) {
        //vector<pair<int, int> > edge;
        multimap<int, int> edge;
        int p1, p2;
        for (int i = 0; i < m; ++i) {
            cin >> p1 >> p2;
            edge.emplace(p1, p2);
        }

        unordered_map<int, int> Mx; // 保存X中已经匹配的节点以及匹配到的Y中的节点
        unordered_map<int, int> My; // 保存Y中已经匹配的节点以及匹配到的X中的节点
        
        cout << maxMatching(n, edge, Mx, My) << endl;
        
        set<int> res; // 保存需要搬出教室的人的编号
        res = getMinVertexCover(n, edge, Mx, My);
        for (auto it = res.begin(); it != res.end(); ++it)
            cout << *it << ' ';
    }
}

补充知识点

参考：二分图的最大匹配、完美匹配和匈牙利算法

二分图

定义：简单来说，图中的点可以分为两组，并且使得所有边都跨越组的边界，这样的图就是一个二分图。

等价定义：不含有奇数条边的环的图。

匹配

匹配(Matching)：在图论中，一个匹配是是一个边的集合。其中任意两条边都没有公共顶点。

最大匹配(Maximum Matching)：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

完美匹配(Perfect Matching)：如果一个图的某个匹配中，所有顶点都是匹配点，那么它就是一个完美匹配。

匈牙利算法（Hungarian Algorithm）

求解最大匹配问题的一个算法。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途经另一个未匹配点（出发的点不算），则这条交替路称为增广路（Augmenting Path）。

增广路的特点：非匹配边比匹配边多一条。因此，只要把增广路中的匹配边和非匹配边的身份交换即可使图中匹配边数目比原来多了1条。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。

匈牙利树：一般由BFS构造。从一个未匹配点出发运行BFS（唯一的限制是必须走交替路），直至不能再扩展为止。

匈牙利算法要点：

  • 从左边第1个顶点开始，挑选未匹配点进行搜索，寻找增广路。
    • 如果经过一个未匹配点，说明寻找成功，更新路径信息，匹配边数+1，停止搜索；
    • 如果一直没有增广路，则不再从这个顶点开始搜索。
  • 由于找到增广路后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。DFS版本通过函数调用隐式地使用一个栈，而BFS版本使用prev数组。

几个定理：

  • 定理1：最大匹配数 = 最小点覆盖数（Konig定理）
  • 定理2：最大匹配数 = 最大独立数
  • 定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

Konig定理

参考：【learning】二分图最大匹配的König定理

已知一个二分图的最大匹配数为m。

定理阐释：

按照如下方式给这堆点打上标记：

  • 以右边部分所没有匹配到的点为起点，按交替路的方式遍历下去，直至不能继续走下去了；
  • 给沿途的点全部打上标记。

将右边没有标记的点和左边有标记的点组成一个点集，这个点集便是最小点覆盖点集。

标记时交替路性质：
对于一条在交替路上的边(u, v)，必定满足：

  1. u,v均为标号点；
  2. 若该边为匹配边，则遍历时先走到u，再走到v，即方向为从左至右；
  3. 若该边为非匹配边，则遍历时先走到v再走到u，即方向从右至左。

为何这是一个点覆盖？
首先可以把边分成两类，一类是在某条交替路上的边，一类不在。

  • 对于在交替路上的边，显然可以通过选取左边部分打上标记的点来覆盖掉。
  • 而对于不在交替路上且没有被覆盖到的边，它在右边部分的端点一定是没有标记的。

点覆盖的大小为何等于m？

  1. 由于是交替路，并且起点在右边，所以左边的被标记的点的个数必定和交替路中匹配边的个数相等。
  2. 非交替路上的且没有覆盖到的边的右端点肯定连到的是未标记的右边的点，而右边每个未被标记的点必定会连且只会连出一条匹配边。
  3. 两者相加为得到m。

m为何是最小点覆盖？
覆盖m条匹配边最少都要m个点，所以覆盖点显然无法小于这个值。