QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648307#5423. Perfect Matching0x3fffffffAC ✓422ms34316kbC++202.9kb2024-10-17 18:13:252024-10-17 18:13:25

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 18:13:25]
  • 评测
  • 测评结果:AC
  • 用时:422ms
  • 内存:34316kb
  • [2024-10-17 18:13:25]
  • 提交

answer

#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
using namespace std;
typedef pair<int, int> pii;

int n, A[MAXN + 10];
vector<pii> ans;

int L, R;
unordered_map<int, int> mpL, mpR;

vector<int> e[MAXN * 2 + 10], v[MAXN * 2 + 10];
int deg[MAXN * 2 + 10], dep[MAXN * 2 + 10];
bool vis[MAXN * 2 + 10];

// BFS 用来统计连通块内边的数量
int bfs(int S) {
    int ret = 0;
    queue<int> q;
    q.push(S); vis[S] = true;
    while (!q.empty()) {
        int sn = q.front(); q.pop();
        ret += deg[sn];
        for (int fn : e[sn]) if (!vis[fn]) {
            q.push(fn);
            vis[fn] = true;
        }
    }
    return ret / 2;
}

// 返回还没有匹配的边
int dfs(int sn, int fa, int from, int d) {
    dep[sn] = d;
    vector<int> vec;
    for (int i = 0; i < e[sn].size(); i++) {
        int fn = e[sn][i], idx = v[sn][i];
        if (fn == fa) continue;
        // 把返祖边和子节点传上来的边都记录下来
        if (dep[fn] > 0) {
            if (dep[fn] < dep[sn]) vec.push_back(idx);
        } else {
            int t = dfs(fn, sn, idx, d + 1);
            if (t > 0) vec.push_back(t);
        }
    }

    // 把记录下来的边两两匹配
    while (vec.size() > 1) {
        int x = vec.back(); vec.pop_back();
        int y = vec.back(); vec.pop_back();
        ans.push_back(pii(x, y));
    }
    if (vec.size() == 1) {
        // 还剩一条边没匹配,把连向父节点的边也用来匹配
        assert(from > 0);
        ans.push_back(pii(vec.back(), from));
        return -1;
    } else {
        // 连向父节点的边交给父节点匹配
        return from;
    }
}

void solve() {
    mpL.clear(); mpR.clear();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        mpL[A[i] - i] = 0;
        mpR[A[i] + i] = 0;
    }
    // 离散化
    L = R = 0;
    for (auto it = mpL.begin(); it != mpL.end(); it++) it->second = ++L;
    for (auto it = mpR.begin(); it != mpR.end(); it++) it->second = ++R;

    // 建立二分图
    for (int i = 1; i <= n * 2; i++) e[i].clear(), v[i].clear();
    memset(deg, 0, sizeof(int) * (n * 2 + 3));
    for (int i = 1; i <= n; i++) {
        int x = mpL[A[i] - i], y = L + mpR[A[i] + i];
        e[x].push_back(y); v[x].push_back(i);
        e[y].push_back(x); v[y].push_back(i);
        deg[x]++;  deg[y]++;
    }

    ans.clear();
    memset(vis, 0, sizeof(bool) * (n * 2 + 3));
    memset(dep, 0, sizeof(int) * (n * 2 + 3));
    // 枚举每个连通块
    for (int i = 1; i <= L + R; i++) if (!vis[i]) {
        // 奇数条边则无解
        if (bfs(i) & 1) { printf("No\n"); return; }
        // 偶数条边则构造答案
        dfs(i, 0, -1, 1);
    }

    printf("Yes\n");
    for (pii p : ans) printf("%d %d\n", p.first, p.second);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3860kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
6 3
1 4
5 2
Yes
1 3
4 2
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 238ms
memory: 28616kb

input:

10
100000
0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...

output:

Yes
78 77
138 137
201 200
242 244
287 289
309 308
315 314
321 320
335 337
380 382
396 395
450 449
459 458
462 461
480 479
515 517
518 520
524 526
554 556
567 566
617 619
660 659
734 736
761 763
788 790
851 853
903 902
933 932
978 977
987 986
1089 1088
1104 1103
1160 1162
1218 1217
1271 1273
1283 128...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

10
100
28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...

output:

Yes
99 98
97 96
95 94
93 92
91 90
89 88
87 86
85 84
83 82
81 80
79 78
77 76
75 100
33 32
31 30
29 34
38 37
36 35
27 26
25 24
23 22
21 20
19 18
17 16
15 14
13 12
11 10
9 28
73 72
71 70
69 74
8 7
6 5
4 3
2 1
68 67
66 65
64 62
61 60
59 63
58 57
56 55
54 53
52 51
50 49
48 47
46 45
44 43
42 41
40 39
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 226ms
memory: 34316kb

input:

10
100000
-40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...

output:

Yes
100000 99999
99998 99997
99996 99995
99994 99993
99992 99991
99990 99989
99988 99987
99986 99985
99984 99983
99982 99981
99980 99979
99978 99977
99976 99975
99974 99973
99972 99971
99970 99969
99968 99967
99966 99965
99964 99963
99962 99961
99960 99959
99958 99957
99956 99955
99954 99953
99952 9...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 422ms
memory: 23624kb

input:

10
100000
0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...

output:

Yes
89504 28
63463 26518
8564 1121
36811 36817
95315 8931
96991 61541
81303 70110
16772 13611
34736 778
92637 55231
18933 19162
97729 87006
59542 3408
92548 81132
83637 41302
92168 28333
71221 3610
88310 80993
74032 11544
821 940
80608 33052
42619 14756
3199 1661
47380 3633
37677 26691
67617 66364
2...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 149ms
memory: 4320kb

input:

1000
1000
-2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...

output:

No
No
No
No
No
No
Yes
14 15
37 36
75 74
113 112
131 130
144 142
152 151
167 165
171 170
185 183
186 184
202 200
207 205
213 212
221 220
245 243
267 266
272 271
278 277
286 284
314 312
330 328
334 333
372 370
377 376
401 400
423 422
426 424
442 440
466 464
476 474
501 499
515 513
559 557
580 578
589 ...

result:

ok 1000 Cases (1000 test cases)