QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106468 | #5423. Perfect Matching | cokle | TL | 0ms | 0kb | C++11 | 2.5kb | 2023-05-17 20:56:19 | 2023-05-17 20:56:22 |
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, level;
bool bfs(int n) {
queue<int> q;
for (int u = 1; u <= n; u++) {
if (match[u] == NIL) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = 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);
level.resize(n + 1);
int matching = 0;
while (bfs(n)) {
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);
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 << "匐卙卥即匑" << endl;
for (int u = 1; u <= n; u++) {
if (u < match[u]) {
cout << u << " " << match[u] << endl;
}
}
} else {
cout << "匐华卯匑" << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7