Cheeeeen the Cute Cat

前往 算竞题解 分类 || 前往 算竞模板 分类

原题链接

C-Cheeeeen the Cute Cat 2023牛客暑期多校训练营5

简明题意

给定一个二分图的 0101 邻接矩阵，表示一个二分图，如矩阵中 ai,ja_{i,j} 为 11 表示二分图存在一条无向边 (i,n+j)(i,n+j)。题目保证二分图共有 2n2n 个点，n(n−1)2\frac{n(n-1)}{2} 条边，不存在边 (i,n+i)(i,n+i)，不同时存在边 (i,n+j)(i,n+j) 和 (j,n+i)(j,n+i)。现求二分图最大匹配，n≤3000n \le 3000。

解题思路

本题需要分为两步，因为题目隐藏了其模型。

转化模型

这是一幅稠密图，如果直接跑二分图匹配时间复杂度是 O(n3)O(n^3) (匈牙利算法) 或 O(n2.5)O(n^{2.5}) (dinic 算法)，实际题目模型与二分图没有关系。

我们可以将二分图从左集到右集的一条无向边视为转化模型（后文称转化图）上的一条有向边，如二分图无向边 (i,n+j)(i, n+j) 可以视为图上的有向边 (i,j)(i,j)，每条有向边对应一个可以选择的匹配，有向边的起点表示匹配的左集点，终点表示匹配的右集点。

根据匹配的定义，在转化图上，不能有多个匹配共享同一起点，不能有多个匹配共享同一终点。换言之，对于转化图的匹配图，所有点的入度 ≤1\le 1，所有点的出度 ≤1\le 1，所以匹配图一定是不连通的链与圈的集合。

根据题意保证，在转化图上，不存在反向边，不存在自环，有恰好有 n(n−1)2\frac{n(n-1)}{2} 条边，所以转化图是竞赛图。

注：竞赛图，无向完全图的无向边定向后的图就是竞赛图。竞赛一定没有重边、反边、自环，恰有 n(n−1)2\frac{n(n-1)}{2} 条边。

竞赛图与哈密顿图

对于一个稠密图有很好的与哈密顿图相关的性质，复习一下。

  • 无向图：
    • 对于 n(n≥2)n(n \ge 2) 阶无向简单图 GG，对于其中的任意不相邻的点 vxv_x、vyv_y，都有度数之和 deg(vx)+deg(vy)≥n−1deg(v_x)+deg(v_y) \ge n-1，图中必然存在哈密顿通路。
    • 对于 n(n≥3)n(n \ge 3) 阶无向简单图 GG，对于其中的任意不相邻的点 vxv_x、vyv_y，都有度数之和 deg(vx)+deg(vy)≥ndeg(v_x)+deg(v_y) \ge n，图中必然存在哈密顿回路。
    • 对于 n(n≥3)n(n \ge 3) 阶无向简单图 GG，对于其中的任意的点 vxv_x，都有度数 deg(vx)≥n2deg(v_x) \ge \frac{n}{2}，图中必然存在哈密顿回路。（由上一条定理）
  • 有向图：
    • 对于 n(n≥2)n(n \ge 2) 阶竞赛图(无向完全图定向) GG，图中必然存在哈密顿通路。
    • 对于 n(n≥2)n(n \ge 2) 阶竞赛图作为去边子集的图 GG，图中必然存在哈密顿通路。（由上一条定理）
    • 对于 n(n≥2)n(n \ge 2) 阶竞赛图作为去边子集的图 GG，如果图是强连通的，图中必然存在哈密顿回路。

我们现在需要在转化图中找到尽可能长或多的链或圈，根据竞赛图的性质，转化图中一定存在一条哈密顿通路，因此一定存在一条长度为 nn 的链，那么至少存在 n−1n-1 个匹配。如果转化图是强连通的，根据竞赛图性质，那么图中必然存在哈密顿回路，因此一定存在一个长度为 nn 的圈，那么存在 nn 个匹配。但这并不是存在 nn 个匹配的充要条件，只要每个点都属于一个圈，那么整个转化图就存在 nn 个匹配，所有竞赛图的子图都是竞赛图，因此只要其可以划分成若干个强连通的子图即可，即转化图所有强连通分量大小 ≥2\ge 2。

所以结论是，如果图的所有强连通分量大小 ≥2\ge 2，匹配数为 nn，否则匹配数为 n−1n-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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
// Cheeeeen the Cute Cat
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1  // Test Switch
#else
// #define TEST 1
#define LOCAL 1  // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 3005;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

vector<int> edge[MAX];
bool in_stk[MAX] = {false};  // 访问标记
int low[MAX];                // scc 并查集的前驱
int dfn[MAX], cnt_dfn = 0;   // dfs 序号
int stk[MAX], cnt_stk = 0;   // 临时栈, 用于延迟获取 scc 成员
int root[MAX], cnt_scc = 0;  // scc 并查集的根, 以及 scc 的数量
int nodes[MAX];              // scc 并查集的根上对应集合的点数

void __tarjan(int x) {
    low[x] = dfn[x] = ++cnt_dfn;
    in_stk[x] = true;
    stk[cnt_stk++] = x;
    for (int y : edge[x])
        if (dfn[y] == 0) {
            __tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (in_stk[y])
            low[x] = min(low[x], dfn[y]);
    if (low[x] == dfn[x]) {
        nodes[low[x]] = 0;
        do {
            cnt_stk--;
            in_stk[stk[cnt_stk]] = false;
            root[stk[cnt_stk]] = low[x];
            nodes[low[x]]++;
        } while (stk[cnt_stk] != x);
        cnt_scc++;
    }
}

void tarjan(int n) {
    fill(dfn, dfn + n + 1, 0);
    cnt_dfn = 0;
    cnt_scc = 0;
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0)
            __tarjan(i);
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            if (x) {
                edge[i].push_back(j);
            }
        }
    }
    tarjan(n);
    for (int i = 1; i <= n; i++) {
        if (nodes[root[i]] == 1) {
            cout << n - 1 << endl;
            return;
        }
    }
    cout << n << endl;
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif
    return 0;
}