QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106459 | #5423. Perfect Matching | cokle | ML | 2ms | 3412kb | C++11 | 2.5kb | 2023-05-17 20:39:06 | 2023-05-17 20:39:09 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
const int NIL = 0;
vector<vector<int>> adjList;
vector<int> dist, match;
bool bfs() {
queue<int> q;
for (int u = 1; u < adjList.size(); u++) {
if (match[u] == NIL) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = INF;
}
}
dist[NIL] = INF;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] < dist[NIL]) {
for (int v : adjList[u]) {
if (dist[match[v]] == INF) {
dist[match[v]] = dist[u] + 1;
q.push(match[v]);
}
}
}
}
return dist[NIL] != INF;
}
bool dfs(int u) {
if (u == NIL) {
return true;
}
for (int v : adjList[u]) {
if (dist[match[v]] == dist[u] + 1 && dfs(match[v])) {
match[u] = v;
match[v] = u;
return true;
}
}
dist[u] = INF;
return false;
}
int hopcroftKarp(int n) {
dist.resize(n + 1);
match.resize(n + 1);
int matching = 0;
while (bfs()) {
for (int u = 1; u <= n; u++) {
if (match[u] == NIL && dfs(u)) {
matching++;
}
}
}
return matching;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 构建图的邻接表表示
adjList.clear();
adjList.resize(n + 1);
dist.clear();
dist.resize(n + 1);
match.clear();
match.resize(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (abs(i - j) == abs(a[i] - a[j])) {
adjList[i].push_back(j);
adjList[j].push_back(i);
}
}
}
// 使用Hopcroft-Karp算法求解完美匹配
int matching = hopcroftKarp(n);
if (matching == n / 2) {
cout << "Yes" << endl;
for (int u = 1; u <= n; u++) {
if (u < match[u]) {
cout << u << " " << match[u] << endl;
}
}
} else {
cout << "No" << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3412kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 2 5 3 6 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Memory Limit Exceeded
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...